770C: Online Courses in BSU

Build a dependency graph, and then DFS on all k main courses. In the end, order by the post finish time

769C: Cycle in Maze

Note that we want lexicographically mininal cycle, this means we don’t need to find minimal length at all, because to get the lexi graphically smallest cycle, we need to insert D as many times as we can

also note, we want to find cycle with length exactly k, k = mahanttan distance + 2 * number opposite the distances. i.e., given K, we know how many extra D and Ls we can insert, if we know the the shortest path we need to k

So we need to calcualte the shortest path from the desitination to all grids, and then from the starting point, we try inserting D as much as we can, until step + shortestPath(grid) = k, and then L, and then U

785D: Anton and School - 2(!!!)

Consider when we are at a ( bracket, so we need to know: # of (s before i, and number of )s after i, and any same number combination would work.

Turns out there is a closed formula for that! When we have a answer-ish string, i.e., starts with x (s followed by y )s, the total choice is (x+y choose x)

Proof

  1. Consider our combination, # of opening brackets in x picked o => x - o closing brackets are picked, however, at this time we also have x - o open brackets UNPICKED (because we have in total x opening brackets). Therefore, each pick maps to a combination

  2. Each of the mapping translation is equivalent and reversible. Therefore, this closed formula is sound and complete

Note that we are going through the string. To avoid duplicate, we need to mark that the current ( we run into must be selected. This change the formula to choose(lb + rb -1, lb)!!!