Two hard problems.
Problem 1: one person game: given 8x8 grid, with each cell having a number, find a path in the grid with maximum sum. The path cannot contain zero cell.
I wrote a brute force dfs solution, which passed case 1 and 3 by sheer luck. This 20 points was also the only points I earned. Now we know the starting position has to be nonzero. A cell can go up, down, left, right, 4 neighbors. Still no idea for a solution.
Problem 2: data center. Given integer n, find the number of possible labeled spanning forest with root, 1 2, 1 2 3, 1 2 3 4, ..., 1 2 ... n. MOD = 10^9+7
Two people solved it. I don't have any idea. Looks a tough counting problem.
UPDATE:
Solution for problem 2 from chhung6.
The idea is DP with knowledge of Cayley's formula. The number of labeled rooted tree with n nodes is n^(n-2)
Let dp[N][M] be number of forests with N servers and M clients,
then N=1 we use Cayley's formula.
N=2, we can use K clients to server 1 and M-K clients to server 2, and there are (M choose K) ways to split the M clients.
In general,
dp[N][M] = sum_K=0^M mult((M choose K), dp[N-1][K], (M-K+1)^(M-K+1-2))
be careful when M-K+1=1, then (M-K+1-2) is -1.
Now that we have dp[N][M], the answer is sum_K=2 to n: dp[K][n-K]
since n could be as large as 10^9, you know you need a closed form. Then the natural step is to google the first a few terms. However, there is a catch.
Search the first a few terms of ans[2, 3, 4, 5, 6] did not return anything useful. In fact, my search in google or oeis did not return anything.
Then the next step is to search sum_K=1 to n: dp[K][n-K], note the start index is from 1 now. This gives a closed form formula in oeis,
A058128 a(1)=1, a(n)=(n^n-n)/(n-1)^2 for n >= 2.
1, 2, 6, 28, 195, 1866, 22876, 342392, 6053445, 123456790,
our answer is simply a(n) - number of spanning trees with n nodes (that is, with only 1 server)
Subscribe to:
Post Comments (Atom)
http://ideone.com/960YK
ReplyDeleteI did try solving this problem but could able to pass only one test case. Can you please let me know what's wrong with my approach. In my code I am try to do DFS at the each vertex to find a connected component with maximum value.
I did the same thing. The first one uses very advanced DP which you work row by row but you have to remember how the row above you were connected. The algorithm probably runs in 2^8*8*8. Sorry I do not have a good reference to the solution, but I remember in codeforces.com there is a similar problem.
ReplyDeleteThe DFS approach easily TLE. I got lucky to pass 2 cases.
Is the first one a simple DP? Since the board is only 8*8, and the path length is only 64 at most. I guess so, I didnot read the original problem before..
ReplyDeleteyou can still code and submit. Your idea sounds like exponential. length 64 is quite large indeed.
Delete