-emli-'s blog

Virtual Contest — Kyrgyzstan (IOI) Qualification Round
By -emli-, history, 5 years ago, In English

Contest Link

Contest Time

The writers are ulandev and Azret.

Registration to site is enough to participate/register to round.

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

Comments Comments (14)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have three questions about it:
1. How many problems are there?
2. Is there partial scoring?
3. Which language the problem statement is written?

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

Are people with star on their names real (onsite) participants?

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

Will be there editorial and will be possible to finish the problems ?

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

What is the expected solution for Pb4? Is it correct to just assume all final numbers are in some small range like $$$[-5, 5]$$$ and then do DP from left to right?

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

How to solve C?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Task C. City of Future

    Author solution: ulandev.

    First, transform the coordinates $$$(x,\ y)$$$ to $$$(x'\ =\ x\ +\ y,\ y'\ = x\ -\ y)$$$. Now, the distance between two points $$$(x_1',\ y_1')$$$ and $$$(x_2',\ y_2')$$$ equals $$$max(|x_1'\ -\ x_2'|, |y_1'\ -\ y_2'|)$$$, which is called Chebyshev Distance, because:

    1. $$$x_1'\ -\ x_2'\ =\ x_1\ +\ y_1\ -\ x_2\ -\ y_2\ =\ (x_1\ -\ x_2)\ +\ (y_1\ -\ y_2)$$$
    2. $$$x_2'\ -\ x_1'\ =\ x_2\ +\ y_2\ -\ x_1\ -\ y_1\ =\ (x_2\ -\ x_1)\ +\ (y_2\ -\ y_1)$$$
    3. $$$y_1'\ -\ y_2'\ =\ x_1\ -\ y_1\ -\ x_2\ +\ y_2\ =\ (x_1\ -\ x_2)\ +\ (y_2\ -\ y_1)$$$
    4. $$$y_2'\ -\ y_1'\ =\ x_2\ -\ y_2\ -\ x_1\ +\ y_1\ =\ (x_2\ -\ x_1)\ +\ (y_1\ -\ y_2)$$$

    It is not hard to see why the maximum of those gives the Manhattan distance between two original points $$$(x_1,\ y_1)$$$ and $$$(x_2,\ y_2)$$$.

    With this trick, the task becomes much easier. You can sort the points by $$$x$$$ and then go by points from left to right, maintaining the $$$[last,\ i]$$$ window such that $$$x_i\ -\ x_{last}\ \leq\ C$$$. Each point $$$k$$$ in this window will be stored in a binary search tree as a pair $$$(y_k,\ k)$$$ (in C++ we use the standard set<pair<int, int>>).

    When adding a new point $$$(i\ +\ 1)$$$ to the window, we can quickly find the closest nodes in the tree $$$(y_p,\ p)$$$ and $$$(y_q,\ q)$$$ such that $$$y_p\ \leq\ y_{i + 1}\ \leq\ y_q$$$.

    If $$$y_{i + 1}\ -\ y_p\ \leq\ C$$$, then we register the edge between $$$(i\ +\ 1)$$$ and $$$p$$$ in the graph. Do the same with $$$y_q$$$.

    After that, you can simply traverse the graph and find the connected components.

    Code

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Task B. Biased Path

Author solution: Azret.

If $$$S$$$ and $$$T$$$ are not in the same connected component, or if it is the same vertex, but it does not have self-loops, then the answer is "Mumkun emes".

Otherwise, we can define the result of an operation of multiplying a square matrix $$$P$$$ of size $$$N\ \times\ N$$$ by itself to be the matrix $$$R$$$, where $$$R_{i, j}\ =\ min(P_{i, k}\ +\ P_{k, j})$$$ for $$$1\ \leq\ i,\ j\ \leq\ N,\ 1\ \leq\ k\ \leq\ N$$$. Now you can raise this matrix $$$A$$$ to the power $$$2019\ -\ 1,\ 2 \times\ 2019\ -\ 1,\ 3\ \times\ 2019\ -\ 1$$$ until, as a result of multiplication, let's denote it by the matrix $$$B$$$, the value of $$$B_{S, T}$$$ will not be determined ($$$-1$$$ appears because the number of vertices in the path $$$-\ 1$$$ = number of edges).

Code

Author solution: ulandev.

Run Dijkstra on the graph $$$G\ \times\ 2019$$$, where $$$2019$$$ versions of $$$V_r$$$ are created for each vertex $$$V$$$ (one version corresponds to one remainder of division by $$$2019$$$). Each edge $$$X\ \rightarrow\ Y$$$ turns into $$$2019$$$ edges $$$X_r\ \rightarrow\ Y_{(r\ +\ 1) \mod 2019}$$$. We are looking for a path from $$$S_1$$$ to $$$T_0$$$.

Code

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Task D. Deriving Sequence

Author solution: ulandev.

Task D can be solved using dynamic programming. The state is the position $$$i$$$ and the value of the element at $$$i$$$ $$$(-1,\ 0,\ 1)$$$. Using that we can compute the state for $$$(i+1)$$$ and all possible values $$$(-1,\ 0,\ 1)$$$.

https://pastebin.com/Dd8b8sG1 https://pastebin.com/gakcq8Lg

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

Why does it say "Rejected" when I submit in archive for Task B?

→ Reply