Can you please give a counter-example to find the error in my approach??? (I guess there is an overflow -_-) Problem:- https://codeforces.me/problemset/problem/1594/C My approach:- https://codeforces.me/contest/1594/submission/170945137
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/10/2024 13:01:47 (l1).
Desktop version, switch to mobile version.
Supported by
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.