Martynas's blog

By Martynas, history, 5 months ago, In English,

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.

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

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

    Uh, sorry for the OBOE. At least the timeanddate.com link was correct. Thanks!

»
5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
5 months ago, # |
Rev. 5   Vote: I like it +3 Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Solutions:

A
B
C
»
5 months ago, # |
Rev. 6   Vote: I like it +8 Vote: I do not like it

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 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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 :)

»
6 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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