arvindr9's blog

By arvindr9, history, 5 years ago, In English

I was doing 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.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).