DRGHTS-Editorial

editorial
, , ,
21

Thanks for the explanation … that was one big mistake.

1 Like
22

@honeyslawyer : The main idea behind my solution was the same. Use BFS, Store parent and traverse recursively till u reach root or a node that already has a draught

In fact after using fast I/O my solution became the best one. I guess this BFS solution was better than the DFS solution!

23

@Eu1er : Stack Size will not give u the right answer, You are missing a key point here. Imagine 3 rooms with window side by side 1-2-3, with 2 edge (1-2,2-3) now suppose all 3 have window and u start from 1. Now u go to 2 and ur stack size is 1. so ans=1. again u go to 3, your stack size is 2. so ans becomes 3. But the actual ans is 2 only. You need to empty your stack after discovery of a window.

1 Like
24

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

25

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

26

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 …

27

How to check this condition ?!

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

  return (cnt >= 2);
}
29

My solution was accepted, I made a BFS forest(Root of each tree may or MAY NOT be marked) and counted number of nodes between two nodes with open windows, This had two cases a) two nodes were in two different sub trees for which i found the common ancestor and marked all the nodes between the two marked nodes and the common ancestor b) The two nodes lie one above the other in this case i simply marked the nodes which came on the way.

Here is an efficient implementation of the above : http://www.codechef.com/viewsolution/3382545

30

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… -_-

31

If anyone gets time could they please look at my code and tell me why I’m getting wrong answer
http://www.codechef.com/viewsolution/3453438
Thanks.

32

Hmm, I’m getting a wrong answer but can’t seem see, why, some basic tests locally seem to pass, anyone have a some more test cases that I could run my code through?

Here is my current solution that is failing:

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

Edit- Here is another version but still failing:
http://www.codechef.com/viewsolution/3471976

I’m using n*n-1/2 for calculating first answer by checking sub-trees for all “1” nodes.

The second answer I’m counting all leaves with no open windows and subtracting from the number of nodes, with a special case being 1, which I return 0.

Or am I mis-understanding the 2nd question, i.e. there is still a draught even if the room has no openwindow as a long as it is on the path of rooms that have openWindows, even if those rooms are not direct neighbours? So they can be few nodes away?

33

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:

34

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.

35

6 1
1 1 1 1 1 1
1 2

ans should be 1 2, your answer is 1 6.
There must be atleast two open rooms for a draught to pass (as per the question).
Hence ,in this test case , rooms numbered 3,4,5,6 don’t have a draught passing through them.
may be change the base case. :smiley:

36

Man I feel so sad :frowning: I really thought I had it covered, disjointed tree and randomly ordered links. Although my five test cases (including the two you provided, thanks!) pass, my submission still says wrong answer.

Hmm I wish the authors would provide a good set of test cases for us to run our code against.

If anyone spots where I went wrong, I would be grateful!
http://www.codechef.com/viewsolution/3477643

37

I solved this problem using a DFS that returns a parameter which tells whether the current node is to be included or not for the answer of 2nd part of the question… The description of my solution is given here

38

Guys can someone please tell me why my solution is being rejected:

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

I can’t see what’s wrong with it. I’m using the method of counting no of 1-label nodes in a tree for answer to 1 and pruning for the answer to 2.

I would really like to get some closure on this. Is my method of printing the answer somehow not being accepted?

39

plz post the tester’s and setter’s solution asap.

40

Could anyone tell me what the heck is wrong with my solution?

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