I'm stuck in test case #10 in D. The test case has n = 20000. Is there a way I can see the complete test case?
I'd be thankful if someone can review my solution: https://mirror.codeforces.com/contest/1272/submission/166760372
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 160 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | Dominater069 | 154 |
| 8 | awoo | 154 |
| 10 | luogu_official | 151 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 11:16:52 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
I am not sure if seeing it will help you out in some way, but basically you can output the vector for example saying if the first number == 33125630.
From testcase #5 onwards, the values are in the range of 10^7 — 10^9 and n is 20000. I feel, I am probably missing some edge case. I have been thinking about it for two days. I am unable to see. I have seen solutions from the editorial as well as top rankers from the contest. They have slightly different implementation which is clearer than my solution. However, I'm not over invested in my solution and really want case I'm. missing.
N is 200000.
Yes. Sorry. N is 200000 from testcase#5 onwards.
Any reason behind doing space optimized solution?
I did not think about it as dp at all. I just thought that to calculate the answer I don't need more than 3 values at once. It is a coincidence that the solution is a space optimized dp.
Does s denote a max with 1 deleted element and f with all consecutive elements?
Yes
Last else if states that v3 > v1, but if it is less then all variables reset to 0/1. Consider the case when v3 <= v1, but v2 > v1.
I am actually not quite sure if we can consider such case having only 3 variables. I'll try once more in a bit, but I might assume it either needs a bit more of variables or is impossible.
Nope, I can't find a way to solve it using 5 variables only.
Take a look at Ticket 15977 from CF Stress for a counter example.