pllk's blog

Datatähti Open 2021 (Finnish Olympiad in Informatics)
By pllk, history, 4 years ago, In English

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.

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

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

You can now start the contest!

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The scoring is IOI based right ?

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can we discuss the problems now ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

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

→ Reply
»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve D for full points?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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)

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        It's just a bit of casework.

        • If a current vertex that has been printed is at an even distance from the root:
        1. 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].
        2. 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.
        1. 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].
        2. 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].
        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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)

        → Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

How to do F?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 7   Vote: I like it +54 Vote: I do not like it

    Some intended solution ideas:

    Subtask 1

    Subtask 2

    Subtask 3: ??? case handling

    Crucial observation

    Subtasks 4 & 5

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Will be official editorial?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share their approach for problem E ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone plz. explain how to approach problem B.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?
    → Reply