Вы не забыли про контест )))

How to solve div2. 500?

F*ck TopCoder.

Did anyone get "Request time exceeded" when submitting a challenge?

Sorry for long testing queues and timeouts. I hope it won't repeat.

very short editorial

Congratulations for the winners — tourist, Petr, Egor, and snuke. They managed to solve all three problems!

In my opinion C div2 was pretty hard to implement in just let's say 40 min.And also it has some cases.

My idea: dp[i][conf1][conf2]=All the trees cut from matrixes with just i lines and the last line has configuration conf1 as S and E (0=E and 1=S),and conf2 represents what it has been cut and what is avalaible. cnt[i][conf1][conf2]-number of matrixes with i lines that have conf1,conf2 on the last line.

From dp[i][conf1][conf2] I go to dp[i+1][conf3][conf4].But I fix just conf1,conf2 and conf3 because conf4 is the result of cutting(it can't vary)

But for conf2 I need to represent it as a number in base 3(0-available,1-cut,2-unavailable).

The complexity is O(H* 2^7 * 3^7 ^ 2*7). Also there are some constants,idk if they can be erased,but the constant is at least 7,so it doesn't pass TL.

Does anyone has a better idea(faster),and easier to implement?

Hi, I don't think my solution is the intended one, but it passes all test cases except one in the system tester. The test data is http://www.textsnip.com/5ycpyz

On my PC I get the correct answer of 354.

On TC tester I get this:

terminate called after throwing an instance of 'std::bad_alloc' ** what(): std::bad_alloc**

Any thoughts? I used that unordered_map for the first time today, it's supposedly a hash_map so it gives O(1) lookup. With regular map, I get timeout on earlier examples.

It's a nice problem and a bit different from usual TC problems. Required more algorithms/data structures knowledge and less cleverness. (I'm not clever :-)).

Thanks!!

typedef long long LL;
long long count(vector <int> v) 
{
	int n = v.size();

	unordered_map<LL,unordered_map<int,int>> m;
	for (int i = 0; i < n; i++)
	{
		m[v[i]][n] = 0;
		for (int j = n-1; j >= 0; j--)
		{
			m[v[i]][j] = m[v[i]][j+1]+(v[j]==v[i]);
		}
	}
	LL res = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = i+1; j < n; j++)
		{
			LL p = LL(v[i])*LL(v[j]);
			if (p > 1000000) continue;
			for (int k = j+1; k < n; k++)
			{
				res += m[p*LL(v[k])][k+1];
			}
		}
	}
	return res;
}