JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
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 path
2) 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-3

when 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%7D

The 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=14738

Which 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<int> interpolation(vector<int> x, int m) {
	int n = x.size() - 1;
	vector<int> inv(n + 1); inv[1] = 1;
	for (int i = 2; i <= n; i++) inv[i] = 1LL * inv[m % i] * (m - m / i) % m;
	vector<vector<int> > dp(n + 1, vector<int>(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<int> ret(n + 1); ret[0] = x[0];
	vector<int> mul({ 1 });
	for (int i = 0; i < n; i++) {
		vector<int> 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;
}
RSS