DRGHTS-Editorial

editorial
, , ,
21

I used the same approach. I removed all such leaves iteratively :slight_smile: CodeChef: Practical coding for everyone

22

Hm, I think now it’s clear to me…

Why there is not a better test case ? :’-(

23

Rubik’s answer is not n. As stated by @anton_lunyov in the contest “After solving the problem I could assert that draught is passing through the room if and only if this room lies on the path between two different rooms with open windows (regardless of whether it has open window or not). Regarding Furik question, it is clear enough: the pair of rooms should be counted if and only if they are connected and both have open windows.”

1 Like
24

This means a node should be visited only after all its children have been visited.

25

That shows that I’m an ignoramus, I read that comment, but somehow ignored it :frowning:

26

how to check the third case

27

You already have the I() values of all children of a node, just check if there are two or more children have nonzero I() value.

28

Actually the language of problem was very confusing. I also had 28 WA. Then I read this comment and it helped a lot :slight_smile: Thanks to @anton_lunyov

29

Actually i was able to solve it because of @anton_lunyov comment.Before that i interpreted as u @betlista .For me problem statement was confusing.

30

@sambuddha - You did everything right … the only problem(the same i had) is that we forgot to explicit typecast the count to long long which cost me around 20 WA’s … here’s your AC solution which i tried
just modified the tot_count

http://www.codechef.com/viewsolution/3437568

… even though i found the problem i have no clue as to why it happens … if you have any idea please share it with me …

31

count is int and multiplying count by count is an integer that overflows integer value…although you are putting it up in long long variable but count*count is still int

1 Like
32

Thanks for the explanation … that was one big mistake.

1 Like
33

U can do something like 1LL * count * count to avoid overflow!

34

Ohhh I did not notice that at all… Thanks to all of you…

35

First of all thank you for a thought … and yes you are right actually i did emptied the stack … problem with my code was that i did not explicitly typecast the int to long long in (count)*(count-1) which cost me a hell lot of pain and time … my algorithm was right all the way …

36

How to check this condition ?!

37 
bool check(w) {
  int cnt = 0;
  for (u : children(w))
    if (I(u)) ++cnt;

  return (cnt >= 2);
}
38

I wasted 12 hours on this problem… I got my algo and code within 35 mins… The only thing that kept me from submitting was the same int and long long int… I tried everything but it gave me wrong answer… When I read your post and realized I have done the same thing, my code was immediately accepted, and I wanted to kill myself… -_-

39

6 3
1 0 1 0 1 0
1 2
3 4
4 1
Your 2nd solution doesn’t give any output for this case!
ans should be 1 3

Hope it helps! :slight_smile:

40

Brilliant, that helped a lot. I got that test to pass, I assumed the tree was always fully connected.

However, my answer still seems to be wrong:
http://www.codechef.com/viewsolution/3472762

I must be missing some logical step of the problem, any other test cases anyone can provide that I can run the code through? Perhaps my answer to the second approach is wrong of tree pruning. I’ll try maybe a counting method instead.