## Class SUmmary

(translation available later)

if(ok) //mid满足条件 { high = mid; //降低上边界 } else { low = mid + 1； //提高下边界 } 这样的话mid = (high + low + 1)/2; 对于 low = 2, high = 3如果mid = 2 满足条件就会出现死循环了。 因此必须 mid = (high + low)/2;

# POJ 1157 / IOI 1999: Little Shop of Flowers

The phrase "select ... from ... so that ..." tells that this is a DP problem. Since there are only two incrementable variables (flowers and pots), the DP array is 2-D. Therefore, DP[i][j] must stand for the maximum pleaseantness with I flowers and J pots. Since this problem requires the result to be based on both the DP array and the input together we can merge them into one array. Also, since every value D[i][j] where j

## Problem: 08 Clock

#### What's the problem?

One optimization is not always enough. Other checks, as simple as drawing three branches for each nodes, can reveal that doing step 2 after step 1 and doing step 1 after step 2 is the same; with this, you can remove four out of nine nodes per round, a significant optimization than the little 1/729 improvement through detecting repeated steps. It is very simple to just do some more work extending the bounds to revealanother more important optimization.

08 CLocks

This problem uses a BFS search for the shortest-reachable solution. However, a simple BFS is way too slow. But we can still improve the O(9^n) time complexity. We can first save each state as a base-4 number (e.g. 132331201) and convert it into base 10, then save it to a hash array. Or even more simply, we can realize that a move sequence like "I J" where I and J are integers in 1~9 produces the same result as the sequence "J I", cutting down 4/9 values every round. Also, storing the different movements can be done in an array: store a 0 or 1 in the array depending on whether or not a move changes that clock. Then, iterating over a specific sub-array and adding the value, whether 0 or 1, updates the array.

Darren Li

New York City