Balanced String IOI 2016 Training Round #5 -- how to prove the solution is correct

Revision en1, by arvindr9, 2020-01-30 05:39:38

I was do the following problem:

Basically, given a string $$$S$$$ of $$$A$$$'s and $$$B$$$'s, you want to determine whether for any two circular substrings of $$$S$$$ of the same length $$$l$$$ ( $$$1 \leq l \leq N, 1 ≤l≤N$$$ ) the number of As in the first substring and the number of As in the second substring differ by at most 1. (A circular substring is basically a substring that can wrap around S, such as $$$[S_n, S_1, S_2]$$$).

The solution in the editorial seems elegant, but I'm not sure how to prove its correctness.

Any comments about why the solution is correct are appreciated.


  Rev. Lang. By When Δ Comment
en2 English arvindr9 2020-01-30 05:41:51 3 Tiny change: 'I was do the follo' -> 'I was doing the follo' (published)
en1 English arvindr9 2020-01-30 05:39:38 823 Initial revision (saved to drafts)