not fast enough

[lelekos]

So i have to write a programm that reads integers and if
a) the number of positive integers is the same with negatives integers
b) the sequence of posivite integers is the same with the absolut of negatives integers.
it should type "yes". example for b): if i type
3 4 5 -3 -4 -5 it should display "yes" but if i type 3 4 5 -3 -5 -4 it should type "no". I have 2 lists(pos for positives and neg for negtives). My code runs perfectly in all test cases the only problem is that i want it to run in less than a second even for millions of numbers. In that case it runs in 1.08 seconds. I even tried to compare the sequences after i read all the integers but it still doesn't run in less than a second. How can i improve that?

int main ()
{
  int ar, sumt, suma, sum, i, j;
  queue pos;
  queue neg;
  sumt = 0;
  suma = 0;
  sum = 0;
  i = 0;
  j = 0;
  while (cin >> ar) {
    if (ar > 0) {
      pos.enqueue (ar);
      sumt = sumt + 1;
      j++ ;
    }
    else if (ar < 0) {
      neg.enqueue (ar);
      suma = suma + 1;
      i++;
    }
    if ((j > 0) && (i > 0))
    {
      if (pos.dequeue() == -neg.dequeue()) sum = sum + 1;
      i--;
      j--;
    }
  }
  if ((sumt == suma) && (suma == sum)) cout << "yes" << endl;
  else cout << "no" << endl;
  return 0;
}

[Ganado]

Usually, when dealing with millions of I/O operations, the bottleneck is stream flushing.
std::endl flushes the stream every time, so try replacing endl with "\n" and see if that helps.

[lastchance]

Condition (b) implies condition (a), so you need only consider condition (b).

You should exit immediately if condition (b) fails at any point - not read all the integers and then decide. For example, with your sequence 3 4 5 -3 -5 -4 you can write "no" when you get to the -5, not all the way to the -4.

It may be easier to make an early exit from a separate function than to put everything in main().

[lelekos]

i tried it and it still runs in the same time. i tried to run the code even without comparing the 2 lists (without lines 22-27) and it still runs in the same time (1.08 secs). so maybe i shouldn't even use 2 lists?

[Ganado]

How are you measuring that? If what you say is true, it sounds like the enqueueing and dequeuing is the bottleneck. I think you should be able to change the logic around to only use 1 queue, if I'm not mistaken. Is there a max to how long one sequence can be? Perhaps just use a static array, if so.

[coder777]

Do not use queue. At least vector with a large capacity or you may check a list.
You do not need two containers just one. Instead use two loops.
The first loop is storing the values and detect whether there is a change of the sign.
The second loop just compares the following values.
You may have a third encompassing loop if you have multiple of this sequences.

[ne555]

> Usually, when dealing with millions of I/O operations, the bottleneck is stream flushing.
> std::endl flushes the stream every time, so try replacing endl with "\n" and see if that helps.
there is only one output operation...
for the inputs, may try std::ios_base::sync_with_stdio(false); at the beginning.
http://codeforces.com/blog/entry/925


> it sounds like the enqueueing and dequeuing is the bottleneck.
perhaps you should show the implementation of those function (and the `queue' class).
or simply use a stl container.


> I think you should be able to change the logic around to only use 1 queue
>> You do not need two containers just one.
the second container would have at most one element.
(dunno how removing one container may speed up anything)


> it still doesn't run in less than a second. How can i improve that?
if `.enqueue()' and `.dequeue()' are O(1) then your algorithm is O(n)
so aside from lastchance's improvement, there is no much you can do.

consider buying a better computer.
(you are compiling with optimizations, ¿right?)

[Ganado]

there is only one output operation...

Ha you're right, I misread the code.

Good point with the implementation of the queue class. I assumed he was using the stl, but the functions in the stl are called different things.

And yes, I'm aware that my suggestion was a micro-optimization, the only thing it would decrease the runtime by is a constant allocation (unless OP is dealing with very long sequences that force the queue to re-allocate).

Building off your note, my guess is OP's queue class is re-allocating every enqueue?

[jonnin]

can you stop if you find the answer is no early?

do you know the list is +++++ ------- format ? If so, can you just jump to the middle of the list and check it much simpler:

if( array[index1] == array[index2] && something)
//still yes
//else early exit on no?

[lastchance]

Uses one STL queue; single loop; O(N) worst case; only (explicit) arithmetic operation is unary minus.

#include <iostream>
#include <sstream>
#include <queue>
using namespace std;

//======================================================================

bool isBalanced( istream &in )
{
   bool Qpositive = false;                                 // Are current numbers in the queue positive?
   queue<int> Q;
   int n;

   while ( in >> n )
   {
      if ( n )                                             // Only concerned with non-zero numbers
      {
         bool npositive = ( n > 0 );                       // Is the test number positive?
         if ( Q.empty() || (npositive == Qpositive) )      // Queue is either empty, or has same sign ...
         {
            Q.push( n );                                   // ... so add this number
            Qpositive = npositive;                            
         }
         else                                              // Numbers in the queue have opposite sign ...
         {
            if ( (-n) != Q.front() ) return false;         // ... so check this number ... exit if wrong
            Q.pop();                                       //                          ... remove balance if right
         }
      }
   }
   return Q.empty();
}

//======================================================================

int main()
{
   vector<string> TESTS = { " 3 4 5 -3 -4 -5    ",
                            " 3 4 5 -3 -5 -4    ",
                            " 3 4 5 -3 -4 -5 -4 ",
                            " -3 -4 -5  3 4 5   ",
                            " -3 3 5 -5 4 -4    ",
                            " -3 3 0  5 -5 4 -4 ",
                            " -3 4 5 -5 3 -4    " };

   for ( string s : TESTS )
   {
      stringstream ss( s );
      cout << s << ": " << ( isBalanced( ss ) ? "yes" : "no" ) << endl;
   }
}

//====================================================================== 

 3 4 5 -3 -4 -5    : yes
 3 4 5 -3 -5 -4    : no
 3 4 5 -3 -4 -5 -4 : no
 -3 -4 -5  3 4 5   : yes
 -3 3 5 -5 4 -4    : yes
 -3 3 0  5 -5 4 -4 : yes
 -3 4 5 -5 3 -4    : no

Unless @lelekos is looping through a whole set of sequences, then his main could be reduced to

int main()
{
   cout << ( isBalanced( cin ) ? "yes" : "no" ) << endl;
}

If it was looping through many sequences then you would have to empty cin after each test, as the isBalanced() routine may be able to return without emptying the stream.

[dhayden]

i tried to run the code even without comparing the 2 lists (without lines 22-27) and it still runs in the same time (1.08 secs).

Then clearly the problem is the queue class. Can you post the implementation?

[lelekos]

well it worked with only one queue and a few other changes :P. thanks a lot !