a codeforces contest.
A. Divisible Permutation
just do it https://codeforces.com/contest/2188/submission/368936553
B. Seats
I actually sillied here and thought the contribution of a segment was rather than …bad looks.
C. Restricted Sorting
we can freely rearrange all values in the range among themselves
also note that if there exists such that and , this value can never be moved. otherwise, conjecture that all other values may be freely rearranged?
proof: we can always move either to to a non-stuck index. we can then swap this to either or if needed, then swap with the desired value.
https://codeforces.com/contest/2188/submission/368940046
D. Shortest Statement Ever
answer bounded by because we can just set either or to
(after consulting editorial, this doesn’t look like a very good problem…)
E. Jerry and Tom
Tom will win for sure if his shortest path to destination is Jerry’s
otherwise, I think Jerry always wins
(consulted editorial…solution is fairly nice, should probably better formalize optimal strategies when thinking about game problems in the future)
F. Cool Problem
(consulted editorial)
kind of cool I guess? still rather contrived though…
1E. Doors and Keys
1 0 1 1 1 4 0 2 0 3 0 14 0 10 18 7 25
1110000001
dp on rightmost unlocked door, current pos ⇒ value = minimum time to reach?
(read editorial)
i missed an observation: if going back for a key, it’s actually better to drag the keys along with you in order to maximize time of arrival of first key ⇒ better chance that the door has already been unlocked
formally ⇒ if you pass a key and come back for it later, you’d rather swap the moves so that you come back for it now
therefore, we basically only need to consider moving to the right but with the extra cost of dragging along keys ( if we are carrying keys)
finally, note that we should never carry more than keys because it will take at least time to get rid of all the keys, after which we could just wait for all the doors to open
Final Thoughts
IMO a pretty mid contest aside from Doors and Keys and Restricted Sorting