The problems are available in English in this open contest

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

Yes

Yes, you can upsolve problems later

You will get a full window

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

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

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.

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

Some intended solution ideas:

Subtask 3: ??? case handling

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.

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.

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