chrome's blog

Topcoder Single Round Match 671
By chrome, history, 9 years ago, translation, In English

Hi there!

Tomorrow Today at 18:00 MSK will be held Topcoder SRM 671.

Let's discuss problems after contest.

  • Vote: I like it
  • +151
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2. 500?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It's still challenge phase. As in, not "after contest" — you shouldn't ask yet.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just calculated number of triples on prefix which multiplication gives needed value

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You could write a*b*c=d as a*b=d/c(d/c needs to be integer). So for a pair (a,b) we need to find all pairs(c,d) with d/c=a*b.This can be done in O(n^2) with a proper order.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    very easy problem just store the vaules in map , which will tell us about the number of times that value occurred , then simply 3 nested loops , multiply the numbers in the main vector corrosponding to index in the loop, find the value in map. add the map value to ans; here the code .. http://ideone.com/SO6u9G

    → Reply
»
9 years ago, # |
  Vote: I like it +56 Vote: I do not like it

F*ck TopCoder.

→ Reply
»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Yes

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I submitted a challenge when there are ~10s left, and nothing appears, after the system test this message shows up. That guy finally fail the test

    → Reply
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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!

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
}
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try to use method map.count() and only after it use operator [].

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Er, I have a question about WHY this makes it so much faster. Is the savings on the longlong addition operation that we skip if it is unnecessary? If the item was not found, the map would return 0 and I thought adding 0 would be highly optimized..

      This was the speedup:

      if (m.count(p*LL(v[k])))
	res += m[p*LL(v[k])][k+1];
      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        it's because operator [] insert element if there is no such element in map.

        → Reply