chrome's blog

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

Hello!

Tomorrow at 05:00 MSK will be held Topcoder SRM 650.

Let's discuss problems after contest!

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

»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Will there be TopCoder Tshirts for top performers in this one?

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

How was 500 solved?

I had an idea that each new edge created a cycle, so by bashing all edges in at least one cycle in the graph to check if removing some set of them you could find the answer, but I ran out of time :(

Does this work? (and is there a better cleaner way o.O)

EDIT: Yeah this will time out, for some reason I was thinking the graph would be at least close to a tree, but possible modifications and optimizations might make it work.

EDIT 2: See below for a working version of this by yzyz :)

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Though I did not solve the 500, your above approach almost surely will TLE in some test data. One example is just when the graph (with the added edges) is just a big cycle with some extra edges in between. Then all edges (2h + 1 of them) are in a cycle, so you have to bash all of them. Since you have to check for every triplet of edges, this takes probably too long. Not sure how to reduce the number of edges that you have to check.

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

      Hmm yeah I didn't think about that oops. Well you can also do this:

      1. if h>2 there must be some nodes with degree 1, which must be leaves if the answer is affirmative (at least 2^(h-1)-6 of these). You can take out those and their only neighbor (which must be their parent if the answer is affirmative) which already divided the number of nodes by 4 (approximately).

      2. in the rest, there must be a lot of nodes with degree 3. check this first.

      That definitely reduces it a lot, not sure if it's enough to avoid TLE though. (also it's a huge pain to code so idk...)

      EDIT: Okay yeah I don't think this works in time even with the above 2 points, but a countertest is hard to create especially if no one thought this solution might be attempted so it might pass anyway lol. A good countertest might have a ring with additional edges connecting i,i+2 in the ring, plus a little bit to satisfy point 1.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +21 Vote: I do not like it

        Here's a simple solution without any corner cases (except for h=1, but that's trivial):

        Note that each extra edge must belong to at least one cycle. Moreover, if the answer is "Correct", then the length of each cycle can't be greater than NUMBER_OF_EXTRA_EDGES * 2 * h. So we can recursively find any cycle, check that it's length satisfies the above condition and iterate over all its edges. In this way we can fix three edges that we want to remove. Now we have a tree and we need to check whether it's full binary tree, which can be easily done in O(N). The overall complexity is O(h^3 * 2^h).

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +42 Vote: I do not like it

        My solution without any special cases looks very straightforward.

        You try to use every vertex as a root of the tree. We want to build a tree layer by layer. Whenever we consider a vertex we want to add 2 its children to the tree. If there are more than two adjacent not used vertices, you try all pairs and mark not used edges as "wrong" and go to the next vertex of the tree.

        If at any moment you have marked more than 3 edges as "wrong", you stop the process. I think it can be proved that this solution has time complexity O(n2), where n is number of vertices of a tree.

        Here is a link to the solution.

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

          yes, this approach is O(n^2) because you will try every combination of the wrong edges but you will have at most 3 wrong edges (if you have more then this configuration of the tree will never be a tree). In the worst case these 3 wrong edges will be between the middle nodes which means that you will try at most 4*4*4 combinations (if there are 3 nodes with more than 3 edges), or 4*5 combinations (a node with 4 edges and a node with 5 edges) or 6 combinations.

          So, i think in the worst case it will run in 4*4*4*(N^2)

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

    My original solution was similar to what you described and failed system tests, but I solved it afterwards. The number of edges in a cycle is small if there is a solution, so we can just automatically return "Incorrect" if the number of edges we have to check is greater than 60.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -37 Vote: I do not like it

Great, I was 2nd before systest, but my 900 failed because of segfault, because I iterated through n edges, not through n-1 >_>... Last time I could have been 1st and this time I could have been 2nd in SRM, but nooo :<.

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

It's quite coincidence; sorry_dreamoon/qwerty787788 got second place in Codeforces and Topcoder

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

Can anyone explain some short solution to 900 (like this one)? During the contest I've came up with quite complicated dp, which I couldn't implement in time so it was a surprise to me that there exist such a short solution.

cc Endagorion

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

    Suppose we know which vertices contain keys and which don't. How do we determine if we can get stuck? Alter the problem a bit: suppose we have enough keys from the start, and we want to unlock some edges while collecting all available keys in such a way that finish is not reachable from the start, and the most keys are wasted (that is, the difference d between the resulting and the starting number of keys is as small as possible); we can stop unlocking at any moment ignoring the fact we have enough keys. This task can be solved using subtree DP: suppose that the root is starting vertex, then for each unlocked edge we must simply add its d to our answer, and unlock only such locked vertices that make our answer better, also account for the key that the root might contain; put dn - 1 = ∞ to forbid unlocking the finish vertex. Now, we can get stuck if and only if d0 ≤ 0.

    To count the distributions compute Dv, k — number of distributions in the subtree of v such that dv = k. Recalculation is straightforward: process children one by one, and consider each combination of values of k for the processed part and for the child.

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

      Hah, nice. On the very beginning of my thought process I observed that we can freely move within parts with no edges locked, so in fact we 'should' compress vertices and later use some Newton symbols and coded this using this compressed tree, but of course my code was longer and modulo some stupid segfault (which could have been prevented by using flag -D_GLIBCXX_DEBUG) I also made it work. Here is my code: http://community.topcoder.com/stat?c=problem_solution&rm=325215&rd=16314&pm=13579&cr=23113968

      Because of few unnessecary debugs, resizes and changing input it looks even longer than it should, so difference between our codes is not that big as it seems, but I have to admit that I did a tradeoff between bit easier thought process and longer code (which I don't like to do : p).

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

        Yeah, early version of my solution involved compressing the tree you described, but I was too lazy to write another DFS, so I made the DP do all the work. Spent quite much time in debugging too.

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

      Do you know how to prove that the task of computing Dv, k breaks into independent subtasks Dwi, k for v's children? Although I know that this solution is correct, it's not obvious to me why we can treat these subtrees independently (i.e. why we don't need to go from one subtree to another multiple times).

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

        If you assume that you already have an infinite supply of keys at the beginning (as Endagorion did), the order you unlock the doors doesn't matter: the difference between keys earned and keys collected will be the same in the end.

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

          But how can we be sure that we won't end up in some impossible situation with that assumption?

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

            We can't. The point is that assumption can only make reaching the finish easier, not harder, so you know that if d0 ≤ 0 and you follow the same path as the infinite-supply guy you will definitely get stuck at some point (maybe before the infinite-supply guy gets stuck, but you'll still get stuck anyway).

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

              Gotcha! Then I have the opposite question: how to prove that if the infinite-supply guy doesn't get stuck, then the limited-supply guy can't stuck as well?

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

                OK, let me stop being lazy and give the full proof this time:

                Let I be the set of paths walked by the infinite-supply guy and L be the set of paths the limited-supply guy can walk. Clearly, . d0 is the minimum value of d (difference of earned keys and spent keys) for all paths in I.

                • d0 > 0: All paths in I have d > 0. As , this means all paths in L have d > 0 as well, so it's impossible to run out of keys.
                • d0 ≤ 0: Some path in I has d ≤ 0. This is actually the hardest case, because we have to prove some path in L doesn't reach the exit as well. The way to construct such a path is to follow the I path as far as you can, and you will get stuck at some point.
                → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        As I said above, when compressing tree I did a tradeoff resulting in an easier thought process, so I will use it here, because it's pretty straightforward to classify trees in which we may get stuck.

        So compress the tree. Firstly cut from the tree subtree rooted in compressed vertex which contains original vertex n-1 and completely forget about it (but don't forget to multiply answer in the end by 2number of original vertices in this cut subtree - 1). Let bad subtree be a subtree containing root such and containing less keys then its number of vertices (compressed). It is obvious that if there exists bad subtree we can get stuck unlocking its locked edges and if there is no bad subtree then we can always unlock one more edge.

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

for problem 1000 Div2 this is my solution:

http://ideone.com/SZc8gi

I thought if the extra edge was a self loop or a duplicate edge between two nodes then I will not add it to adj list or degree count

then I'll dfs over the graph to find the only edge that is not a bridge, because it a binary tree right ??

and at the end the root of the tree should have degree if 2 and the leaves should have degree of 1 and there should be 2^(h-1) leaves;

so what is wrong with my algo or soultion.

→ Reply