chrome's blog

Topcoder Open Algorithm Round 2A
By chrome, history, 9 years ago, translation, In English

Hi!

Tomorrow at 18:00 MSK will be held TCO16 Round 2A.

You can read about TCO16 here.

Also this round has limited number of competitors only 2500. And max number of advancers to the next stage is 40.

Let's discuss problems after contest.

GL && HF!!!

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

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is anyone else with an automatic berth unable to register? I know JoeyWheeler and I got automatic berth and can't register but gongy qualified through round 1C and successfully registered...

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

How to solve A ? Exponential dp on power of 3 s or something?

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

    Cases.

    Basic observations: 1. First of all just look at the exponenets, so we have n pairs of integers, and we can replace two pairs by its max, or min. 2. WLOG our goal is to get (0, 0). // by subtracting goal

    Then we divide points in four categories x-axis, y-axis, center, the rest. Now:

    1. If we have  ≥  2 centers then OK

    2. If we have 1 center and sth on some axis then OK

    3. If we have 1 center and maximum of all points in the rest has x, y > 0 or minimum of all points in the rest has x, y < 0 then OK.

    4. If we have sth positive on both axis, or sth negative on both axis then OK

    5. If all points on x-axis are positive, and all pts on y-axis are negative, and we have soem point in the rest with x < 0 and y > 0 then OK.

    6. If all points on y-axis are positive, and all pts on x-axis are negative, and we have soem point in the rest with y < 0 and x > 0 then OK.

    In other cases Impossible.

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

      Can you or someone else give more intuition of these cases? How do we go from these properties to the existence of a series of moves that guarantee hitting the target?

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

        Suppose that there is no pts in the center. First of all we have to have sth on both axis — which is clear.

        The last move should be min on (+,0) and (0,+) or max on (-,0) and (0,-).

        Suppose that there are points of the form P1 = (0,  + ) and P2 = ( + , 0). Then replace all the rest by one point in any way, say Q = (a, b). Depending on where the Q is we can either remove Q (i.e. min(P1, Q) = P1 or etc.) or project Q on some axis (i.e. min(P1, Q) = (0, b) etc. )
        to obtain two pts of the form (0,  + ) and ( + , 0). And we use min on them.

        In the same way we can treat the case P1 = (0,  - ) and P2 = ( - , 0). (Because there is the symmetry : (x, y) –  > ( - x,  - y) which swaps min and max).

        The remaining case is: all pts on x-axis are (+,0), and all pts on y-axis are (0,-).
        When we have some point of the form (-,+) then we can in first move use max((0,-),(-,+)) = (0,+). And use the previous case. So suppose that we have no pts of the form (-,+). So the upper left quarter of plane is empty. Observe that using moves we cannot get into this quarter so it is impossible to get (0,0) (which lies on the boundary of that quarter).

        Ok. Now the center can be treated as point on x-axis or y-axis. Using the same arguments we can consider the cases with center too.

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

    I had dp/backtrack with memoization, complexity about O(39) but I don't have a proof that it works. There are 9 groups of elements and I assumed that in each group we don't need more than 2 elements. So, each group contains 0, 1 or 2 elements.

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

    Iterate over all subsets of three numbers. First do gcd operation for all numbers not in the subset, then iterate over all operation sequences for the remaining three operations. If you do not find answer this way, then its Impossible.

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

    Here's a proof I had for casework:

    ???
    → Reply