Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

arvindr9's blog

By arvindr9, history, 2 months 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.

Read more »

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

By arvindr9, history, 2 years ago, In English,

The link to the problem can be seen here: http://naipc.uchicago.edu/2017/_static/naipc2017.pdf

Basically the problem gives a list of strings of parentheses (not necessarily valid) and asks to find the length of the longest valid string of parentheses by concatenating some of the strings from the list.

I was looking at the solution here: http://www.cs.ucf.edu/~dmarino/progcontests/mysols/northamerica/2017/pieces.java

The solution involves placing the strings into a vector and then ordering them based on low (the min value of open minus closed over all intermediary characters) then diff (open minus closed) then length. Then, DP is used to find the longest length that results when concatenating a subsequence from the vector into a valid string of parentheses.

What I am confused about is why the vector can be sorted that way. This seems to imply that any set of strings that form a valid string of parentheses can be rearranged in the sorting order explained above and still form a valid set of parentheses. This seems intuitive (of course you want to have a nonnegative low value for the first string and you want a positive diff value for more open parentheses at the beginning of the string), but why does this work?

If anything I said was unclear, please let me know. Thanks!

Read more »

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