915C - Permute Digits

This follows the patterns of relaxation under constraint!!!

The key insight is that it doesn’t matter how you do brute force search, you have to try the minimal suffix, and see if it can be smaller,i.e., the first digit < b’s digit may not be d[i] - 1.

One counter example is 31, 30, the answer should be 13.

915D - Almost Acyclic Graph

The removed edge must be on a cycle, so we just find a cycle, and try edges on them one by one, to see if the removed graph is acyclic.

Note that to detect cycle in directed graph, we need a “visiting” state on top of the visited state.

I got the idea during the contest, but i was hesitant to calculate n^3 solution, because I didn’t notice that # of edges is no more than 10^5, which makes the overall performance right into the bound!!!

906A - Shockers

Maintain a set of impossibles

  1. for each ., add letter to impossible

  2. for each !, add all letters not in the word to impossible, and check if all but one letter in the word is invalid

  3. for ?, check and update if we are in guessed mode

Official solution

From the last entry we know the answer, and then for each letter, we calculate the latest entry that deny’s its existance. The final answer is the latest of all other 25 letters

912C - Perun, Ult!

This problem has a lot of corner cases!!!

Three types of events

  1. health is set to less than the kill threshold

  2. health is set to higher than the kill threshold

  3. health has been regened more than the threshold

Note that max value must exist in the second right before the second and third event. So for each event, we add a type 2 and or 3 events, and then we do linear scan