arc091_b: Remainder Reminder

Just interate through i * f + K, for all i in [K + 1, N]

arc091_c: LISDL

A >=1, B>= 1, A + B <= N + 1.

Claim: A * B > N Proof: I got stuck here!!!

arc092_a: 2D Plane 2N Points

I used maximal bipartite matching. given N = 100, can be solved with Ford-Fulkerson as network flow problem. Note that this algo has a simplified form for implementation!!!

Note that this approach costs O(V * E), because for each node, we essetinally tranverse all edges in a DFS way, during the shift update with the help of visitor

Official solution

Similar to all pseudo bipartite matching problems, we can just sort one side, try matching head at each time, and take the most restricted matching at the time, so that we leave more possibilites to the remaining ones. Note that translating it to bipartite matching loses too much contextul information, and thus a harder implementation.

Note the core reason the greedy approach works is that suppose the optimal solution didn’t match the current head or matched a different one, we can swap the mapping while maintaining the count

arc092_b: Two Sequences

Consider each bit indepdenently