### AlexDmitriev's blog

By AlexDmitriev, history, 2 years ago, ,

Tomorrow, 16:00 UTC (well, at least if calculated correctly)

UPD: you have 10 more minutes to register

•
• +67
•

 » 2 years ago, # |   +104 How to solve any problem XD?
•  » » 2 years ago, # ^ |   +29 I passed 250.So, how to solve any problem?
•  » » 2 years ago, # ^ |   -8 250: greedy500: bruteforce with memoization and treating isomorphic trees as identicalI suppose it is the worst contest of THAT level.
•  » » » 2 years ago, # ^ |   +28 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?
•  » » » » 2 years ago, # ^ |   +20 How to prove 250?
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +51 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.
•  » » » » » » 2 years ago, # ^ |   +20 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).
•  » » » » » » » 2 years ago, # ^ |   +19 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.
•  » » » » » 2 years ago, # ^ |   0 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.
•  » » » » » 2 years ago, # ^ | ← Rev. 4 →   +18 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.
•  » » » » » » 2 years ago, # ^ |   0 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?
•  » » » » » » » 2 years ago, # ^ |   0 If perm=id my algo will find solution, right?
•  » » » » 2 years ago, # ^ |   +28 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?
•  » » » » » 2 years ago, # ^ |   +59 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.
•  » » » » » » 2 years ago, # ^ |   +23 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).
•  » » » » » » » 2 years ago, # ^ |   +36 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.
•  » » » » » » » » 2 years ago, # ^ |   +1 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.
•  » » » » » » » 2 years ago, # ^ |   +33 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.
•  » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +23 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).
•  » » » » » » » » » 2 years ago, # ^ |   +20 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.
•  » » » » » » » » » 2 years ago, # ^ |   +48 Anyway, do you really want to take the risk on 250? 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.
•  » » » » » » » » » 2 years ago, # ^ |   +11 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).
•  » » » » » 2 years ago, # ^ |   +28 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.
•  » » » 2 years ago, # ^ |   -10 How do you bound number of states in 500?
•  » » » 2 years ago, # ^ |   +28 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).
•  » » » » 2 years ago, # ^ |   +18 Hmm, to be honest they are not totally 'unexpected'.There are few ideas to speed up: combine isomophic trees remove trees with size = 1 remove trees with size = 2 (if there are 2 of them, remove both and answer += 1) remove trees with size = 3 (there are 2 types trees with size = 3, details see my code) We can count the number of states by this dp: dp[0] = 1 dp[i] = 1 + max(dp[i1] * dp[i2] * .. * dp[ik]) where i1+i2+..+ik = i-1 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.
•  » » » » » 2 years ago, # ^ |   +94 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?
•  » » » » » » » 2 years ago, # ^ |   +82 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.
•  » » » » » » » » 2 years ago, # ^ |   +5 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 :)
•  » » » » » » » » 2 years ago, # ^ |   0 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. :)
•  » » » » » » » » » 2 years ago, # ^ |   +10 To me, these two comments represent the difference between ideas and pruning.
•  » » » » » » » » » 2 years ago, # ^ |   +13 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!
•  » » 2 years ago, # ^ |   +23 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.
•  » » » 2 years ago, # ^ |   +23 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.
•  » » » 2 years ago, # ^ |   +8 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.
 » 2 years ago, # |   +50 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.
•  » » 2 years ago, # ^ |   +10 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: dp[1][?] = 1, 1, 1, 1, 1, .. dp[2][?] = 1, 2, 3, 4, 5, .. When we remove a rectangle that means the next row will start from a different index, like: dp[3][?] = (0, 0,) 3, 7, 12, .. We can do dfs on this sequence and we can get the answer for all inputs in less than 0.5sec. (Code)
•  » » » 2 years ago, # ^ |   +5 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.
•  » » 2 years ago, # ^ |   +28 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 :)
•  » » » 2 years ago, # ^ |   +10 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.
•  » » » » 2 years ago, # ^ |   +20 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.
•  » » » 2 years ago, # ^ |   +10 And why does it gives a sequence of steps?