March Cook-Off starts in less than 3h.
Setters are kefaa and chemthan.
Let's discuss the problems after the contest.
UPD. Contest is over. Congrats to the winners!
→ Обратите внимание
До соревнования
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 23:06:35 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
I think I've seen the matrix restoration and array restoration problem somewhere before.
How to solve Chef Restores an Array?
Two adjacent numbers are either related by a +/-1 or not related at all. If they are related by both, ans is 0. To find the relations in linear time, we can use 2 prefix DPs, one for 'I' relations and the other for 'D' relations.
From numbers you already know, you can traverse using known relations(edges) to get unknown numbers and at same time verify other known numbers. We need to make sure that these numbers are in the range [1, k]. For numbers that are still unknown, they will form a forest of chains. In each of these chains, we need to see the difference between the largest and smallest.
Editorials please
chemthan(or anybody else) can you explain the approach for the maximum path on tree question???
Firstly we ignore gcd(u, v), just find the maximum of dist(u, v)·min(u, v). Iterating vertices in decreasing order by values written on them and maintain DSU structure. Each time we connect an edge (u, v), we're only interested in paths pass through that edge. We will maintain diameter of each component. If (x, y) is diameter of u's component, (z, t) is diameter of v's component then the longest path passes through (u, v) is among (x, z), (x, t), (y, z), (y, t). Complexity is O(LCA(N) + DSU(N)).
Now, finding the maximum of dist(u, v)·min(u, v)·gcd(u, v): For each d, we consider only vertices that values written on them are multiplier of d and apply above approche for each group. The sum of all groups is at most N * max_number_of_divisor_of(a[i]) ~ 6e6. We can optimize LCA part by using LCA O(1) per query, so total complexity will be O(DSU(N * max_number_of_divisor_of(a[i])).
how do you solve |S|*AND(S) problem
fix the AND, iterate over supermasks, find largest connected component with dsu.
there are ~2^20 possible values for the AND right? How would you use DSU to find the largest connected component for each value of AND?
say we want to make the and equal to x, add the vertices that are supermasks of x one by one. After adding one we check if its parent is also supermask of x, if that is the case we merge them with dsu. Complexity: 3^17