Thursday, September 19, 2013

ACM ICPC 2009 Greater New York Regional

A. Simple sorting O(N log N)

B. Greedy O(N^2)
The value of a divided subset has to be bigger than a element.
If you decide a value, you can check the fact that it is possible or not.

C. Dynamic Programming
D(i, j) : minimum value in total 'j' stairs, having 'i' balls.
D(i, j) = min( D(i-1, j), max(1+D(i-1,k-1), 1+D(i, j - k) )

D. Stack or Heap O(N) or O(N log N)

E. STL next_permutation()

F. Dynamic Programming
D(i, j, k) : The number of ways in length 'i', adjecent bit are 'j', situation 'k'(number in 'i'th)
D(i, j, 0) = D(i-1, j, 0) + D(i-1, j, 1)
D(i, j, 1) = D(i-1, j-1, 1) + D(i-1, j, 0)
the answer is D(n, m, 0) + D(n, m, 1)

G. Graham Scan

H. Graham Scan & Mathematics

I. BFS with bitmask

No comments:

Post a Comment