AlexDmitriev's blog

By AlexDmitriev, history, 8 months ago, In English,

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

UPD: you have 10 more minutes to register

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

»
8 months ago, # |
  Vote: I like it +104 Vote: I do not like it

How to solve any problem XD?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    I passed 250.

    So, how to solve any problem?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    250: greedy

    500: bruteforce with memoization and treating isomorphic trees as identical

    I suppose it is the worst contest of THAT level.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      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?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        How to prove 250?

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 2   Vote: I like it +51 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it +20 Vote: I do not like it

            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).

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it +19 Vote: I do not like it

              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.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 4   Vote: I like it +18 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              If perm=id my algo will find solution, right?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +59 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it +23 Vote: I do not like it

            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).

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it +36 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 months ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                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.

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it +33 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 months ago, # ^ |
                Rev. 2   Vote: I like it +23 Vote: I do not like it

                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).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months ago, # ^ |
                    Vote: I like it +20 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months ago, # ^ |
                    Vote: I like it +48 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months ago, # ^ |
                    Vote: I like it +11 Vote: I do not like it

                  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).

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +28 Vote: I do not like it

          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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      How do you bound number of states in 500?

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      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).

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        Hmm, to be honest they are not totally 'unexpected'.

        There are few ideas to speed up:

        1. combine isomophic trees
        2. remove trees with size = 1
        3. remove trees with size = 2 (if there are 2 of them, remove both and answer += 1)
        4. 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.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +94 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it +18 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it +82 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 months ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it

                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 :)

              • »
                »
                »
                »
                »
                »
                »
                »
                8 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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. :)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months ago, # ^ |
                    Vote: I like it +10 Vote: I do not like it

                  To me, these two comments represent the difference between ideas and pruning.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months ago, # ^ |
                    Vote: I like it +13 Vote: I do not like it

                  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!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

»
8 months ago, # |
  Vote: I like it +50 Vote: I do not like it

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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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)

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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 :)

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        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

        Unable to parse markup [type=CF_TEX]

        .
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      And why does it gives a sequence of steps?