### Martynas's blog

By Martynas, history, 5 months ago, ,

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:

• +46

 » 5 months ago, # |   +3 The dates should be 30 and 31 (not 29 and 30).
•  » » 5 months ago, # ^ |   0 Uh, sorry for the OBOE. At least the timeanddate.com link was correct. Thanks!
 » 5 months ago, # |   +11 It doesn't seem like I can register, there's just a login form.
•  » » 5 months ago, # ^ |   +8 Yes, I was trying to register too ...
•  » » 5 months ago, # ^ |   +8 Apparently there's a delay, the registration should start soon at https://cms.lmio.lt/vyr-eng/
•  » » 5 months ago, # ^ |   +8 Now it's possible to register!
•  » » 5 months ago, # ^ |   0 You can register
 » 5 months ago, # | ← Rev. 5 →   +3 ᅠ
 » 5 months ago, # |   +30 Solutions: AWe must find for each star the time frame in which it's inside the circle. Then we sort those to find the time in which we could see the most stars.To find the intersections, if they exist, I changed every star to a function and found intersection points with the circle by a formula on paper. Because of imprecision, after I find the intersection points and the times, I just iterate on the close integers (+- 3) to find the exact time frame. BWe will never want to change a height below 0 anyway (exactly 0 is at least as good), so we can ignore this restriction.Let's subtract from position $1 \le i \le n$ the value $i * M$. Now the sequence of heights we iterate over is non-increasing. When we adjust the height of some pole, it's best to change it to the height of the one before it. We can view it as ignoring all the poles which we picked to change the height of. Since we're looking to minimize the number of ignored poles, we're looking to maximize the number of unchanged poles, which form a non-increasing subsequence. So, the task is to find the longest non-increasing subsequence of the array (and make sure it begins with a 0 before the start of the array). CLet's define $C_i = A_i - B_i$, as the number of extra fertilizers position $i$ has. Interestingly, we do not care whether our operations for some solution make some position have a negative amount of fertilizers; we will always be able to reorder the operations to satisfy this restriction. So we can ignore it.Also, we can regard every operation as taking 1 fertilizer from position $i$ and moving it to position $i-1$ or $i+1$, with the cost of 1.Let's transform $C$ to its prefix sum. Our operations become to change a value in the array from $x$ to $x+1, x-1$ with the cost of 1 = changing $x$ to $y$ with the cost of $|x - y|$. We can only do this operation for all indicies except the last (which is the sum of all $C$), and the goal is for the array to be nondecreasing, and starting from (at least) 0. So first, for every value that is less than 0 or more than the sum of the array, adjust it to fit. Notice that this already solves subtask 1. We can now ignore the last value and the restriction with beginning with 0.The following part is the complex one (making the array sorted). Our process will be to iterate on values from small to large, and in every iteration we have a set of "changeable" values — values which will be at least the current ones in the answer sequence, and we keep incrementing them until it's not beneficial. There will also be a group of values which we already fixed — they will also form a prefix since we fix values from small to large. All values which we have not iterated on are considered unknowns (but we know they are larger than what we have now). Also notice that changeable values will always be the same (they become different when we fix some of them).Suppose the case in which we have one changeable value, and two unknowns to its left. If we decide to fix this value now, then both unknowns to the left must become this value. Observe that since our value is the smallest between those 3, it will be at least as good to increment our changeable value until it's equal to the smaller between the other two (in other words, we decide to keep it changeable). On the contrary, if we had 2 changeables and 1 unknown to their left, then it's better to decrease that unknown towards them instead of increasing them. Also, this makes us fix those 3 positions.Let's formulate this; imagine the array, in which every fixed value (in the prefix) implies a 0 in its position. Every changeable value is a +1, and every unknown is a -1. If there exists a prefix, whose sum is positive, then we should fix all the values in this prefix. We can implement this array with a lazy segment tree — when we change a value between $-1, 0, 1$, we update a suffix by adding some value to it. Then a query is the maximum value and its position.Fixing values can be done by bruteforce, since overall we fix $n$ values.
•  » » 9 days ago, # ^ |   +8 C can be done with a priority queue (submission). Some other problems which can be solved in a similar fashion can be found here:https://github.com/bqi343/USACO/blob/master/Implementations/06%20-%20DP%20(3)/README.md#6Is this trick well-known?
 » 5 months ago, # | ← 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)Let $X_i$ the number of placements that can be done by $i$ ways. First, calculate the number of unordered pairs of ("??ab", "ab??"), ("?a?b", "a?b?") which two are different. It can be calculated by brute-forcing a and b, and multiply number of ways for two strings. Let this number of ways $C_1$. Second, calculate the number of unordered pairs of ("abcd", "cdab"), ("abcd", "badc"), ("abb?", "?aab"), ("?bba", "baa?"), ("ab?a", "b?ab"), ("a?ba", "ba?b") which two are different. We can brute-force them. Let this total number of ways $C_2$. Third, calculate the number of unordered pairs of ("abba", "baab") which two are different. We can also brute-force them. Let this number of ways $C_4$. Then, we can say that $(X_1, X_2, X_3, X_4) = (C_1, C_2 \div 2, C_3 \div 2 \times 4, C_4 \div 2)$. Finally we can print $X_1 - X_2 + X_3 - X_4$ by inclusion-exclusion principle. Source Code (C++) Problem B (Coins, 77.1 points)Let $seq_i$ the number of zeros in $i$-th row. We want to optimize this sequence with hill-climbing algorithm, but since this problem is required to process "biased" (not random) image data, I thought that we should do good initial $seq$ for it. So, how to produce a good initial $seq$? I've thought the following ad-hoc approach. First, don't think about sum of silver/copper coins. Let's just think about the "cost", which is defined by silver -> copper: cost x, copper -> silver: cost 1-x, where $x$ is a real value in $[0, 1]$. Then, we can easily compute the minimum cost solution by DP in $O(n^2)$. The number of silver coins in minimum cost solution will be an increasing function of $x$. Therefore, we can binary-search $x$ that the number of silver/copper coins will be nearest to true value. But it is not perfect because there is some error in number of silver/copper coins. We adjust the number by random greedy approach. Then, we got 50.2 points, with getting better than perfect score in testcase 5. And then, we can do hill-climbing because the solution is near enough to the optimal. The neighborhood in hill-climbing is: do [1, 14] process of seq[i]++, seq[j]-- for random valid (i, j). If the score improves or stays, we will update the solution. If the score deteriorates by one, we will update the solution by $1/2$ probability. Otherwise, we will not update the solution. Then, finally, we could get 77.1 points by getting better than perfect score in testcase 1, 3, 4, 5 and 7! Source Code (C++) Problem C (Tax Evasion)If the coin is in depth $d$, this coin can climb up to depth $\lfloor (d-1)/2 \rfloor$, so the range which a coin can move (and finally stop) will form a subtree where the tree is rooted from vertex $0$. So, if we do "Euler Tour", we can reduce this problem into interval problem — the range where the coin finally stops will be like $l_i \leq x \leq r_i$. Let's think about binary-searching the answer. If the answer is $a$, all coins must stop at the different spot which the depth is at least $a-1$. We can judge if the answer is $a$ or more, by greedy algorithm, with priority queue, and it takes $O(n \log n)$ time complexity. Therefore, we can solve the problem by $O(n \log^2 n)$ time complexity. Source Code (C++)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 →   +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 months ago, # ^ |   +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 months ago, # ^ |   +8 By the way, our solutions combined would have approximately score of 98. What was your approach?
•  » » » 5 months ago, # ^ |   +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 :)
 » 9 days ago, # |   +8 You can submit all problems here: https://oj.uz/problems/source/431