Do all the soldiers have different ranks ( id's)?

I guess most of the Java Programs are timing out when I submit. i.e. the result is not obtained from the program within the time limit.

I can optimize the code, but i don't know to what level. In the problem itself, if you guys can give the order of the input data which will be used to verify the program, it will be easier for us to optimize.

@Pradeep What do you mean by giving the order of the input data?

Hi Aniruddha. Sorry for the late reply. I mean to say, you are giving some input data and verifying my program by running it in codechef server machine right? If you give us the order of the input data that you use to verify my program, it would be useful to optimize my code. I am seeing a warning in the above problem saying "large input data". But, if you have given the order of input data it would have been useful. For example, in this problem, you could have given - Order of input: 10 test cases, maximum 100 soldiers per test case.

i have tried optimizing to the greatest.. but still says timelimit exceeded can somebody help...

@darshan You might want to check the complexity of your solution. If your complexity is of a higher order, no matter how hard you optimize it, it won't run in time.

my algorithm runs in O(N^2) time in the worst case. It is impossible to reduce it to O(N)... And I cant figure out how to do it in O(NlogN) time... :S

btw, is there a case where the input is
0 1 2 3 4 5 6 7...

I would be very surprised if anyone got this in java under time.

Is it possible that a soldier can move more steps to left than the actual number of soldiers standing on its left. For example: "0 2 2 3 1" Is this case possible? Can 2nd soldier move 2 steps to left even if there is only one soldier is standing on its left..?

@vinay Please re-read the problem statement. Your question is answered in the statement itself.

No, that wouldn't make any sense.

Hi, Can I submit a solution in C#? Also what would be the signature of method which I have to write? Is it as follows?

    public static string Solve(string [ ])

 what must be the time complexity???

like O(n), O(n^2) for this program to run...

Has to be better than O(n^2).

can sm1 give me its solution

How do I submit code written in C#. I submitted a console app and then I submitted the source code. Bothe the times i got compilation error.

 

Vinayak

does the time taken  for finding the answer matter on whether i use a linked list or an array??

or it just depends only on the order?

Well, I am unclear as to what you mean by 'order'. Linked lists and arrays are two different data structures and as such, comparison between the two is inappropriate.

i made a code for this problem in turboc c++ in windows .... i modified it to run on the g++ compiler provided by cygwin on windows... but it is not compiling on codechef judge

pls do post a rpli, i hav tried several times to submit the solution

Please take a look at Sample Solutions and the FAQ

man its an o(n) simple algo .....

Hey where do i find the solution to this problem???

OR

Can anyone give some hint?? i tried it with linked list.

But it took too much time

Please give some alternative algo!!

I'd like to point out that the examples are a bit ambiguous.

I originally interpreted the question as, "List original position by rank" instead of "List rank by original position". It's easy to see which is correct when you consider it, but the example outputs are the same either way.

It wasn't until a friend (who originally agreed that I was doing it correctly) pointed out that I had it backwards that I corrected my mistake.

I think the problem statement + the examples do a good job of explaining what is required.

Anybody able to get the O(NlogN) time..?

My solution: Worst case O(N^2) & best case O(N). getting TLE.

 

TO THE WEBMASTER

Please clarify in the question that the positions moved by a soldier array is given such that the soldiers are standing in the wrong formation and not after sorting how much each soldier had to move.

Hi , From where to read inputs and where to put output ..i mean console or file or is there any method signature... any info plz...

Standard input/output streams.

Thanks Stephen , Is there any successfull submiotion for this problem in Java .. i mean in time...i am going out of time.

Yes.

I am getting RunTimeError ..How can i know what type of error ...any info.. plzz

It's a runtime error. Your program ceased to execute midway. Please test on the local system with large test cases.

I have hit on a O(n) algo, its giving proper answers for the quoted test cases, but the submission says wrong answer.

I have pasted my code in forum at

http://discuss.codechef.com/showthread.php?t=922

Anyone plz help  :)

i think program has to be O(n²) for the worst case and O(n) best case. the sorting algorithm is insertion sort so to get back the unsorted array, we would need a similar algorithm but doing the opposite.

I used an algo which doesnt have any sorting...so it should always work in linear time.

It has given correct answers for above test cases as well.

I tried hard but cant understand the bug in my code.

Any help....

My code is at,

http://discuss.codechef.com/showthread.php?t=922

I am also curious, was there any C program submission without TLE. I have updated my soln but still I am getting TLE.

Posted my soln in http://discuss.codechef.com/showthread.php?t=922

You can get the answer to your question by simply checking out the list of successful submissions.

the solution is not being displayed in the list of submissions

My solution works fine for the problem cases stated but the I still get a wrong answer on submission.

I have posted my solution at http://discuss.codechef.com/showthread.php?t=922

@Aniruddha

what would be the steps order for the final rank order 32415?

It is unclear that the soldier would move left until there is no one superior to his (just) left or to his left direction?

Each soldier moves until there are no superiors anywhere to the left of the soldier. Otherwise they wouldn't end up sorted, would they?

I am getting run time error which says "Run Time Error(OTHER)". Can you tell me where exactly the problem is.

I have written code in c# thus "int" can easily be assigned with 200000 (Max value), my array is not going out of bound. I have checked everything but still getting error.

@Admin - Please help!

Other implies using too much memory. Your StringBuilder is going to be far too large by the end of the last test.

You should not be waiting until the end of your program to print things out. Read the new FAQ.

@Stephen - Thanks for reply. I am printing result after each test case besides that I have removed my Array as well and now its exceeding the time limit. :( 

No clue what is going wrong and how to optimize it further... :(

I just test two different methods, using tree or skip list can solve this problem. And the solution is mentioned in my blog

http://washingtonzju.blogspot.com/2010/01/solution-of-ordering-soldiers....

:)

@admin:

My code for ORDERS runs in O(nlogn) time. For n=200000, for the worst case input, the code takes less than 3 seconds to find the solution. But printing the solution is taking a lot of time, ~20 seconds in Java. What should i do?

can we have the exact Test cases our solutions are subjected to, this will help us in designing an optimum solution

No. FAQ

FAQ

Hello all,

I posted a solution which gives the wrong answer. The problem of this is that it gives exactly the same output as this one on the bunch of tests I did (up to 200000 soldiers, several instances...). The one I linked is a naive solution which should be exact. I cannot know exactly because it runs out of time here :)

So without giving the code I'm trying now, can someone try to explain me what is wrong with my naive solution, without considering the time it takes to solve the problem?

 

Thx!

It is exceeding the time limit even in python..can somebody help!!!

I have a very small algo of around 28 lines but it is still failing

@ADMIN..

IS ALL THE CASES MUST HAVE A SOLUTION...??

MY MEAN TO SAY THAT IS THERE IS ANY CASE LIKE THIS

1

5

1 0 0 0 0

BECAUSE 1 RANK ONE CAN'T MOVE TO THEIR LEFT BECAUSE IT IS ALREADY AT LEFT MOST POSITION.....

PLEASE HELP....

can we use Scanner class to take input from console

??

plz help

 

Program working f9 in my pC

but runtime error in codechef

(code removed by admin)

Do not post code here. Read the FAQ.

Scanner is supported, but is extremely slow at reading input so you really shouldn't use. (Though, your algorithm is also too slow, so changing input methods alone won't help :))

The reason you are getting a runtime error would be obvious if you had tested your code on a maximal sized input, so I presume you haven't tried that yet.

i was trying reverse* method,......... worked perfect ....... but time limit exceeding ...  :(

Can we have cases like :

 

0 0 0 1 2   i.e ...  1 2 5 4 3

0 0 0 3 3  i.e ...  3 4 5 1 2

 

coz my algorithm solves all cases possible

 

and sample cases are of type 0 1 0 , 0 1 2 0 1

 

@Anoop

In my opinion, your 2nd case (0 0 0 3 3) should return 4 5 1 2 3.

@Guillaume Verger...

for 4 5 1 2 3 it will be 0 0 2 2 2

@Anoop

Thx! Your answer points where I misunderstood this problem :) I thought that given the input we had to make the soldiers walk and then return the position. In the example 0 0 0 3 3, the soldiers 4 and 5 would have done 3 steps, going to the left of the soldier 1.

The program compiled successfully on my computer....but it shows that there is a compilation error in my program.It shows 'main' class not found,whereas there is a 'main' class in my program...the program's in Java...j2se

Lets talk about the case

 

5

0 1 2 0 1

1 2 3 4 5 (5th being the highest rank, there is no superior to 5 so it should not be performing any movement)

The movement for highest rank should always be zero.

 

I am not sure if I missed any thing here.

ignore above! i got it now

Hi all,

i guess ... an algorithm with time complexity worst case O(n^2) and best case O(n) is enough, but the key factor is reducing time needed for reading input...

Is that so ??

Expecting comments from those who solved this problem ..

 

thanks

what does runtime error (other) include specifically.My code gives runtime 0.25 & memory 220.3M as shown by codechef.i had earlier submitted a solution for another problem with same memory requirement.the Faq and sample solution have not helped evn..sum1 pls help

I ve tested all cases in by pc. on dynamically alloting d arrary its comming TIME LIMT EXCEEDED (3.5 M). when i m statically allocating array size to 50000 den its comming RUNTIME EXCEPTION (1.50 TIME and 2.9M) none of the other code is been changed.

Did you have a question? Since the problem says n can be up to 200000, it's pretty clear why using 50000 would give you a runtime error. If you were asking why your code was timing out, have you tried test cases with n=200000?

To Admin:

I am very much confused about the input format!!!  According to format the orders of the soldiers should be input in a single line. But any of the solution is not precisely following the input format as specified.

In C, the write scanf statement in a loop which is now way going to accept input from a single line with values separated by spaces. Its very confusing. Please tell me whether it can be done or not. Or provide me with the link of a running solution so that i can get the exact format n proceed.

scanf in a while loop will read inputs from a single line separated by spaces.. that's how scanf works. I'm not really sure what you're asking.

Please read this small code. It'll clearify my problem. I am trying to read 5 values separated by space using scanf and it gives me Segmentation Fault. I am using GCC. So how the space separated values are being accepted in the solution to the above problem using the same pattern of input.

#include <stdio.h>
int main()
{
int arr[5],i=0;
while(i<5)
scanf("%d",arr[i++]);
return 0;
}

See forum. Or a reference.

Thnks a lot. Got the reply in forum. Silly mistake. :)

I have submitted my solution which runs for the sample test cases and one mentioned in the comment.

But, at the end, it got wrong answer. Is there any way to know for which test case, it goes wrong.

What the hell

1)The question is ambiguous on direction left and right

2) anyway I solved it on my system with a very portable language java and it is running well for various test cases, but when I sumit the file it shows some compile time( not runtime) errors . How it could be possible

How exactly is it ambiguous? Everything involving left and right seems perfectly clear to me.

As for your compile error, that is because you haven't read the FAQ so you do not understand what the judge requires.

The final content of the console should look like:

2
3
0 1 0
5
0 1 2 0 1

2 1 3

3 2 1 5 4

or

2
3
0 1 0
2 1 3
5
0 1 2 0 1
3 2 1 5 4

forget the previous one I read the FAQ

 

but I always have this error when I submit code

:( internal error occurred in the system

 

Please help me to understand this one

In case of php code, you need to execute

php -q test.php < in.txt > out.txt

instead of

php test.php < in.txt > out.txt

because php by default adds HTTP headers in output thereby causing result as "Wrong Answer"

Pls help

run time error for java program

is there any way to get the case for which my solution fails?

Hm, my code was judged to take 24.27s to complete, but it still succeeded. Weird.

@narainbalaji : Try creating some random test cases and manually check your programs output.

Is there something wrong with an extra space at the end of the line? Does that invalidate the result?

AN arraYliST is fAr more effICieNt tHAN A linKedlist fOr tHis probLeM aLtHOugH iT DOes nOt SolVe It iN TIme!

@admin: my code works well on my sustem but it shows runtime error on codechef...why??

i used a binary tree.. logn insertion and then a recursive inorder traversal to find final positions. still time limit exceeded :S now im starting to tire.. :(

please! help someone? is there something i dont see here? can I do without using a binary tree??

I see that most solutions are in C/C++ and extremely few in Python or JAVA. Just wondering why so. Is that the distribution of choice of programming languages on CodeChef or is it just this problem? I wrote correct solution to this problem in both python and Java but bother are exceeding time limit. If the time limit is 13 seconds how come the last couple of programs have succeeded despite taking a much longer time ?

Can somebody point out why my solution is timing out: Here is my code(C) # include void cal_rank(int *pos,int array_size) { //printf("Size:%dn",array_size); int pos_shift,n,m; for(n=0;n0;--num_test) { scanf("%dn",&num_sol); //printf("Num of soldiers: %dn",num_sol); pointer = (int *)calloc((num_sol),(sizeof(int))); arg = pointer; size = 0; for(num_sol;num_sol>0;--num_sol) { scanf("%d",pointer); //printf(":%d:",*(pointer)); ++pointer; ++size; } //printf("nEnd of test casen"); cal_rank(arg,size); free(arg); printf("n"); } //free(arg); } int main() { get_input(); return 0; }

Can somebody point out why my solution is timing out: Here is my code(C) # include void cal_rank(int *pos,int array_size) { //printf("Size:%dn",array_size); int pos_shift,n,m; for(n=0;n0;--num_test) { scanf("%dn",&num_sol); //printf("Num of soldiers: %dn",num_sol); pointer = (int *)calloc((num_sol),(sizeof(int))); arg = pointer; size = 0; for(num_sol;num_sol>0;--num_sol) { scanf("%d",pointer); //printf(":%d:",*(pointer)); ++pointer; ++size; } //printf("nEnd of test casen"); cal_rank(arg,size); free(arg); printf("n"); } //free(arg); } int main() { get_input(); return 0; }

can someone help me with submission. i am submitting my program but site says this language won't work. i am using c++

does anyone has any idea whether the test cases have the worst case .....1 2 3 4 5... too....cuz i guess dat will change everythnng...thnx

This question has a clear answer with O(n^2) . I use this solution for test. my solution is O(N^1.5) . I have compared result of my solution and the O(n^2) result for 10000 times and all of them are the same. i test it for big sizes such as 20000 , 200000 and get no error from this test. but I get wrong answer from site. should I place extra 'n' or other thing into my result?

I used a simple insertion sort. Through i expected time limit exceeded, i keep on getting wrong answer! i have tested my ans with randomly generated large inputs against some of the accepted solutions and found their diff returns the output to be same! please help!

I, sure my solution should work and it is working ofr the sample program but it is still not being accepted . why so ? :/

My logic is undeniable :p the answer coming in slmost zero seconds . what more do you expect :o

I always get time limit exceeded error

this code produces the exact requirement in my pc and in microsoft visual c++ 6.0, but upon submission iam told time limit exceeded. somebody help me. i will be very pleased to be helped. #include int soldiers[200000]; int moves[200000]; int i, j, k, m, n, t, x, count, temp,xindex; int main() { scanf("%d",&t); do{ scanf("%d",&n); for(xindex=0;xindex1) { m=i-x; temp=soldiers[i]; for(j=i;j>m;j--) { soldiers[j]=soldiers[j-1]; } soldiers[m]=temp; } } printf("n"); for(k=0;k0); return 0; }