700A: As Fast As Possible(!!!)

I failed to solve this problem during contest. I thought the bus had to take students to the end and then head back

Insights

  1. To be able to minimize the time, all students should arrive at the same time. Otherwise, the bus could have headed back earlier and helped the slowest one

  2. Since input is 10k max, we can do a bsearch on number. Because we have the insight 1), the related search would be the final time every one arrives. Note that our epsilon is 10^-6

  3. Because each group arrive on the same time, and v1, v2 are constatnt, that means each group spend on the bus for the same amount of time. This furthur suggests the time spent to meet the bus heading back is same across all groups

  4. Therefore, we can calculate by multiplication, how much time bus has been running, and as long as bus run can conclude within t, the answer is possible

Remember to setprecision to display required number of precisions

645A: Amity Assessment

The DFS-state approach is too complex to code for this problem. For this problem, we notice that no matter how we move, the relative clockwise order of tiles remain same.

Therefore, it is enough just to form a 3 element string from inputs (minus the x), and see if we can rotate the from to form to

592C: The Big Race

If it will be a tie if, L is within the range of (i* lcm(w, b), i* lcm(w, b) + min(w, b))

So total # = (t / lcm(w, b) - 1) * min(w,b) + min(w,b) - 1 + tailBand

Note that need to handle the case where min(w, b) > T

53C: Little Frog

n = 3, 1 -> 3 -> 2

n = 4, 1 -> 4 -> 2 -> 3

n = 5, 1 -> 5 -> 2 -> 4 -> 3

The pattern is obvious now

717C: Potions Homework

Sort the student by laziness

Claim: the optimal is achieved when lowest lazyness is paired with highest difficlutiles

Proof: Exchange proof. Suppose we have l1 LT l2 and d1 LT d2, we can improve the solution by pair l1 with d2 and l2 with d1

l1 * d1 + l2 * d2 - l1 * d2 - l2 * d1 = (l2 - l1) * (d2 - d1) > 0

12C: Fruits

Sort the fruits by numbers

Max total = max # of fruit is most expensive

Min total = min # of fruite is most expensive

Exchange proof, note that the swap works for both ways

616C: The Labyrinth

Flood fill on each passable cells, for each passible cell assign the component number, and then for each wall, get the set of its neighbor component numbers and add up

635A: Orchestra

Calculate n(r, c) = number of vs in the rectangle with bottom right corner at (r, c), note that n(i, 0) = 0, and n(0, i) = 0

n(r, c) = n(r-1, c) + n(r, c-1) - n(r-1, c-1)

Then brute force on all (prevTop, prevLeft, br, rc) combos, find all combons such that n(br, rc) - n (prevTop, rc) - n(br, prevLeft) + n(prevTop, prevLeft), note that prevTop < br and prevLeft < rc