a codeforces contest.
A. Game with a Fraction
if Alice can always win by decrementing
what are some losing positions?
if then is losing β is losing β if difference is , must get to .
otherwise always winning by the same logic (no bad pairs which descend from this pair)
https://codeforces.com/contest/2196/submission/369064455
B. Beautiful Pairs
clearly . letβs enumerate the larger of the two valuesβ¦then the other has only possibilities
https://codeforces.com/contest/2196/submission/369065627
C. Interactive Graph
let denote the set of paths starting from
note that if a path currently ends at , the number of ways to extend it is always because the graph is a DAG
proof: no path in can ever contain a previous node in the path, otherwise there would be a cycle. therefore, all paths are always valid.
therefore, we can always skip to the next edge (unless we exhaust all paths with this prefix, in which case we move to a new node --- this is why we get extra queries)
https://codeforces.com/contest/2196/submission/369308801
D. Double Bracket Sequence
what if thereβs only one bracket type
well, surely not better to swap to the other bracket type
proof: we can replace all oc of other bracket type with this one, balances strictly larger
fix # of ) to change to ( β we should definitely change a prefix of these same of ( to change to ) β we should definitely change a suffix
if difference between the two counts is , then we have to change at least occurrences of ( to )
at the same time, if )))]]], we have to know to change all ) to [
for two brackets, a similar observation should hold: we should change prefix of ), ] and a suffix of (, [
but maybe we want to change ) to ]? hmmβ¦
for example in the obvious case (], we have to keep the side of one of them
well if we change ) to ] and a later ) to [, evidently we should swap
therefore for ), we change a prefix of it to ( or [, and a suffix to ]?
actually, i think it should be [[[ ((( ]]]
[)() β would should change the first ) to a ] rather than the second one
but in ()[) then we should change the second one
what if we ignore the types, fix the brackets, then pair matching ones to a given type? countercase
[)]](]
minimal with ignored types is 1, but opt solution is
[[]]()
(read editorial)
first, I missed a really obvious solution for single bracket: just flip ) to ( when bal < 0, and if bal > 0 at the end, flip the last few ( if necessary
proof: if the minimum balance is , we must use at least flips to make it valid. then, we must use a certain number of flips to get final balance back to zero, and the above algorithm is one way to achieve this
after way too much thinking, I finally have a satisfactory explanation of this problem
a nice way to rephrase the RBS condition is like so:
there exists a pairing of brackets such that each pair is either or
thus, consider fixing the pairing and summing the costs of each pair. here are two crucial observations:
- if there exists a matchable or that are not currently in the same pair, it is not worse to pair them together instead (from at least 1 + 1 to at most 0 + 2). from this, we know that we must match an LPS (longest valid parentheses sequence) for both bracket types.
- from here, it remains to determine which specific LPS to pick. we refer to a bracket in a 0-pair as matched, otherwise unmatched. then, if there exists an unmatched ) between a 0-pair, it cannot be worse to match the left bracket of this 0-pair to the ) instead. similar for unmatched (.
together, these two operations uniquely determine the optimal LPS for both bracket types. as for the remaining string, first erase all types as these donβt matter for 1-pairs and 2-pairs. then, if there are an even number of both bracket types, we can form all 1-pairs. also, if there exists (), we can also form all 1-pairs. otherwise, the string looks like
)))...)(...(((
where both types occur an odd amount of times. since 1-pairs can only be of the form )) or ((, it follows that we must form at least one 2-pair that looks like )(.
therefore, we have found the optimal solution.