Tomorrow, 16:00 UTC (well, at least if calculated correctly)
UPD: you have 10 more minutes to register
Tomorrow, 16:00 UTC (well, at least if calculated correctly)
UPD: you have 10 more minutes to register
| # | User | Rating |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 2 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 4 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
How to solve any problem XD?
I passed 250.
So, how to solve any problem?
250: greedy
500: bruteforce with memoization and treating isomorphic trees as identical
I suppose it is the worst contest of THAT level.
Why? I think 250 is very nice. 500 uses not so common idea that there are not so many trees on 50 vertices. What's wrong with that?
How to prove 250?
We have to put an opening parenthesis to 0-th position in s.
We have to put one more opening parenthesis on positions 0-2 in s.
We have to put one more opening parenthesis on positions 0-4 in s.
...
It's easy to see that we need to pick each of those in such a way that the matching position in t is leftmost possible, because if not, we can swap and everything gets better.
It's interesting that the same idea (except depending on the oddity of n one needed to pick the best position out of the last 1 or 2, then another out of the last 3 or 4 and so on) was used in TCO just last year, and also in Round 3 :) Round 3B medium (and back then it wasn't the first time I saw it either).
I thought that the task was a breeze after applying this idea, and was surprised to be one of the first to submit. It actually took me very little time to see and prove the greedy, but apparently it didn't go this smooth for most people (for example Errichto, who set previous 3B, as well as great amount of people who solved the medium back then, couldn't solve this task).
Hah, indeed there is a similarity. I should have tried to solve Easy and then Med. Instead, for almost full 75 minutes I was fighting with 1000-pointer. And I opened Easy and Med in maybe last 3 minutes, only to read statements. So, you can't say I didn't manage to solve Easy. Though in total I had -25 points in that round so I can't brag much.
Well, I don't know which approach do you mean, but in may solution the key fact is: s0... sn - 1 is CPS iff there are at least one '(' among {s0}, at least two among {s0, s1, s2}, at least k among {s0, ..., s2k - 1} and n in total.
I believe this statement is oblivious.
My solution: going from left to right, trying to put '('. If there are some suffix of second string with more '(' than ')' (initially all characters are ')'), than we cannot place '(' now. Then check first string to be good.
Proof:
Let's assyme that solution exists but we didn't find it. Fix solution with longest prefix same as in our string. Let our string be S, solution string be T, the strings after applying permutation are S * and T * Let's find the leftmost position where strings S and T are different. We'll call it p, and corresponding position in S * is p * . The only possible situation is S[p] = '(' and T[p] = ')'. Now I want to construct solution with longer prefix same as in our string. Let's find the rightmost ')' in T * such that it is to the left to p * and corresponding position in S is to the right to p. Such ')' exists because we allowed S[p] = '('. Now if we exchange T[p] and the ')' we find, it will be a solution with larger prefix same as in our string.
And what if: perm = id, S = ((( ( ..., T = ((( ) ..., you don't have any other ')' in T* to the left of p* except for p* one. What have I understood wrong?
If perm=id my algo will find solution, right?
250 is awful problem because you don't have to prove greedy to get AC. It is obvious greedy but I spend ~25 min trying find another solution or prove it. Maybe I am so stupid.
There ARE many trees on 50 vertices. At least 250. Probably there are not so many ways to choose non-intersecting subtrees of the given tree. Again, if we don't compress isomorphic trees, there are many. Can anybody prove it? And again, this solution is obvious. All you need is to believe. Is it really good property of competitive programmer?
I think saying that those solutions are obvious is an over-statement (or trolling). There are many possible greedys in 250, and most of them don't work. There are several possible ways to reduce the state space in 500, and only the most accurate one works. In both cases, if you just "believe" you'll most probably believe in an incorrect solution before seeing the correct one. So instead of believing, one has to try to get some proof (more likely for 250) or at least an intuitive argument (more likely for 500), and coming up with proofs and intuitive arguments is a valuable quality in my view.
And what is your intuitive argument for 500?
Yes, when you are proving your solutions you will be better ON AVERAGE. But when just 4 people can guess the right greedy and win, I have no chance to be faster if I will prove my solutions (exactly what has happened).
It's a square-root type of argument: either we have many small trees, which can be only of a few different types, and thus we'd have only a few states, or we have a small number of trees, and then some_num**num_trees is not a large number.
During the contest I've considered a few cases which I thought would be boundary between the two situations, and in all cases the number of states seemed very low, which gave me confidence that even if there are slightly worse cases the solution would pass. I.e., if we have 10 chains of length 5 each, then we have just C(15, 5)=3003 states.
Just checked the testcase that took my solution the longest — 0.6s — and it has 45651 states (where state also includes who's turn it is, so in the above example there are at most 6006 states). So my examples were roughly 10x off the worst case.
For the second part of your reply: I'm sorry that you couldn't qualify this time :(
But note that had your 500 passed, you'd require just one +50 from challenges to qualify, so I think the proving strategy did stand a decent chance today. At least two qualifying people (myself and yosupo, as we see from comments below) did prove 250.
I'm not complaining about me not qualifying :)
I just say that when so small amount of participants qualifying it may be good idea not to prove your solution. And such a greedy helps those who use this 'strategy'.
About my 500 — I was looking for good solution all the time and only in last 7 minutes start to write something stupid (nothing about isomorphic trees).
I think all participants who use Petr's approach know how to prove it since it's obvious. Other correct greedy solutions are unexpected and not so intuitive in my opinion (How you check you can put a '(' matters), so it's unfair to call it an awful problem. Anyway, do you really want to take the risk on 250?
Imo 500 is not good though. First of all it's 500. People who have no clue on it will just guess, and it's not hard to guess the solution--greedy or brute force. "Choose brute force, make it as fast as you can" seems enough to pass.
In a regular round, you absolutely wouldn't. But this is TCO, in which coming in 5th is the same as coming in 150th. If you evaluate your chances of qualifying the "legit" way to be fairly low, gambling might actually be the sensible thing to do.
Yes, I agree with your point — not proving could certainly help one squeeze in to the top 4. My point is that it was not the only viable strategy, and it's unclear if anybody from top 4 actually used it (for 250).
I was trying to solve 250 for more than half an hour and I didn't come up with that particular greedy and I think that Petr put it that way it is completely obvious how and also why does it work. However I also don't like 500 at all.
How do you bound number of states in 500?
At least 1000 was very nice.
According to cgy4ever those solutions for 500 were unexpected, he has a provable solution (but his solution is also exponential).
Hmm, to be honest they are not totally 'unexpected'.
There are few ideas to speed up:
We can count the number of states by this dp:
So without all of these optimization, dp[n] is about O(2^n * poly(n)).
After add (2) we will have dp[1] = 1. So dp[n] will be about O(2^(n/2) * poly(n)).
Afrer add (3) it becomes O(2^(n/3) * poly(n)), and so on.
It is hard for me to find worst test cases for (1), what we did is running Simulated Annealing for few days.
So after adding such data we will have: 2+3+4 (or 2+3 with a good implementation) can pass, 1+2 can pass, and with 1 alone it will be very hard to pass.
Note that if we totally don't know (1) then much more of submitted Medium will pass.
Then this task doesn't look good. It is very easy to predict that someone puts whatever prunings he comes up with and passes without knowing why.
Medium of R3 is one of the most important problems in TopCoder and you should keep the best problem for this slot (and don't try to find something two weeks before the contest). Is this really the best task you have?
Well, but why do you think the Hard is nice? It is also very easy to predict that someone puts whatever ideas he comes up with and passed without knowing why. For example, I still don't really know why my solution can work. :P
We started testing about 4 weeks ago, and I have few other nice and more traditional tasks for Medium. Here 'traditional' means that it has one single observation needed and the solution is neat.
There are some reasons behind using this one (and Hard, which is also not 'traditional') in 3A:
It is very challenging. One can easily stuck in finding greedy or other polynomial solution for very long time. There are a lots of wrong solutions one can come up with.
It is neutral and fair to most people. You don't need to be good at a certain area (like probability, math, flow, or has a good understanding of a certain algorithm). AFAIK there is no similar tasks like it so you will not have an advantage by solving similar tasks before.
It tests more strategically decisions and a variety of skill sets: you need to find which direction to go and which specific idea to try, and you need to analyze and predict how well can it work, you need to implement well.
At least the result is not far from what I could predict and I don't regret about using this task. The only thing looks bad in the result is that eatmore gots 5-th place.
Are you talking seriously? Coming up with ideas is a great thing, but coming up with prunings is... well, ICPC-ish.
Also note that eatmore proved the correctness of his solution for d1 hard during the contest.
I found a bit interesting thing.
Voting for this remark will be ignored!
I guess they are protected by admin because this is interesting discussion :)
What do you mean by 'pruning' and 'ideas'? You can't come up with pruning with nothing -- you need ideas. So 'pruning' is a subset of 'ideas'.
And for eatmore's solution: note that he used the word 'somehow', so although he verified his solution, he probably still don't really understand why it worked.
Anyway, good luck in Round 3B and I hope you can enjoy that round. :)
To me, these two comments represent the difference between ideas and pruning.
To be honest I enjoyed 3A too (my first comment was a positive one) — I'm saying this just because I saw the discussion here after the contest and I wanted to write my opinion as a former admin.
Anyway, after you became the only admin, I liked majority of problems in TopCoder. Thank you for keeping the good quality!
I solve 250 by maxflow (and some edges have under limit of flow). This picture is graph of sample1.
This solution is very stupid. But not need to proof.
The flow solution is not stupid. I know this task can be solved by flow first and wanted to use it as 500p in future SRM.
Then I noticed it can be reduced to greedy, so it looks like a good task for 3A's Easy.
As a matter of fact, merely constructing this flow graph needs the same key observation as the greedy solution, so it's not that stupid of a solution.
My solution to Topological Ordering:
First, notice that if there is a solution for n = a and n = b, they can be combined to produce a solution for n = ab. So, it is necessary to solve only for prime n. Then, find solutions for every Fibonacci number: graphs where there are edges from i to i + 2 and i + 3 for all i. Then, generalize this as follows:
For each graph, consider the tuple (a, b), where a is the total number of topological orderings, and b is the number of such orderings that a certain fixed vertex is the last in the ordering. In the Fibonacci solution above, adding a vertex transitions from (a, b) to (a + b, a) (this is how it can be proven that the number of topological orderings is in fact a Fibonacci number). By adding two vertices, it is possible to make a transition from (a, b) to (2a + b, a). Similarly, by adding three vertices, it is possible to transition from (a, b) to (3a + b, a) (the exact arrangement of edges is left as an exercise to the reader). Somehow, these transitions are enough to generate all prime numbers below 32767, and the resulting graph never has too many vertices. Moreover, it is possible to generate it in such a way that for each vertex, at most two edges are added, so the number of edges is also small.
I checked my solution on all possible inputs, and it generates a graph with at most 29 vertices and at most 53 edges. The worst case is n = 24576 = 213·3.
My solution is similar:
Start with 2 chains 1->2->3->4, 5->6->7->8, the answer will be C(8,4). If we add edges between them (like 1->6), the answer will be a bit less. We can count the answer by dp, it is like the way in a 2D grid, and when we add an edge it equals to remove a rectangle.
Another way to see it is doing the dp row by row, so at first we can have:
When we remove a rectangle that means the next row will start from a different index, like:
We can do dfs on this sequence and we can get the answer for all inputs in less than 0.5sec. (Code)
Nice!
I had a very similar idea, but didn't think about trying all sequences for a small size, and instead picked a moderate size (three sequences of length 10, with additional edges from 1st to 2nd and from 2nd to 3rd), and then while the answer is greater add more random constraints, and while it's less remove random constraints.
It timed out on the round, but playing a bit with parameters now I've managed to pass the practice room tests (changed 10-10-10 to 5-10-10).
I have a feeling that if I somehow made the random steps at least a bit more clever, this would pass with ease.
By using a similar observation, it is sufficient to create the number n from the tuple (1, 1) with small number of two types of operations: (a, b) - > (a, a + b) and (a, b) - > (a + b, b).
Choose an integer x such that x is coprime to n and x is close to n / (goldenratio). Consider the euclidean algorithm for gcd(n, x). This gives a sequence to create n in at most O(logn) steps. So, any integer n can be created with O(logn) vertices and O(logn) edges.
Now this problem looks even more interesting :)
Oh, this solution is very nice!
So what is your way to construct (a+b, a) and (a+b, b) with only a few (O(1) in average) edges? I know a simple solution but it will end up with O(logn) nodes with O(logn^2) edges.
Draw two chains: x1 - > ... - > xn and y1 - > ... - > ym. Let a be the number of topological orderings such that xn is the last, and b be the number of topological orderings such that ym is the last.
If you want to construcy (a + b, b), add a vertex xn + 1 and two edges xn - > xn + 1 and ym - 1 - > xn + 1.
And why does it gives a sequence of
steps?