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

Contest link: https://cses.fi/359/list/

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.

Do we have to translate the problem statements from Finish or will an English version also be made available?

The problems are available in English in this open contest

Thanks, that'd be great :)

If I have to roughly translate it to Codeforces language, which division will it be — 1 or 2?

Most problems are div2 level, but there are also some harder problems.

You can now start the contest!

The scoring is IOI based right ?

Yes

Will we able to submit solutions and receive feedback even after the given time frame? (not virtual participation. Just individually trying problems)

Yes, you can upsolve problems later

great. Thank you

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?

You will get a full window

Can we discuss the problems now ?

Not yet, the contest is still running for some people. You can discuss them after 20:00 UTC.

Contest results: https://cses.fi/359/scores/

Thank you for participation! You can discuss the problems now.

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

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

How does divide and conquer (DP) work for this problem?

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.

I solved E using allien's trick, but i feel like should be easier approach. Is allien's trick intended for this problem?

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:

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.

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.

here

Thanks! :)

How to solve D for full points?

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)

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

Can you prove or give some intuition on why this works?

It's just a bit of casework.

evendistance from the root:odddistance from the root, the children of this vertex $$$V$$$ will have already been processed.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)

How to do F?

Some intended solution ideas:

Subtask 1Subtask 2Subtask 3: ??? case handling

Crucial observationSubtasks 4 & 5I 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.

This got a little hard to read. Is there a way to put multiple paragraphs in spoilers?

Why problem C solution is just to check if the inversion count is even?

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.

Will be official editorial?

Can someone share their approach for problem E ?

can anyone plz. explain how to approach problem B.

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.