→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.11.2024 21:53:21 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
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?
Are people with star on their names real (onsite) participants?
Yes.
Will be there editorial and will be possible to finish the problems ?
You can submit problems in archive.
About editorial ask from TooNewbie he solved all problems :)
thanks -emli- !
You can look at the solutions below.
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?
Answer array will be in range $$$[-1, 1]$$$.
Answer array will be like this : $$$[-1, \dots, -1, 0, \dots, 0, 1, \dots, 1]$$$.
There is only one element which operation can't applied. Thus, it is min of answer array.
How answer array will be like if $$$a_1 = 1$$$.
$$$[1, 1, 1, \dots, 1]$$$.
How answer array will be like if $$$a_1 = 0$$$.
[0, 0, \dots, 0, 1, 1, \dots, 1]. if there is $$$-1$$$ between first element and first one, array can't be sorted.
How answer array will be like if $$$a_1 = -1$$$.
With hints above we can apply this kind of algo. For example we contructed answer for some sequence = $$$[-1, \dots, -1]$$$.
If next element is -1. We can just skip it.
if next element is 0. We can apply operation for next element, then it can be $$$-1$$$ or $$$0$$$.
1. if it will be $$$-1$$$. We continue algorithm.
2. if it will be $$$0$$$. We can solve problem like it in hint 2.
if next element is 1. We can apply operation for next element, then it can be $$$-1, 0, 1$$$.
1. if it will be $$$-1$$$. We continue algorithm.
2. if it will be $$$0$$$. We can solve it like in hint 2.
3. if it will be $$$1$$$. We solve it like in hint 1.
In addition I think it can be solved with dp too.:)
How to solve C?
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:
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
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
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
Why does it say "Rejected" when I submit in archive for Task B?