dragoon's blog

GP of Beijing 2019-2020
By dragoon, history, 5 years ago, In English

Let's discuss the solutions.

How to solve B?

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

»
5 years ago, # |
  Vote: I like it +44 Vote: I do not like it

How to solve H?

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

    The key idea is to solve the problem without the strings "A" and then iterate over the number of them to glue to words ending with 'S'.

    And that subproblem is just some tedious case-handling:

    "..SA" + "D..": connect min($$$cnt_{SA}$$$, $$$cnt_{D}$$$) words to each other and subtract 1 if the set of indices of words ending with "SA" is equal to the set of indices of words starting with "D" (they got connected into a cycle). Same for "..S" + "AD..".

    And the only case left is when all words got connected into one cycle. Subtract 1 more if all possible connections are made, union of sets "D.." and "AD.." is equal to union of sets "..S" and "..SA" and there were no subtractions in previous connections.

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

    Copy-paste from recent JAG contest.

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

How to solve E?

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

    Let's emulate the specified in the statements algorithm, but instead of removing overlapped boxes on step 2, we will just skip this step and then for every processed box we will first check whether it was removed previously or not. If it "was removed" just skip it, otherwise select it.

    So we need to maintain some structure that allows adding new selected boxes and checking whether the current box overlaps enough with previously added boxes.

    Let's divide all the plane into square cells with side equal to $$$S$$$ and store these cells in the unordered map, i.e. for each non-empty cell we will store a vector of selected boxes inside this cell. Then to check if current box is overlapped with some other, we just need to go over 9 neighboring cells and calculate IOU with all boxes in those cells straightforwardly. The key idea is that there will be not too many boxes inside one cell because every pair of selected boxes should have $$$IOU <= threshold$$$.

    It passed in 1.2 out of 10 sec.

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

How to solve K, L?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

We upsolved B like this: lets fix set of vertices. Initially it is only 0 in the set. Than make our moves find minimum digit that is adjacent to vertices of our set. Create new set with vertices that is adjacent to previous set by edges with minimum digit. Clearly this is best way we can go. Just save sets to some map and if your current set is equall to some previous set => you have cycle or if you have 1 in you current set => you have way withot cycles. Of course initially we remove vertices that can't be reached from 1 by reversed edges. By the way I don't know why it is not TL.

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

    I think I can make a case where this TLs :) Create a few loops of zeros with coprime lengths, and add zero edges from 0 to one vertex in each loop, and one edges from one vertex in each loop to 1.

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

Can anyone please link a pdf of the problem-set?

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

Any ideas about F?

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

B: We didn't have time to implement but I think the following should work:

1) Remove all vertices that don't have path to 1(bfs/dfs)
2) Add edge 1->1 by number 0
3) From each vertex choose only edges with minimal digits
4) Sort (in at most n iteration, each iteration O(n log n) or O(n) if counting sort) vertices by distance to 1: First, each vertex is in group by its outgoing digits. Then in each iteration vertex i is less the vertex j iff i was less than j on previous iteration or if they were equal and now min(class[outgoing[i]]) < min(class[outgoing[j]).
5) Choose path from 0 greedily. You'll get some preperiod and period which you need to convert to A/B

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

    Sounds too complicated

    1. Remove all edges going to vertices having no path to 2.
    2. Maintain the set of vertices you can be at aftet going through $$$k$$$ edges. It's easy to recalculate the set for $$$k+1$$$ in O(V+E), just consider all minimal edges and go through them.
    3. Build the set for $$$k=V+eps$$$, if you notice during the computation that vertex 2 is in your set at some point, restore the path and break.
    4. Otherwise the answer is cyclic. Restore path for any vertex in set with $$$k=V+eps$$$, and find preperiod and period there.
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I didn't understand. What is V+eps?

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

        Number of edges to go through. If you go at least $$$V+1$$$ edges you will surely find the cycle, which is what we want to.

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

      Ok, that's indeed somewhat easier, thanks

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

We tried solving B by keeping a set of vertices and iteratively advance with the lowest digit edge (only considering vertices that reach $$$1$$$). We do this iteration $$$4n$$$ times, and then extrapolate the rational resulting number. However, it gives WA 7. Any ideas why?

Code

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

    Integer overflow at Out function. My solution is the same as you, but I iterated $$$3n+50$$$ times.

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

    I did the same bug, but I fixed it during contest :)

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

How to solve C?

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

    $$$dp[i][j]$$$ — the minimum price to put $$$i$$$ letters and have latest $$$j$$$ letters copied. $$$j = 0$$$ means the last move was to put a single letter.

    From any state $$$dp[i][j]$$$ you can put a single letter and go to $$$dp[i + 1][0]$$$, paste the current copied string into its next occurence and go to $$$dp[nxt[i][j]][j]$$$ (filling the rest of letters by single insertions) or copy the next $$$k$$$ letters from somewhere earlier (if there was such an occurence), paste it immediately and go to $$$dp[i + k][k]$$$.

    $$$nxt$$$ and occurrence checks can obviously be precomputed with z-function.

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

      I think TL on C was absurdly tight. We had simple $$$O(n^2)$$$ DP solution with substring hashes computed with suffix arrays, but it gets TLE verdict (due to cache-friendliness issues).

      Code: https://pastebin.com/JPLWrVyS Lines 147-177 is the actual DP

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

      We got TLE with exactly this approach, could you share your code?

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

How to solve I?

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

    It works for all $$$n$$$. Just build a staircase:

    [(1, 1)]
[(1, 2) (2, 2)]
[(1, 3) (2, 3) (3, 3)]
[(1, 4) (2, 4) (3, 4) (4, 4)]
...

    (i, j) means, you place block of $$$(i, j)$$$, with $$$j$$$ in the opposite side of sight.

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

Unfortunately, H was in recent MW camp, I think that's why it was solved so much.

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

Any fast solution for K? I solved it using small-to-large in 1.973s, I assume it was not intended.

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

    My solution works in 0.879s. I think it was intended O(N log N) with small-to-large.

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

      My small-to-large solution is $$$O(N \log^2{N})$$$. How one can achieve $$$O(N \log{N})$$$?

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

        For every component you can maintain number of numbers such that x and x+1 are in that component, answer for that component is size — that number.

        Question is how to avoid using sets. Well, you can have vectors and then when you are moving x from smaller vector to larger one, first you need to check if x+1 is there. Same for x-1.

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

    We have just LCA + DSU that passes in 1 second. I guess you can make it sub-nlogn but idk if that will be faster :)

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

      Could you please elaborate your solution in detail?

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

        Well, it's just that $$$i$$$ and $$$i + 1$$$ merge their segments at $$$lca(i, i + 1)$$$. With this fact you simply collect all the updates you'll need to do in each vertex and do one dfs. The answer for vertex $$$v$$$ is $$$1 + \sum \limits_{u \in g_v} ans_u$$$ minus the number of updates in $$$v$$$.

        Also I just realized I don't even use dsu here.

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

What about J? Is this test valid?

2
message A { required A name1 = 1;  required string name2 = 100; }
message B { required B name1 = 1;  required string name2 = 101; }
1
A B

At least, there is no such case in testset, but I think I didn't found anything against it in statement. Answer formally is compatible.

Also, what's the reason of giving 6-page statement with about 10% useful information?

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

    We didn't find anything about it, either, so we assumed this stuff can happen (and I just checked that the protobuf compiler consumes this description just fine). I don't know if I'm more relieved or surprised that such a case was not in the testset. :P

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

What's a reliable way to ask for clarifications during the OpenCups? We asked a couple of clarifying questions through the Yandex system within 2h of the start of the contest and we never got a response. :(

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

    I thought that asking Snark in Telegram was most reliable, but that also didn't work today.

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

BTW are the authors of this contest known? I saw at least three problems that made me interested by the context :)

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

How to solve G?

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

    Let $$$v_1, v_2, \ldots, v_k$$$ be the sons of the root. Let $$$l_i$$$ be the depth of the deepest taken vertex in the subtree of $$$v_i$$$ (possibly $$$l_i = 0$$$). It turns out that the second player wins if and only if $$$max(l_1, \ldots, l_k) = max_2(l_1, \ldots, l_k)$$$. It can be proved using the fact that we can remove all vertices which are ends of some diameter (at least I thought this proof is correct during the contest). Implementation is pretty standard, complexity is $$$O(n \cdot log(n))$$$.

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

      Could you clarify the implementation? In my code I had to divide by numbers that could be zero modulo 10**9+7, but luckily there were no such testcases.

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

        I do it too, but I think it`s easy not to do it. When I maintain these arrays $$$arr_{v, j}$$$ — how many ways to choose in the subtree of $$$v$$$ vertices with the deepest one in the depth $$$j$$$, I need to multiply some suffix by $$$x$$$, so I divide some prefix by $$$x$$$, but I can just not to do it if $$$x = 0$$$, adding some parameter "what suffix is turned to $$$0$$$", recalculating this after every action with the array.

        When I calculate the answer, I can do it too, storing the number of ways in the subtrees which can`t provide another depth $$$d$$$ separately and using prefix sums for others.

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

          Right, that should work!

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

Can someone explain how to solve problem L?

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

    Code brute -> notice the pattern.

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

    Print 2 when n or m is 1, else 2n + 2m — 4.

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

      can you explain whay answer is 8 + 2 * (a — 3 + b -3 ) for a > 2 and b > 2

      → Reply