333B: Chips(!!!)

Assume there is no obstables, what is the maximal number we can add?

  1. Because of rule 2 and 3, we can not add chips to both ends

  2. Because of rule 2, given i, we can add to either row i or col i, but not both

  3. However, if we add to (i, 1), we can also add to (n, i), (n - i + 1, n), (1, n - i + 1)

  4. Therefore, the maximal possible is around 2 * n. Note that if n is even, the middle row is the special case.

  5. Also, need to try all from 2 to n -1, but need to consider the case where previously added chips blocks later additions!!!

115B: Lawnmower(!!!)

However, I had problem implementing the solution quickly and cleanly. The reason being my greedy algorithm is not concise enough.

Suppose we’re on a row, facing right. This strategy say that we need to move to the right as long as there is a weed to the right of us either on this row or on the row directly below us.

Note that this insight can handle the empty row cleanly. Also, we need to track of the last row to calculate how many move down operations we need

34D: Road Map

The old map represents a parent-child relationship easily. Therefore, we can construct the graph and do a simple tree traversal to update the new map

367B: Sereja ans Anagrams

Notice that p is fixed. We can just group entries by ps, and then do a slide window scan to match all possible starting indices

776D: The Door Problem

My WA approach(!!!)

Suppose there exists a solution, what property it has?

  1. If the door is closed : then t(d1) + t(d2) is even, i.e., they have the same oddity

  2. If the door is open: then t(d1) + t(d2) is odd, they have the same oddity

Note that each switch has only 2 choices, even or odd, any numbers can be reduced to this choice.

Conversely, if we can find an arrangement that satifies such odditiy requirment, then we know in the end all doors are open => i.e., we are good, and this condition is strong enough.

So what we can do

  1. In case 1, we union them
  2. For case 2, we union all it opponents
  3. In the end, we scan through all contradictions again, to make sure they are not unioned, i.e., no conflict

Official Approach

Since we care only the oddity, this means we can reduce to toggles to 2 cases, either 0 or 1 Model switch as nodes and door as edges, try coloring node from switch 1, and see if we can introduce any conflicts

Note that implementation wise, it is OK to have duplicates edges in our DS.Although need to consider the case of multiple components - I missed that case!!!