Hi there!
Tomorrow Today at 18:00 MSK will be held Topcoder SRM 671.
Let's discuss problems after contest.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hi there!
Tomorrow Today at 18:00 MSK will be held Topcoder SRM 671.
Let's discuss problems after contest.
Name |
---|
How to solve div2. 500?
It's still challenge phase. As in, not "after contest" — you shouldn't ask yet.
I just calculated number of triples on prefix which multiplication gives needed value
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.
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
F*ck TopCoder.
Did anyone get "Request time exceeded" when submitting a challenge?
Yes
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
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!!
try to use method map.count() and only after it use operator [].
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:
it's because operator [] insert element if there is no such element in map.