insider_pants's blog

Need help to prove my solution of last contest's D question
By insider_pants, history, 5 years ago, In English

The last contest's D question, I came up to a solution which got accepted by I do not have the proof the solution. What I did was, First I did a DFS to give colours to the node(here colours means the parity like in bipartite graphs) and maintain two sets for even parity and odd parity. Now, if i came up to any adjacent nodes which have same colour assigned, I just removed any node from the set, given that both nodes are in the set. Now for the answer, I checked whether the bigger set have atleast K / 2 elements or not. If yes, the print the answer and exit and if not, I did another dfs to find cycles, and print it if its length is atmax k.

Solution

Anyone with some proof or willing to discuss or even hack it will sure help me. Thanks.

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

»
5 years ago, # |
← Rev. 5   Vote: I like it +33 Vote: I do not like it

I hacked your solution, but this is because your dfs2 is actually $$$O(n^2)$$$ in the worst case. I believe you can see generator code for the hack, so I won't describe graph structure (but feel free to ask).

Ancestors, successors and other similar things are in terms of dfs tree

Now about correctness. Actually, you don't delete any node in case of same colors, you delete the ancestor. So, there are two possible cases. If the graph is tree, your algorithm works fine. Assume, it's not a tree. Also, if there is cycle of length $$$\leqslant k$$$, your second dfs will work, so this is not an interesting case too.

Now we have a graph, which is not a tree, and all cycles have length at least $$$k+1$$$. So, if a node with level h has a succesor (not counting children), this successor has level at least h + k (counting from root). Take the leaf with the maximum depth/level (the lowest one). And go $$$k-1$$$ nodes up. None of these nodes has a successor, which is not a child. So none of these $$$k$$$ nodes will be deleted (since you delete an ancestor in the pair).

Now, if $$$k$$$ is odd, this might not be enough. But in that case, because $$$k$$$ is odd, you will not delete the node with level h - k, where h is the level of the leaf (even if they are connected). And with that extra node it will be enough.

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

    "So none of these $$$k$$$ nodes will be deleted (since you delete an ancestor in the pair)"

    Which $$$k$$$ nodes are you referring to here?

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

      We chose a leaf, and then went $$$k-1$$$ nodes up. These $$$(k-1)+1=k$$$ nodes

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

    Thanks for the explanation. Now, I get that I cannot just simply choose which node to delete. I guess my solutions works by luck. Another thing, Can we have a way to choose which node to delete or just we cannot choose?

    By the way, Thanks for pointing out my mistake.

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

      I don't understand. My point is that your code is correct, but slow sometimes. If you will choose arbitrary node to delete in case of two nodes of the same color, it is probably a wrong solution. But you always choose an ancestor, and this is correct. If you will always choose a successor, I think, it is correct too, and the proof is the same, but we take a root and go $$$k-1$$$ nodes down.

      I also noticed my mistake, but it doesn't change anything. i can be not an ancestor, but a visited child. But in that case, we already deleted a, when we were looking at the same edge from i, so i remains in the set.

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

        IF I delete the successor, not the ancestor, one can still find a test case to give TLE. So my point is that my approach is not wrong, but it's slow as either I choose ancestor or successor to delete, there will be a case such that my dfs2 function is called and dfs2 is O(N^2), which will give tle.

        I said that we cannot simply choose any node to delete and by this I mean, we cannot make choice to delete either ancestor or successor as there might be a case that for one pair, by deleting ancestor, there will be more node remaining in the set and either by deleting the successor, it gives the best answer. So my conclusion is that for finding an independent set, we cannot just simply choose which to delete as my other dfs2 function is quite slow which will give tle, not WA.

        Thanks

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

          Ok, now I get it. But there is an easy fix for dfs2: you don't need to build a cycle to calculate it's length. Just save level (depth) of each vertex. The length of the cycle is level[par] - level[a] + 1.

          This is how I did it: submission

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

            That's a nice fix, thanks mate for the help. Cheers

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

I had a very similar idea to yours. First I root the graph at node 0. I also created these sets of even and odd parity, up to size $$$\lceil \frac k 2 \rceil$$$ but as I'm building them if I found adjacent nodes with the same color assigned then I build a cycle of size $$$\leq k$$$ using these two adjacent nodes. Say the adjacent nodes are $$$x, y$$$ I build the cycle by taking the root to $$$x$$$ path and the root to $$$y$$$ path, and finding the last node that the same in both paths. You can prove that this cycle is length $$$\leq k$$$. If, on the other hand, I manage to create a set of even or odd parity of size $$$\lceil \frac k 2 \rceil$$$ with no adjacent nodes then I'll have my independant set.

→ Reply