JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Forums Algorithm Matches SRM 723 Div 2 1000
 Div 2 1000 | Reply How to approach the problem?I see some solutions in the practice rooms and also in contest but unable to prove why they are correct.Please help.
 Re: Div 2 1000 (response to post by saurabh119) | Reply I used almost 2hs to solve it..... You can split the pic into 5 blocks, and consider about :1) in-block path2) between-block path: I label the block from topmost 1, leftmost 2, mid 3, rightmost 4, and the remain 5. i) calc the path 1-2 , and the result is same to 2-4, 4-5 ,5-1 ii) calc the path 1-4 , and the result is same to 2 - 4 iii) calc the path 1-3 , and the result is same to 2-3 4-3 5-3when calculating the path 1-2 , you can only consider the bottom-left of 1 and the top-right of 2, and the in-block point to the bottom-left....I though there may be a more easier solution using InclusionÃ¢ÂÂexclusion principle...have a good luck.....: )
 Re: Div 2 1000 (response to post by scidylanpno) | Reply Thanks, that was very helpful.
 Re: Div 2 1000 (response to post by saurabh119) | Reply Another way to do this: You can find that the answer is exactly (59n^5 - 11n^3) / 3. There are O(n^2) vertices so there are O(n^4) pairs of vertices. The distance between two vertices is O(n), so you can guess that the answer is polynomial which degree = 5.Then, find the answer for n=0,1,2,3,4,5. Finally use "polynomial interpolation" and get the answer = (59n^5 - 11n^3) / 3. If you check for n=6,7,8,9,10, you can see that this polynomial is correct.
 Re: Div 2 1000 (response to post by square1001) | Reply Regarding polynomial interpolation, it's a nice idea, but you need 6 points to calculate 6 coefficients:https://www.wolframalpha.com/input/?i=interpolating+polynomial+%7B0,+0%7D,%7B1,+16%7D,%7B2,+600%7D,%7B3,+4680%7D,%7B4,+19904%7D,%7B5,+61000%7DThe statement only provides 4 points (without module): (0, 0), (1, 16), (3, 4680), (5, 61000). Someone did the following thing:https://community.topcoder.com/stat?c=problem_solution&cr=40509829&rd=17027&pm=14738Which is basically writing a brute force solution, getting the missing values for n=2 (600) and n=4 (19904) and solving the polynomial interpolation using wolfram alpha (or whatever online solver you want) and afterwards implementing the equation, which is constant. This is a nice piece of art.
 Re: Div 2 1000 (response to post by lgandras) | Reply Well, I found a some kind of 'magical' solution:I said that the answer polynomial is (59x^5 - 11x^3) / 3, but actually it's same modulo to 666666691x^5 + 333333332x^3 (let this the answer polynomial).It seems like the sample input only provides (x,y)=(1,16),(3,4680),(5,61000), but it's not true. Because:1. You can also get (x, y) = (0, 0), obviously.2. Doing "newton's polynomial interpolation" with mod 1000000007, you can add (x, y) = (12345, 598011702), (999993007, 763641672) from sample input (999993007 is equal to 1000000000000 mod 1000000007).Now you have 6 points! So you can get the answer polynomial!!!!!Also, the code of newton's polynomial interpolation (my library) is this:```vector interpolation(vector x, int m) { int n = x.size() - 1; vector inv(n + 1); inv[1] = 1; for (int i = 2; i <= n; i++) inv[i] = 1LL * inv[m % i] * (m - m / i) % m; vector > dp(n + 1, vector(n + 2)); for (int i = 0; i <= n; i++) dp[i][i + 1] = x[i]; for (int i = 2; i <= n + 1; i++) { for (int r = i; r <= n + 1; r++) { int l = r - i; dp[l][r] = 1LL * (dp[l + 1][r] - dp[l][r - 1] + m) * inv[i - 1] % m; } } vector ret(n + 1); ret[0] = x[0]; vector mul({ 1 }); for (int i = 0; i < n; i++) { vector mul2(i + 2, 0); for (int j = 0; j <= i; j++) mul2[j + 1] = mul[j]; for (int j = 0; j <= i; j++) mul2[j] = (mul2[j] + 1LL * (m - i) * mul[j]) % m; mul = mul2; for (int j = 0; j <= i + 1; j++) ret[j] = (ret[j] + 1LL * mul[j] * dp[0][i + 2]) % m; } return ret; } ```
 Forums Algorithm Matches SRM 723 Div 2 1000