283B: Cow Program

  1. Note that there are two steps, so we need 2 states for entry.
  2. Because cycle may exists, we use DFS pseudo-code, i.e., we recursive call without parent and then check result instead of doing it before the recursive call.

25D: Roads not only in Berland

1. use DFS to detect redundant edges in a tree

2. For each compoent, add that edge to any node in that component (can force order here)

274B: Zero Tree

Just start from the root and cascade down

452B: 4-point polyline

Follow the example, we can see the pattern is a Z-shaped polyline along the diagonal. use this takes top 3 of the 4 longest line segments in the square.

Alernatively, we can try including both diagonals, and compare results to see which are the best

611D: New Year and Ancient Prophecy(!!!)

A naive DP solution gives O(n^3), how to improve it?

1. Use a prefix sum to calculate total ways(n - l, l1)

2. to do quick comparision, we just need DP to calc the first index where the seg starts at and the seg starts at b are different