rng_58's blog

AtCoder Grand Contest 014
By rng_58, history, 8 years ago, In English

AtCoder Grand Contest 014 will be held on Saturday (time). The writer is yutaka1999.

Contest Link

Contest Announcement

The point values are 300 — 500 — 700 — 900 — 1400 — 2400. Note that the contest duration is unusual (130 minutes).

Let's discuss problems after the contest.

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

Comments Comments (8)
| Write comment?
»
8 years ago, # |
  Vote: I like it +30 Vote: I do not like it

When I click on editorial I get 404. Is it supposed to be like that right after contest and we should wait a while or is this simply a bug?

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

    I had some trouble uploading it, now it is uploaded.

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

Problem E: An easy solution but heavy-coding :).

Find an edge with only one path (c[i], d[i]) pass through (if not answer is NO), remove it and do again.

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

    I know this solution but idk how to do it fast.

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

      I tried to do it fast, but got wrong answer.(I don't know if I implemented it wrongly or thought it wrongly.) Here is my way: we can use heavy-light decomposition, and for each edge in the tree, we record the number of paths that go through it on the vertex which has a larger depth. We also maintained two sets recording which paths are left by storing the dfs-number. When we find an edge with only one path passes through, we can find the path in the sets, and erase it.(Till now, I still couldn't find where is wrong in my programme.)

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

    I implemented this solution.

    Do heavy light decomposition and use segment tree. Let

    Unable to parse markup [type=CF_TEX]

    denote the number of red paths which pass through edge e. For every segment tree node we store a set of all red paths which pass through all the edges the node represents, and also the minimum

    Unable to parse markup [type=CF_TEX]

    among those. Also, we need some propagation to be able to update those minimums.

    Now repeat this process n-1 times:

    Find the edge e with minimum

    Unable to parse markup [type=CF_TEX]

    . If this value is different than one, the answer is NO. Otherwise, remove the only unused red path which contains it from the segment tree, and set

    Unable to parse markup [type=CF_TEX]

    to avoid it ever being the minimal edge again. The complexity is

    Unable to parse markup [type=CF_TEX]

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

Here is what I did in problem D.

  1. Notice that if a vertex has at least 2 adjacent leaves, first wins. Decide that this is better than anything I can prove in 5 minutes so it is worth submitting. This solution passes 30 tests out of 36.
  2. Notice that if a non-leaf vertex has an adjacent leaf and white paints this vertex in the first move, black must paint the leaf. So if every neighbour of a vertex has an adjacent leaf, first wins. This looks like it might be generalized, but I'm not sure how so just submit it for now. This passes 34 tests out of 36.
  3. Now I can either properly generalize the idea by greedily cutting of pairs of vertices bottom-up or guess that there's at most 2 special cases left that I need to handle. It turns out that in the latter case checking the parity of the number of vertices was enough. However, I stopped here, tried to implement the greedy cutting and failed to do it in time, but that's beside the point.

The point being, in AtCoder contests you know the number of test cases that your solution fails at. While I do not claim that this is necessarily a bad thing, it offers some possibilities:

  • Assume you have a slow solution that is either correct but difficult in implementation, or you just believe that it is correct but do not have a proof. Assume also that you know how to speed it up, but it's difficult and requires data structures (or, say, integer FFT). Try submitting your slow solution! The only verdicts you should get are AC and TLE. If it happens to be so, you may now speed it up. This idea also may work in ACM ICPC style contests (unless the authors put large tests before the tricky ones) and in testing solutions of large inputs in GCJ.

  • If you know that your solution's speed is suboptimal but you time out only once or twice, try non-asymptotic optimizations first.

  • If your floating-point geometry problem fails only a couple of tests, try tweaking the epsilon. Note that this strategy is usually a bad one if the number of tests is unknown.

  • If you have several greedy ideas, try combining them and see how many tests you pass.

UPD. Here is an example of how to use this to your advantage: http://codeforces.me/blog/entry/50457#comment-346020

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

    You're very close to the solution. What I did was store a priority queue of leaves sorted in decreasing order of height, and store the degree of each vertex. When we process a leaf, if it is the root, the graph has no edges and P1 wins. If the parent has degree > 2, P1 wins. If the parent is not the root and it has degree 2, then we delete the leaf and its parent and update the degree of parent of parent of leaf accordingly. If the parent of parent becomes a leaf, push it into the priority queue. Finally, if the parent of the leaf is the root, then P2 wins iff the root has exactly one child.

    → Reply