916A: Jamie and Alarm Snooze

This is type of question where existance proof leads to solution

Claim: the answer will exist within 24 hours Proof: because each click <= 60 seconds, so we will hit every single minue of the day, i.e., we will hit 07:mm and 17:mm

916B: Jamie and Binary Sequence

This is a relaxation problems

Constraint: we # 1 bits <= N

Note that for each bit we shift to the right, we increase total count by 1, i.e., we can gradually push bits to the right until we hit N

So we can try:

  1. Can push all bits?

  2. if not, just push 1 to the right by 1, and increase counter by 1

916C: Jamie and Interesting Graph

Build the graph N - 1- 2-…..N - 1, calculate two primes s.t., p2 - p1 > n - 2. Assign p1 to N-1, and 1,…., p2 - n - 2 to (N-2) - (N-1)

For each remaining edege, just add complete graph i -> (i - 1 + deala) % N + 1, with weight p2, until we reach the total count

914C: Travelling Salesman and Special Numbers

The more 1 bits we have, the higher k will be. Therefore, we can dp to find a range of # of 1 bits, s.t., # of steps = k

Then we can answer the following questions, given n, how many #s <= n has < nb 1 bits

so we scan from left to right, keep track of how many 1 bits we have encountered so far, for each one bit we have, we have (remaining pos to the right choose remaining 1bits) to the answer. In the end we need to check if n itself has <= nb 1 bits

914D: Bash and a Tough Math Puzzle

Uses a variant of segment tree