Round 65: Crossing Tree

Answer = 2 * |E| - |longest path|

So we find the longest path first, and put all its edges on a black list

then we start from the first to the second last on node on the longest path, and print out the traversal minus the blacklist edges

Round 65: Count Arrays

I had many problems during idea and implementation!!!

Consider the final array we get, we will just consider number of good arrays ending with i with a[i] = 0.

Find the left most i, that we can construct a good array even if all betwee i and j are filled with 1,e.g, with a two pointer method, and then calculate the partial sum in [j, i).

Round 66: Counting Quacks

sort n numbers, and start calculating for the min LCM <= T, the first answer = number of index, the second answer the T/LCM(1…i)

Round 66: Flipping Matrix

We can see that if there is a row or col full of 0s, we can not flip it.

Claim: as long as no row or col full of 0s, we can find a way to flip Proof: that means, each row in each col forms a permutation of 1..n, i.e.,we just need to rearrange the perm.

So we can just, for each col, find which rows has it. and we keep track by the set size, and we sort by the set size

For each swap, we will

  1. swap first non-visited set.begin() row number with the current col

  2. update the doublely linked map of original col <-> after col

  3. update visited row to col

Official solution

Modelled it as bipartite graph, and find a perfect matching,e.g., by Hopcroft-Karp