AtCoder Grand Contest 021 will be held on Saturday (time). The writer is DEGwer. This contest counts for GP30 scores.
The point values will be announced later.
Let's discuss problems after the contest.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:40:05
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:40:05
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 03:54:57 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Looking forward to the contest!
Is there already a page/spreadsheet with GP30 scores?
Yes, it's published here.
Well, I understand that it's strange question from 8-th place, but how to solve anything except A?
I have no idea why my solition on D is correct (just remember from somewhere fact, that this value and length of maximum palindrom sub-sequence is same). And my solution of B seams to be too hard and still not fully proven.
For D, isn't it obvious? Suppose for simplicity that the answer is even. We divide the subsequence into two strings, the first string s1 with the indices at most
and the second s2 with the rest. Now if length(s1) > length(s2) then we can construct s1 + reverse(s1), otherwise if length(s2) > length(s1) we can construct reverse(s2) + s2. In both cases we obtain a contradiction with the maximality of length. In conclusion we must have that length(s1) = length(s2). Now if s1 + s2 isn't palindrome we can choose string s1 + reverse(s1) which is a palindrome and have the same length.
Well, easy enough. But wasn't obvious for me during contest.
B is construct convex hull and find angles. It can be seen easily that each point not on convex hall has finite area or linear dependence on R . for points on convex hull area is of the order of sector area by that 180- angle so it is R*R order. So ratio of 180-angles will be enough
Well, I had the same, but it looked like too hard for 600-point.
It also looked too hard for me, so I decided to keep things simple:
Let's take a very big circle (R=1e9 isn't big enough but I was lazy to check it in advance and got WA because of that; 1e11 or 1e12 will work better) with center at (0,0). Let's take 1e6 points on it and find answer for each of these points; such approximation will be good enough to get AC :)
Note that we don't need to construct convex hull explicitly because of the low constraints. Please check editorial for details.
Any hints for B, please?
The editorial is posted (you can see the English solutions in its second half)
I've read the editorial for problem E and since there's no forum to ask questions, I'll ask here. Firstly, I don't totally agree with the y-x>=B-N+1 restriction in the case when R=B (for the record, I do understand what conditions the sequence must fulfill in order to be counted). Since y represents the count of blue balls and x represents the count of red balls at a point, at least in the particular case when R=B, in order to meet the "red, blue" subsequences requirement, x should be greater than or equal to y (x >= y). That is, the point should never enter the region y-x >= 1, which is totally different from B-N+1 (which btw I have no idea where it comes from). Also, this condition is enough (it also implies that the path passes through (R, B-1)). Where is my reasoning wrong? Anyway, the problem is that I wouldn't be asking here, if I knew how to continue it. The problem is that when B<=R<=B+N-1, we need to have at least N-R+B red-blue subsequences, and in this case I really can't see such an easy interpretation of the constraints: I'd say that only for y>=something (namely, for the last N-R+B blue balls), the points must have y — something <= x (to assure that we have enough many red balls to choose from in order to match the current blue ball). The problem is not the formula, but that in this case, the restriction starts to be applied only after a certain values of y. I guess the editorial can't be that wrong, so could you please briefly explain me where is my reasoning wrong? (and/or note if there is any mistake in the editorial — I really can't see how the formula in the R=B case makes any sense)
I got stuck on the same point. I think you should consider the case n=2, k=6. For example, if we only check we never enter y-x >= 1, we will miss a sequence like "RBBRRB" which is valid.
Holy shit, you're right! I now realize that when I wrote the comment, I was thinking of something like B=R=N (when all the Bs have to be matched with a R that appeared before). I have to rethink the condition, but now that you helped me realize I was totally losing track of N, I think I can. Thanks!
Could you please upload testcases?
Could I get 27.txt of task C:
input and the answer (YES/NO)?