922D: Robot Vacuum Cleaner

Order by the ratio of h/s

proof: Consider the noise function of f(a + b) = f(a) + f(b) + ns(a) * nh(b) Conversely, f(b + a) = f(b) + f(a) + ns(b) * nh(a)

Therefore, f(a+b) > f(b+a) <=> a’s ratio (s/h) is higher

Implementation-wise, watch out for the case where nh = 0 and handling doubles!!!

934C: A Twisty Movement

Considering the point separating 1 and 2, if the band we select does not cover the point => Consider the case of not choosing anything

Therefore, we just dp on the cutting point, and reassemble the two parts 1112222111222

932D: Tree

binary lifting

938C: Constructing Tests

Easy to see the maximamum 1 pattern => x = n^2 - floor(n/m)^2

So we can brute force on all factors and see if possible to form a pair of factors

938D: Buy a Ticket

  1. For back and forth, double the edge count

  2. To calculate multiple shortest paths, just add all nodes to the initial heap. The final answer is the answer we are looking for!!!