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: https://csacademy.com/contest/ioi-2016-training-round-5/task/balanced-string/

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.

History

 
 
 
 
Revisions
 
 
  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)