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

# | User | Rating |
---|---|---|

1 | Benq | 3813 |

2 | tourist | 3768 |

3 | maroonrk | 3570 |

4 | Radewoosh | 3535 |

5 | fantasy | 3526 |

6 | jiangly | 3523 |

7 | Um_nik | 3522 |

8 | orzdevinwang | 3441 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 179 |

3 | nor | 169 |

4 | Um_nik | 167 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

7 | adamant | 162 |

8 | kostka | 161 |

9 | YouKn0wWho | 158 |

10 | errorgorn | 155 |

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

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/27/2023 04:35:20 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by asaecs2 (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 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. QEDThnx a lot sir ... I got it.