bernett's blog

MemSQL Start[c]UP 2.0 — Round 1 problem F
By bernett, 10 years ago, In English

Hello everyone, I have been thinking about this problem http://codeforces.com/contest/452/problem/F for quite some time and finally couldnt come up with anything. Then I saw this solution to the problem http://codeforces.com/contest/452/submission/7280377 . What I could get from his solution is, it is assumed that the middle value and one of the numbers a or b is within a range of 5. Could someone please explain how this approach works and its proof. Also correct me if my assumption about his solution is wrong.

  • Vote: I like it
  • +21
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Lololololol such trolling! I think that is highly related and proves that if there will be 11 instead of 5 that code in fact will be correct :o! How haven't I noticed that!?!? http://codeforces.com/blog/entry/13095#comment-180033

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

There is pretty simple solution with data structures plus hash which allows to update polynomial hash. The point is if middle point does not have two number one at left one at right , in this situation think about a sequence i th element equals to 0 if it is at left and 1 otherwise and this sequence is palindromic on center position of (a+b)/2. After this observation you can do some kind of sweep style algorithm.

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I found only one solution that uses no hashes , and no tricks like the solution you posted.(link) but i can't prove it. Could somebody help to prove it?

Solution you posted is not correct. One test to show it's not correct : 10 10 5 1 3 2 9 7 6 4 8

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Finally i proved why it works.

    w2 function works like this: If there is a even number that can be rewritten as sum of two odd numbers/2 (one in left side and other in right side) , it returns false, otherwise true.

    If we have w2() as a black box, we can solve this problem.

    First check even numbers by odd numbers. (w2(v)).

    Then check odd numbers by even numbers(--v , w2(v)).

    It remains to check even numbers by even numbers and odd numbers by odd numbers. So we split the sequence in two sequence of even numbers and odd numbers , and for making new sequences (l and r) a permutation , we divide each number by two.(To easily use the same function Work)

    How w2() works? It depends on a lemma :

    --For an even number v[i] , if sum of the biggest odd number on the right (ohi) and on the left (hi) is bigger than 2*v[i] , and sum of the smallest odd number on the right(olo) and on the left(lo) is smaller than 2*v[i] , there is at least one arithmetic sequence of length 3.

    --Proof : If v[i] = 2*k , and there is an j that 2*k-j lies on different side than 2*k+j , 2*k-j , 2*k and 2*k+j make the requested sequence. Other way for each j that 1 <= 2*k-j , 2*k+j <= n , 2*k-j , 2*k+j lie on the same side. We prove by induction on difference with 2*k that all elements in {2*k-1,2*k+1,2*k-3,2*k+3,...} lie on the same side.(That it is impossible , because there should be at least one element in the other side to get its minimum and maximum) The basis is obvious : 2*k-1 and 2*k+1 are on the same side.(otherwise there would be a arithmetic sequence)

    Due to symmetry suppose that sequence likes this. ...2k...2k+1...2k-1... 2k+3 is in the right side of 2k , otherway we have(2k+3,2k+1,2k-1), and 2k-3 is in the same side with 2k+3.(right of 2k) By the same argument 2k+3 is in the right side of 2k+1 , and 2k-3 is in the left side of 2k-1.

    With some similar argument we can show always 2k+o , 2k-o , 2k+o+2 , 2k+o-2 are in right side of 2k ,(o is a odd number) and if 2k+o+2 is in right side of 2k+o ,, 2k-o-2 is in left side of 2k-o , and vice versa.

    For showing this for o+4 and o+2 , we first show that 2k+o+4 is in the right side. If 2k+o+4 is in left side , 2k+o+4 , 2k+o+2 , 2k+o make a good sequence or 2k-o-4 , 2k-o-2 , 2k-o make a good sequnce. For the remain suppose this positions :

    a)...2k...2k+o...2k+o+2...2k-o-2...2k-o... --> 2k+o+4 is in left side of 2k+o+2 and 2k-o-4 is in right side of 2k-o-2

    b)...2k...2k+o+2...2k+o...2k-o...2k-o-2... --> 2k+o+4 is in right side of 2k+o+2 and 2k-o-4 is in left side of 2k-o-2

    c)...2k...2k+o+2...2k-o...2k+o...2k-o-2... --> 2k+o+4 is in right side of 2k+o+2 and 2k-o-4 is in left side of 2k-o-2

    d)...2k...2k-o...2k+o+2...2k-o-2...2k+o... --> 2k+o+4 is in right side of 2k+o+2 and 2k-o-4 is in left side of 2k-o-2

    Other positions can be proved by symmetry.

    By knowing this lemma w2() is simple :).

    I hope this proof to be correct and helpful. :)

    → Reply