Class SUmmary

(translation available later)

二分的边界变动要注意。 对于此题,我们搜索的是最大值。 if(ok) //mid满足条件 { low = mid; //提高下边界 } else { high = mid - 1; //降低上边界 }

这样的话如果用 mid = (high + low)/2; 上下取整的话。如果low = 2, high = 3 如果mid = 2 满足条件那么就会一直死循环。 这是因为low = mid不修改本身。 因此要用向上取证 mid = (high + low + 1)/2; 这样的话不会出现问题了。

同样下面这个例子我们搜索的是最小值

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

总结下来就是,如果边界变动过程中满足条件后low = mid, 那么我们要对mid向上取整使得连续两次的low的值不会相同, 对于 high = mid,那么我们要对mid向下取整使得连续两次的high的值不同。

POJ 1157 / IOI 1999: Little Shop of Flowers

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

Lesson 1 8/25/2017 Yoyo

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 revealanother 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.

GitHub – testitem

Darren Li

New York City