ko_osaga's blog

GP of Romania
By ko_osaga, history, 7 years ago, In English

I never thought Kuhn-Munkres would strike me that hard...

How to solve F L? And what was intended for H?

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

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

How to A, C, D, J? :D

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

    J: For each edge suppose that there are a persons on the on side and 2m-a persons on the others side. Then it will be used in min(a, 2m-a) pathes. So, iterate over edges, and over a and multiply C(2m, i)·vi·(n - v)(2m - i)·edge·min(i, 2m - i) where v is the number of vertices on one side of the edge

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

    C: Let x_0 = 0, and x_i is how much down will i-th component drop. Then for each two consecutive # is one column we get equation of form xj <  = xi + C (and for the lowest one xi <  = x0 + C. This inequalities can be solved using Dijkstra.

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

      Could you please share your implementation with Dijkstra? Mine got TL, so I had to remove log n factor by using n vectors instead of set (since the distances are at most n).

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

        We also had no log n factor via n doubly linked lists.

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

        code: https://ideone.com/4URZio
        author: zemen
        Works in 1.279s on 5th test, all other testcases < 0.6s

        Seems to be usual dijkstra on priority queue

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Actually I used SPFA so I had nm (maybe n+m) factor... My modeling had edge with C<0. I couldn't figure out how to fix it but just wrote that

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

        https://pastebin.com/qSZ9aE0J
        Dijkstra with std::set, works 1.24 on 5th test.

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

          Thanks! The reason for my TL was that I inserted all vertices into std::set at the beginning (obviously not too clever). Now that I only insert the starting vertex first, it passes in 1.2 seconds as well.

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

      The author's solution is similar to this, but a bit more simplified. Instead of having a vertex for each component, there is one for each cell in the matrix. Now all edges in this graph have either C = 0 or C = 1 allowing for a very easy O(N * M) implementation (and creating the graph is easier to implement too).

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

    D: somewhat straight-forward case-analysis (the problem is to write this cough code).

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

    A: That was solved without me, but solution is hungarian algo on matrix  - A

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

I want to participate in next GPs, but I don't know how, can someone help me ?

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +25 Vote: I do not like it

L:

First, find the xor of all numbers. If it's 0, it's a draw. If not, find its highest 1 bit, and then we only need to look at this bit, so we reduced our problem to n zeroes and ones, with odd number of ones. The player to grab an odd number of ones wins.

Now, if n is even, the first player wins, because he can guarantee all black or all white squares in an alternating coloring, and one of those must have an odd number of ones.

When n is odd, if the first player grabs a zero, he loses by the above argument. In the following game, the first player must always grab the same number as the second player, otherwise he will again lose by the above argument. So his only chance is to always repeat the move of the second player, an only in case half of all ones after the first move is even.

Now, when can he always match the moves of the second player? I claim that when what remains after his first move looks like this: ABA', where A' is a reverse of A, an in B all numbers come in pairs (i.e. 001111001100).

The proof of this last statement is not yet very formal in my head.

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

    After move of the first player length of sequence is even. Seems that it could be reduced to empty string by operations of removing two neighboring equal numbers.

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

      But not every string that is reducible in this manner is winning for the first player. For example, consider

      100100100001

      Here the second player wins because he keeps taking from the left end, and obtains either 100100 or 10010000, at which point he wins by taking 1 and first player can not repeat.

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

where can i find these problems?

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

What about B, I and K?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it +5 Vote: I do not like it

    K: Suppose we have odd number of "corners" then base figure is

    112
102
332

    otherwise base figure is

    11222  
10004  
33344

    now, we can add to either top or bottom side pairs of corners:

    221x  
2x11 (to top, symmetrical to bottom)

    then, rest of triminos, dominos, and cells (in that order), adding each figure to the currently shorter side. It may be proven that it'll always work.

    code is ugly but actually easy to write

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

    B (by ilyakor):

    Let's do backtracking column by column. For each column, if we choose some number, then we also immediately determine the number for all rows that have some other number in this column. And that, in turn allows us to determine the values for some other columns on the right of the currently processed one. Finally, if we choose a number that is not present in this column, then we determine all rows, and can stop backtracking and take k to the power of the number of yet undetermined columns.

    More precisely, we remember the following during backtracking: we have chosen the numbers for the first x columns and some subset of rows, and for some of the remaining columns the already processed rows require a specific color.

    If we start off by having n rows, then we branch at the first column into several recursive calls with n1, n2, ... rows such that n1+n2+...=n. So if inner processing inside one recursive call takes O(nm) where m is the number of remaining columns, then the overall running time is given by f(n,m)=O(nm)+f(n1,m-1)+f(n2,m-1)+..., which means f(n,m)=O(nmm).

    Doing the internal processing in O(nm) is not entirely straightforward as naively we would iterate over the entire matrix for every candidate color, but can be done using some standard counting tricks taking advantage of the fact that different colors have a big common part of processing.

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

    I: Dynamic programming where states are pairs (j, k), where i is the number of strongly connected components and k is the number of "free" edges. A transition either adds a free edge, or uses the new edge along with some free edges to merge strongly connected components with a cycle.

    After we reach edges, it is impossible to keep n strongly connected components, with similar conditions for smaller counts of connected components. We need to remove all states with (where i is the total number of edges).

    This DP has complexity O(n6), and can be optimized to O(n4).

    code

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

D is almost the same as this (decimal instead of binary), but test data for D is stronger than this past problem. You might not get AC only by copy-pasting and changing some "10"s into "2"s.

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

F: consider a range [L, R] of values in the first array so that everything outside it will be removed in the final answer. Clearly, the number in the range must form an increasing subsequence.

Let x and y be the numbers immediately below and above [L, R] in the first array respectively. The play will then proceed as follows: first erase all the numbers at least y, then erase all numbers at most x (or vice versa). The optimal strategy is to insert numbers from [x, y] as long as possible, then (assuming we are currently trying to erase larger numbers) insert smaller elements, effectively increasing the number of smaller elements to be deleted later. We can predict the number of moves required for each phase in O(1) just by the number of elements inside the range and to either side of it.

Finally, only ranges that are non-extendable to either side should be considered, which makes for an , or even an O(n) solution.

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

How do you guys find these GPs ? I don't see them on any calendars nor any announcement blog. Or are they private contests ?

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

How to solve E?

→ Reply