bluefog's blog

By bluefog, history, 3 years ago, In English,

Submission under review : http://codeforces.com/contest/767/submission/24809891

For problem : http://codeforces.com/contest/767/problem/C

Which cases am I missing? I tried to implement the two conditions as given in the tutorial but the submission fails for test 9 (which is a large one, i cannot debug by viewing the case).

Thank you for your time and attention

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in the editorial it was written:

To check the second option, let's write down all vertices v such that sv = x / 3 and there is no other u with su = x / 3 in the subtree of v

I think, you are not checking this correctly.

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

    Thank you for your reply

    The idea i tried was to take the first node encountered during the dfs which had sv = x / 3 and adding it to a set of candidates and ensuring none of its children were added to the set of candidates. This property gets reset as soon as the dfs returns from this node, so nodes from other subtrees can be added in the set of candidates.

    This way the list of candidates would only have nodes which do not exist in each others subtree and have sv = x / 3. We would find a solution if the set of candidates has 2 or more elements.

    I may be missing something here

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

    Nevermind, I found the case of failure.

    If we go to add the first such node and do not check any of its decedents for this property, we will miss the case where two distinct subtrees of this subtree have sv = x / 3.

    Thank you very much for your insights

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I am also having the same problem ..... getting wrong ans on test case 9 and also my approach is also same. Can you please elaborate the case of failure ?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        7
        0 0
        1 0
        1 5
        3 -1
        3 1
        4 5
        5 5
        

        A testcase which fails on my solution, but answer is 6 7, each subtree having sum 5.