I know AC solution to this problem, that uses O(1) memory. It is wrong, and answers "Not a proof" for test
4
3
1
4
2

Yes, it's my solution with ID = 2350964
http://acm.timus.ru/status.aspx?space=1&num=1494&author=52345

I think that there is no correct solution with memory complexity less than O(N). N or at least N/2 integers may be required to be stored at some moment on hard test. On page
http://acm.timus.ru/rating.aspx?space=1&num=1494&count=100
there are many solutions that use too little memory to be correct.

Your test and some others were added. 50 authors lost AC.

By the way, it is possible to store N bools to solve this problem, and AC solutions with memory about 200K are OK.

Edited by author 20.11.2008 13:52

Is it _really_ possible to solve this problem using only N _booleans_? I mean it seems good enough to keep all necessary information, but not enough to search the information _fast_, so solutions with N booleans should probably get TL on a good test.

Could you send such solution to e-mail, associated with my account?

Test generated by the following program may be hard for some solutions storing only booleans.

const
   n = 100000;
var
   low, high : integer;
begin
   assert(n mod 3 = 1);
   low := n div 3 + 1;
   high := low + 2;
   writeln(n);
   writeln(low);
   low := low - 1;
   while low > 0 do begin
      writeln(high);
      writeln(high - 1);
      high := high + 2;
      writeln(low);
      low := low - 1;
   end;
end.

Edited by author 22.11.2008 01:05

I can imagine a correct solution using N bits packed in integers. It uses O(N^2) time but with very good constant. But I think that solution using N booleans cannot pass TL.

And you are right! Thank you. I added your test and some other tests of similar structure, and 85 authors got TL and WA.