Can you please give a counter-example to find the error in my approach??? (I guess there is an overflow -_-) Problem:- https://codeforces.com/problemset/problem/1594/C My approach:- https://codeforces.com/contest/1594/submission/170945137
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.04.2024 19:56:27 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by the.wiz (previous revision, new revision, compare).
The correct approach is simpler. (My proof might scare you, though, because I made it rigorously.) Case 1 (you found this one): all characters are equal to
c. Then no operations are needed. Case 2: Not all characters are equal toc. Then we have further subcases:A. There is at least one character not equal to
cin the first n-1 characters and the nth character is equal toc. B. The nth character is not equal tocand the first n-1 characters are all equal toc. C. Among the first n-1 characters, one is different thancand the nth character is different than 'c'.X = n
X = n-1
Remember that the sum of all n is at most 300000 (and the time limit is 2s). This means we can safely use an algorithm with
O (n log n)time complexity. Trying all possible values of X between 2 and n-1 and checking that the characters on positions X, 2X, 3X, etc. are all equal tocis such an algorithm and should do the trick.Basically: if we find such an X, then we can output it and that is a solution. Otherwise, we must do it in two steps: X1 = n and X2 = n-1.
Suppose that we can do it in one step with a certain X. So, after the operation, all characters are
c. This means that, before the operation, all characters on positions X, 2X, 3X etc. were alsoc. (For any X, the characters on position X, 2X, 3X etc. are equal tocbefore the operation if and ONLY if these characters are equal tocafter the operation.) This means that there exists an X (1 <= X <= n) such that all characters on positions X, 2X, 3X etc. are equal toc. However, this is NOT true because we are in case 2, subcase C. X=1 doesn't work because all elements should have beenc, X=n doesn't work because the nth character should have beenc, and all other X-s don't work because we checked them. Contradiction. Therefore, we can't do it in a single step. QEDThnx a lot sir ... I got it.