1135. Recruits acm.timus.ru Problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
pkiulian
New poster
Posts: 1
Joined: Thu Nov 29, 2012 6:00 pm
Location: Bonn, Germany
Contact:

1135. Recruits acm.timus.ru Problem

Post by pkiulian » Thu Nov 29, 2012 6:57 pm

Ok so I have a problem and on acm.timus.ru, the answers come too seldom.

For the problem 1135. Recruits. I do:
So what I am doing is to note 1 instead of > and 0 instead of <. Therefore if I have the configuration 10 then it will become 01. The 01 configuration doesn't change.
Therefore if I take the example from the problem I have

110010
101001
010101
001011
000111

So I see there is a shifting of the zero's to the left and a of one's to the right.
So I am saving in the beginning the positions of zero's in an array (zero[]) and the positions of the one's in another array (one[]).
then I consider k = one[0].

Therefore the all algorithm (after reading the data) looks practically like this

k=one[0];
for (int i=0;i<z;i++){
if ((zero-k) >=0){
result+=(zero-k);
k++;
}
}

I think the complexity of this is even O(z) where z is the numbers of zero's.

The problem with this is that I obtain TL on test 15. Is there anything faster or is only my coding problme (java)?

Please help me with suggestions why this is TL? I find it hard to belive there is something faster algorithmic than O(n) here.
Thank you!

Post Reply

Return to “Algorithms”