### pllk's blog

By pllk, history, 8 months ago,

Datatähti Open 2021 is an open online contest based on the final round of the Finnish Olympiad in Informatics (Datatähti) 2021.

The duration of the contest is 4 hours, and you can start the contest at any time between 29 January 2021, 16:00 (UTC) and 31 January 2021, 16:00 (UTC).

The contest consists of six problems (from easy to difficult), there will be subtasks and full feedback, and the scoreboard will be published after the contest. You can discuss the problems here after the contest.

• +88

 » 8 months ago, # |   +16 Do we have to translate the problem statements from Finish or will an English version also be made available?
•  » » 8 months ago, # ^ |   +22 The problems are available in English in this open contest
•  » » » 8 months ago, # ^ |   +3 Thanks, that'd be great :)
 » 8 months ago, # |   +9 If I have to roughly translate it to Codeforces language, which division will it be — 1 or 2?
•  » » 8 months ago, # ^ |   +11 Most problems are div2 level, but there are also some harder problems.
 » 8 months ago, # |   +14 You can now start the contest!
 » 8 months ago, # |   +11 The scoring is IOI based right ?
•  » » 8 months ago, # ^ |   +11 Yes
 » 8 months ago, # |   +3 Will we able to submit solutions and receive feedback even after the given time frame? (not virtual participation. Just individually trying problems)
•  » » 8 months ago, # ^ |   +3 Yes, you can upsolve problems later
•  » » » 8 months ago, # ^ |   +3 great. Thank you
 » 8 months ago, # |   0 If I start the contest at around 14:30 UTC on 31 January, will I get the full window of 4 hours or just the partial window till 16:00 UTC?
•  » » 8 months ago, # ^ |   0 You will get a full window
 » 8 months ago, # |   +5 Can we discuss the problems now ?
•  » » 8 months ago, # ^ |   +5 Not yet, the contest is still running for some people. You can discuss them after 20:00 UTC.
 » 8 months ago, # |   +18 Contest results: https://cses.fi/359/scores/Thank you for participation! You can discuss the problems now.
 » 8 months ago, # |   +26 Problem 5:Carbon Copy: http://apio-olympiad.org/2007/apio-en.pdf (Problem 2)"Don't copy my homework exactly": https://oj.uz/problem/view/JOI18_candies
•  » » 8 months ago, # ^ |   0 Also this!Or you can be smart and [loosen constraints]https://atcoder.jp/contests/abc162/tasks/abc162_f).Actually I knew about this problem & knew that there is a stupid greedy but I hate greedy so I asserted the fact that the function is convex. And came up with 2 solutions d&c and alien's trick. I later proved both convexity and greedy by modeling the problem as mcf (hopefully correctly).
•  » » » 8 months ago, # ^ |   +8 How does divide and conquer (DP) work for this problem?
•  » » » » 8 months ago, # ^ |   +15 Not "d&c dp". Just d&c to solve for all k. solve for l, mid and mid+1,r also keep flags indicating whether you took border elemenets. Then merging is a bunch of min convolutions of convex arrays which can be done using greedy for convex arrays.
 » 8 months ago, # |   0 I solved E using allien's trick, but i feel like should be easier approach. Is allien's trick intended for this problem?
•  » » 8 months ago, # ^ |   +46 My solution:Assume $x_1 \leq x_2 \leq \dots \leq x_n$. Let $d_{i} = x_{i+1} - x_{i}$ for $i < n$.We want to take $k$ values $d_i$ with minimum total sum. We cannot take adjacent values.Look at the $i$ with minimum $d_{i}$. Given any solution that doesn't take both $d_{i-1}$ and $d_{i+1}$, we can add $d_{i}$ to the solution in place of $d_{i-1}, d_{i+1}$ or if neither exists, any other pair, and not increase its cost.Thus, we may assume that if we do not take $d_{i}$, we take both $d_{i-1}$ and $d_{i+1}$.Define a new sequence $d'$ of length $n-3$ as follows: \begin{align} d'_{j} = d_{j} &\text{ for } j < i-1\\ d'_{j} = d_{j} + d_{j+2} - d_{j+1} &\text{ for } j = i-1\\ d'_{j} = d_{j+2} &\text{ for } i \leq j \leq n-3\\ \end{align}In this sequence, taking $d'_{i-1}$ means taking both $d_{i-1}$ and $d_{i+1}$ in the original sequence. Not taking $d'_{i-1}$ means taking $d_{i}$.Thus, solving this shorter sequence for $k' = k - 1$ and outputting its minimum cost plus $d_{i}$ gives the answer.
•  » » 8 months ago, # ^ |   0 Can you share your solution?I tried to implement a solution with that trick, but I can't get it to work when there's no way to choose the incentive such that the number of chosen pairs becomes equal to K.
•  » » » 8 months ago, # ^ |   +5
•  » » » » 8 months ago, # ^ |   0 Thanks! :)
 » 8 months ago, # |   +8 How to solve D for full points?
•  » » 8 months ago, # ^ |   +5 I didn't really prove it, but if you start from a root (say it's vertex 1) you can find such an order by always going as far down as possible in the tree (when you are at a given vertex, bfs the reachable vertices, i.e. not yet used and with a distance leq to 3, and choose the one which is farthest from root)
•  » » 8 months ago, # ^ | ← Rev. 2 →   +10 I used a trick similar to that of IOI20 Stations. Perform a DFS from vertex 1. For all vertexes at an even distance from 1, print them out before processing their edges. For all vertexes at an odd distance from 1, print them out after processing all of their edges.My code
•  » » » 8 months ago, # ^ |   0 Can you prove or give some intuition on why this works?
•  » » » » 8 months ago, # ^ |   +6 It's just a bit of casework. If a current vertex that has been printed is at an even distance from the root: If this vertex $V$ has children, then the next printed vertex will be either the child of a child of $V$ (distance 2, even vertex), or a child of $V$ (distance 1, odd vertex) [this will happen if the child of $V$ has no children of its own]. Otherwise, the next printed vertex will be another child of the parent of $V$ (distance 2, even vertex), or the parent of $V$ (distance 1, odd vertex) [if all of its children have already been processed]. If a current vertex that has been printed is at an odd distance from the root, the children of this vertex $V$ will have already been processed. If the parent of $V$ still has other children to process, the next printed vertex will be a grandchild (child's child) of the parent of $V$ (distance 3, even vertex), or another child of the parent of $V$ (distance 2, odd vertex) [if it has no children of its own]. Otherwise, the next printed vertex will be a child of the grandparent of $V$ (distance 3, even vertex), or the grandparent of $V$ itself (distance 2, odd vertex) [if the grandparent of $V$ has no children of its own].
•  » » » » 8 months ago, # ^ |   +5 Each node is visited exactly once, so it remains to be proved that the distance is at most 3. When you visit a node with an even distance, the next node (if there are any) will be its grandchild. The last node after finishing that subtree is a child, then after leaving that node a brother or the parent is visited. (note that the parent was bot printed yet because odd distance so it is guaranteed to be free)When the distance is odd, either the parent or a brother was the last printed node. The next printed node after visiting the current node is a child; when there are no more children, the node itself is printed, then a brother (if any) or the grandparent is visited.(I am worried this is kind of a mess, you should probably simulate it on paper to really understand it)
 » 8 months ago, # |   +27 How to do F?
•  » » 8 months ago, # ^ | ← Rev. 7 →   +54 Some intended solution ideas:Subtask 1 Observe that only the order of where the horizontal segments end up vertically is significant. Therefore it is enough to test all combinations of lengths in $[1, 7]$, or all permutations. Subtask 2 Building on the previous subtask, you may notice that the conditions for a valid permutation are quite simple. Directions of vertical segments can be encoded as "$x$ must be below $y$" or the other way around. — Making sure that a horizontal segment $z$ does not intersect with some vertical segment between $x$ and $y$ boils down to "$z$ must not be between $x$ and $y$". — Collect all these conditions, and do a bitmask DP. The second kind of condition can be checked by preventing $z$ from being chosen if one of $x,y$ has already been chosen in the mask, but not both. Subtask 3: ??? case handlingCrucial observation A triplet of horizontal segments $x, y, z$, where the the vertical segments in between them go in the same direction, can always be chosen to be next to each other in the permutation under certain conditions. This effectively means that these three segments can be combined to act as one. — Let $L[i]$ represent the x-coordinate of the leftmost point in the horizontal segment $i$, and similarly $R[i]$ of the rightmost point. — The conditions are $L[x] < L[z]$ and $R[z] > R[x]$. This simply means that other adjacent vertical segments can go in either direction without intersecting with $y$. — Proof that these segments can be combined: (a nice visual intuition for it is shown in the article linked below, p. 10) — Consider any valid permutation of horizontal segments. Assume the directions of the vertical segments in between is up, so $x < y < z$, and that $x$ goes left-to-right. Between $x$ and $z$, the permutation might look like $[x, g_1, \dots g_m, y, h_1, \dots, h_k, z]$, where $g_i$ and $h_i$ represent other horizontal segments in between. — Replacing this part of the permutation with $[h_1, \dots, h_k, x, y, z, g_1, \dots, g_m]$ still leaves the solution valid, and the three segments are next to each other as wanted. — The solution remains valid because: — First, no vertical segment changes direction. $x, y, z$ remain in the same order. The vertical segment before $x$ cannot be connected to any $h_i$ because of the vertical segment between $y$ and $z$. However, if it happens to be connected to some $g_i$, the relative order between $x$ and $g_i$ stays the same. The same reasoning applies to the vertical segment after $z$. — Second, no new intersections occur. This is because the horizontal segments in between are limited in length. More specifically, the horizontal segments in between are bounded by $R[g_i] < R[x]$ and $L[h_i] > L[z]$, which when taking the condition into account, mean that $R[g_i] < R[z]$ and $L[h_i] > L[x]$. This guarantees they will not intersect with the vertical segments connected to $x$ or $z$. Subtasks 4 & 5 One way of turning the observation to a solution is to maintain a stack of horizontal segments (which may be original, or consist of multiple original segments combined together) with the criterion that the segments in the stack have non-increasing length (from bottom to top). — The order of the stack is not necessarily related to the final order, as the direction may change at any point, forming a spiral for example. — If the next horizontal segment being added to the stack is shorter than the previous one, simply add it on top of the stack, and the criterion is upheld. — If it is longer, we may either combine the new segment and the top two (or one if there is no more in the stack) segments together according to the observation, or conclude that there is no solution. This depends on whether the vertical segment before the horizontal segment being added goes in the same direction with the previous one or not. The new segment is replaced with this combined segment, and the check should be repeated again until the criterion is satisfied. — Equal lengths require additional special handling, and the observation can be extended for equal lengths too, assuming vertical segments go outwards. If the vertical direction remains the same as was previously, then the new equal length horizontal segment can be placed on top of the stack. Otherwise there is no solution. — To output the final answer, you can maintain linked lists of the original segments contained in each element of the stack, and determine their relative orders based on vertical segment directions. — Implementing this correctly is not exactly straightforward, so the 4th subtask admits a less optimal implementation, but I assume it still requires making the observation. I got the idea from the problem of folding a "1-dimensional" paper with predetermined crease points, and directions in which the creases should fold. This is equivalent to the final version of F but seemed much harder to understand as a problem statement.I found a paper (after solving it myself!) which discusses this folding problem among others.
•  » » » 8 months ago, # ^ |   +5 This got a little hard to read. Is there a way to put multiple paragraphs in spoilers?
 » 8 months ago, # |   +15 Why problem C solution is just to check if the inversion count is even?
•  » » 8 months ago, # ^ |   +2 Define $inv = \Sigma^n_{i=1} \frac{|p_i-i|}{2}$. We can see that swapping pairs does not change this value mod 2. Given sufficiently large n (6?) we can always move the smallest value to the front in two moves. By doing so we can reduce this problem to n = 8, and check with brute-force solution that all permutations with even inversion count are good.
 » 8 months ago, # |   +14 Will be official editorial?
 » 8 months ago, # |   0 Can someone share their approach for problem E ?
 » 8 months ago, # |   0 can anyone plz. explain how to approach problem B.
•  » » 8 months ago, # ^ |   0 If the second set has a sum of $a$, we can see that the sum of the three sets is $3a$. Since the sum of the three sets is the sum of all the numbers from $1$ to $n$ we get that the sum of the numbers, $\frac{n(n+1)}{2} = 3a \rightarrow a = \frac{n(n+1)}{6}$. It's easy to see that if $n(n+1)$ is not divisible by $3$, then no possible $a$ exists.Now we will show that if $n(n+1)$ exists, then we can always divide $1\ldots n$ into the three sets. Place $a-1 \mod{n+1}$ into set 1 and $a \mod{n+1}$ in set 2. Now we just have to place numbers that sum up to $\left\lfloor\frac{a-1}{n+1}\right\rfloor*(n+1)$ and $\left\lfloor\frac{a}{n+1}\right\rfloor*(n+1)$ in set 1 and 2 respectively. Any number we don't select in this process will go into set 3.We can form the $n+1$s necessary for set 1 and 2 using the pairs of numbers $i$ and $n+1-i$. Are there enough pairs?Since we only need $\left\lfloor\frac{a-1}{n+1}\right\rfloor + \left\lfloor\frac{a}{n+1}\right\rfloor \leq 2\left\lfloor\frac{a}{n+1}\right\rfloor \leq \frac{n}{3}$ pairs and there are at least $\left\lfloor\frac{n}{2}\right\rfloor - 2$ available, there are enough pairs for any number greater than 11. We can check the numbers from 3 to 11 and see that this algorithm works for them too.