Someone Please Explain D,E solution(English)?It's in Japanese
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
10:15:32
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
10:15:32
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.11.2024 07:19:29 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
My solution for D: It can be observed that the whole game consists of two phases: In the first phase Takahashi will take the greatest numbers, which Aoki will take some numbers around x. In the second phase the two will alternately take the greatest number. One should binary search on the position such where the transition between two phases happen. To check it one may need another binary search to count the numbers taken. After that the sum can be computed in O(1) if precalculated the partial sums and partial sum on even indices. The solution takes
time.
Can u explain the two phase in above test case.Thanks
5 5
3 5 7 11 13
1
4
9
10
13
I'll explain the third query. I'll use T for Takahashi and A for Aoki. First T takes 13, A takes 7, and then T takes 11. Then A was supposed to take 11, but it is already taken by A. This is where the transition happens: the two players' territory(I don't know if this is clear enough) intersects. From now on, A and T will alternately take the greatest number remaining, which is: A takes 5 and T takes 3.
I had a similar idea: a suffix of A will be taken by Takashi, some part (same length or one less) before that by Aoki and the remaining prefix alternatingly. Then I processed the queries sorted decreasingly and kept pointers to the borders, so it's
.
edit: It's
Oh yes, this can be done more efficiently if processed offline. But I think that's
due to the sorting process :D
Yeah, I added the
in the wrong place :D
How to find the position of transition?
In fact, I binary searched on the suffix that was taken by Takahashi. which requires the length of the region of Takahashi to be at most one more than the length of the region of Aoki. This may be hard to explain, you may refer to my code. Code
why l=pos-1 in ur code?
and ll numl=mid-(lower_bound(a,a+n+1,2*x-a[mid])-a) what it does?
The first one is because I choose r as the final answer, and pos is an valid answer. The second one implies the amount of numbers in Aoki's region.
My solution for E: Let dpv, j, 0 denote the minimum sum of Ai in the connected component of v if we cut j edges in the subtree of v, and the connected component of v only consists of batteries. And dpv, j, 1 denote pretty much the same thing, but allows the connected component of v consists of computers. The DP should be calculated in an ordinary manner, which may seem to have a complexity of O(N3), but is actually O(N2). There are many proofs given on this kind of problems, e.g., Barricades in Algorithmic Engagements 2007, which can be found in the book looking for a challenge