### asaecs2's blog

By asaecs2, history, 5 months ago,

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

• +3

 » 5 months ago, # |   0 Auto comment: topic has been updated by asaecs2 (previous revision, new revision, compare).
 » 5 months ago, # |   0 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 to c. Then we have further subcases: The subcasesA. There is at least one character not equal to c in the first n-1 characters and the nth character is equal to c. B. The nth character is not equal to c and the first n-1 characters are all equal to c. C. Among the first n-1 characters, one is different than c and the nth character is different than 'c'. Suitable X for case A.X = n Suitable X for case B.X = n-1 Solution for case C.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 to c is 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. Proof of two-step requirementSuppose 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 also c. (For any X, the characters on position X, 2X, 3X etc. are equal to c before the operation if and ONLY if these characters are equal to c after the operation.) This means that there exists an X (1 <= X <= n) such that all characters on positions X, 2X, 3X etc. are equal to c. However, this is NOT true because we are in case 2, subcase C. X=1 doesn't work because all elements should have been c, X=n doesn't work because the nth character should have been c, and all other X-s don't work because we checked them. Contradiction. Therefore, we can't do it in a single step. QED
•  » » 5 months ago, # ^ |   +3 Thnx a lot sir ... I got it.