Блог пользователя Martynas

Автор Martynas, история, 5 лет назад, По-английски

This weekend the best coders from Lithuanian high schools will participate in the final stage of the Lithuanian Olympiad in Informatics. As it was the case in the previous years, you are invited to take part in an online mirror. This IOI-style competition will take place on two days:

See http://online.lmio.lt/ for more information.

Links: online contest, online scoreboard, onsite scoreboard.

  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The dates should be 30 and 31 (not 29 and 30).

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

It doesn't seem like I can register, there's just a login form.

»
5 лет назад, # |
Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Solutions:

A
B
C
»
5 лет назад, # |
Rev. 6   Проголосовать: нравится +8 Проголосовать: не нравится

I only participated in Day 2, got 2nd in Day 2 only results by taking 277.1 points. Here's my solution:

Problem A (Cards)
Problem B (Coins, 77.1 points)
Problem C (Tax Evasion)

I was completely beaten by scanhex because I got zero points on testcase 2 of "Coins". Now I especially want to hear scanhex's solution of "Coins" :)

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Problem C can also be solved with the same idea, but without binary searching. Incrementally add nodes as possible sinks from the bottom up. We iterate over the coins (after pulling them upwards to their subtree root) in decreasing order of depth (this implies the ranges the nodes cover as we keep going cannot be contained by previous ranges, which is used to prove the greedy), and add a node as another necessary sink, while the current coin doesn't have a free sink in its subtree. Once there is a free sink we can remove it (we maintain sinks with a set). $$$\mathcal{O}(n \log n)$$$.

    Also, you can solve the first two tests of B optimally with dp in $$$\mathcal{O}(n^4)$$$.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Well. How does an answer look like? Let's consider black coins. On each horizontal line, they form a prefix of it. Also, these prefixes are not increasing. The output of our program is the number of white coins initially lying on these prefixes.

    This observation can give us a precise solution. Let's calculate dp[i][j][k], which will be minimal number of white coins lying on our prefixes, assuming that we already chose first $$$i+1$$$ of them and the last ($$$i$$$-th) has a length of $$$\geq j$$$, while the sum of lengths of prefixes equals to $$$k$$$. Transitions would be pretty trivial, I won't describe them here for now.

    Of course, this DP has approximately N*N*(N*N/2) states and it is terrible. So, let's store only $$$MAGIC_1$$$ best states for each pair of $$$i$$$ and $$$j$$$. I say that state dp[i][j][k] is better than dp[i][j][l] if $$$k-dp[i][j][k]>l-dp[i][j][l]$$$. Also, it will likely result in storing only states with small $$$k$$$, so let's store only a set of states with disctinct $$$k/MAGIC_2$$$.

    That's pretty much it, constants differ from one test to another, but for me $$$MAGIC_1$$$ is generally equals to $$$70$$$ and $$$MAGIC_2$$$ vary from $$$100$$$ to $$$280$$$.

    With regards to the second test case, it is clear that this solution is particularly good on it, because you can store almost all possible states.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    By the way, our solutions combined would have approximately score of 98. What was your approach?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Now I wrote my solution of "Coins" in comment above.

      I actually struggled to finalize the way to select, "DP + heuristic-like improvement" or "Making good initial solution + improvement by hill-climbing". And I finally selected the latter. Your solution is based on the former and you won against me :)

      Obviously, seeing the scores for each results, your solution is good at some tests, and my solution is good at other tests. I think it's because your solution is based on heuristic-like DP approach and my solution is based on optimization (marathon match)-like approach.

      For example, for testcase 2, your solution is strong because its base solution is designed to be "absolutely optimal". For me, its base solution is not designed to be absolutely optimal. Thus, I got score $$$[577, 585]$$$, not the optimal $$$576$$$, and it varies by submission.

      But my solution is based on optimization-like approach, so, for some testcase, my solution is even better than $$$K_1$$$, which want to get more than 10 points :)

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

You can submit all problems here: https://oj.uz/problems/source/431