EternalFire's blog

Problem "per" POI 03
By EternalFire, history, 6 years ago, In English

https://szkopul.edu.pl/problemset/problem/l85hlaT4lDfPzwm3IPUHIMVo/site/?key=statement

I'm getting stuck at this problem. Could you give me a hint ? Thanks.

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

Comments Comments (10)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by EternalFire (previous revision, new revision, compare).

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

Well, I am not able to think of any solution and looks like no one helped you so here is the code by ko_osaga if you didn't come across it yet.

→ Reply
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Notice that for any 3 length AP , the first and last term must be of the same parity , hence if we can we can ensure that for every middle element , all elements with odd parity lie on left and all with even parity lie on right , we are done.
so just pick the middle element of 1..n , put all odd terms on left and all even terms on right , and recursively solve them.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But then won't all elements on depth two of the recursion be of the same parity? Can you explain the solution in a with some more details.

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

      Let's look at the bits of each number. In depth K of the recursion we'll look at the Kth least significant bit.

      In depth 0 we put all numbers with the first bit 0 at the left part, and the remaining on the right. Any arithmetic progression cannot contain 2 elements from both halves, so we recursively solve for the left part and right part, and now look at the second bit, and so on.

      For each layer of recursion we do time and there are layers.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I also thought that looking at second bit, third bit and so on, depending on layer will work, but I don't think it is correct.

        It shouldn't work, because we want the equation a0 + 2 * d ≠ a2 to hold, which only forces the 0-th bit to be distinct.

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

          On some layer K, we know that for all elements there, all the bits before the Kth one are equal, which forces the difference of an AP there to have all bits before the Kth be 0, which means all previous bits have no effect on the Kth one so this is exactly a subproblem.

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

          okay , so for simplicity we assume N = 2m - 1 or N = 2m , if not we can always find the smallest such number  ≥ N and remove the larger elements before printing.
          lets say N = 15 , then middle element = 8 , all elements on left are 7, 9,  5, 11,  3, 13,  1, 15 , the ones on right are 8,  6, 10,  4, 12,  2, 14 its clear that the difference between consecutive elements is 2 so we can instead treat them by reducing to 1..N / 2.
          This reduced the problem from 15 to 7 and 8 , 7 can be solved similarly , for 8 , we again pick 5 as middle element , push 1, 3, 5, 7 on left and 2, 4, 6, 8 on right and solve again. [ We basically just need to maintain that after splitting , differences is 2]

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

          actually the 2n - 1 case is useless and we can go straight to the next power of 2 and get the usual ordering we do before FFT.

          → Reply