Does anyone know the live standings of IZhO 2022?
Does anyone know the live standings of IZhO 2022?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 157 |
6 | maroonrk | 155 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | BledDest | 145 |
Название |
---|
Today and tomorrow IZHO 2022
standings of day 1
Do you have the standings of Day 2?
standings of day 1 + day 2
How to solve A?
Given an array
a[1], ..., a[n]
. You can delete i-th element if2 * a[i] = a[i - 1] + a[i + 1]
. What's the minimal length of array after performing some operations?n <= 300000, 1 <= a[i] <= 10^9
Subtasks:
(14 points).
n <= 15
(13 points).
a[i] = i
(9 points).
a[i] <= 3
(17 points).
n <= 300
(18 points).
n <= 3000
(29 points). No additional constraints
+
DP on substrings
Let's look at the difference between adjacent elements.
Assume that $$$b_i = a_{i+1}-a_i$$$, and now our task will be to remove equal neighbors, and put the doubled value instead.
Now let's do some dynamic programming here, $$$dp_{l, r}$$$ — which determines whether we can remove a subarray $$$b_{l \dots r}$$$.
The observation is that, for the fixed $$$l$$$, there at most $$$log_2(n)$$$ such $$$r$$$. Hence, for each $$$l$$$, we can just maintain a set that stores those rightborders. Try to come up with transitions by yourself.
After calculating these $$$dp$$$ values, the problem can be solved with another dynamic programming. $$$d_i$$$ — minimal length of after performing operations on prefix $$$b_{1 \dots i}$$$. Answer to the problem will be $$$d_n$$$.
Thank you very much
Do you have the other tasks too?
IZHO 2022 day 1 problem A really difficult for me
Can anyone tell me IZHO 2022 day 1 problem B and problem C
Does anyone know the standings of IZhO 2022 day 2?
standings of day1 + day 2