RBTREES - Editorial

editorial
, , , , , , ,
24

Someone please give it a look.

1 Like
25

https://www.codechef.com/viewsolution/37117273

i m getting TLEā€¦ can somebody help plzā€¦

1 Like
26

can someone please explain me how the ans is going to be calculated? We have to add distances between the nodes but we in tutorial where are we adding those distances?

1 Like
27

In the editorialist solution the part where ans+=excess[u]+req[u], that is where we count the number of nodes for which we travel the edge from u to its parent.

1 Like
28

I guess in your recursive function you are passing string s as pass by value and as its size can reach O(N) and your recursive function is called O(N) times, your algo is taking O(N^2). so globally defining it or passing it by reference might fix the issue of TLE

1 Like
29

Editorial is very nicely written got each point ā€¦ thank you

3 Likes
30

My code is getting WA on codechef but the same code got accepted on csacademy.com

Either CSAcademy has weak testcases or there is something wrong with codechef.

PLEH !!

code accepted at csacademy.com

code getting WA at codechef.com

2 Likes
31

Thanks for going through my messy code and I could never realize that issue. It went from TLE to WA now. Could you help haha? I am also trying to figure out the issue there. CodeChef: Practical coding for everyone
EDIT: Thanks @psychik I figured it out and got AC. Thanks for pointing out that pass-by-value mistake. It is something I could never figure out.

2 Likes
32

Maybe you could respect the team for their efforts and rather not disrespect them for a genuine flaw they somehow missed! ā€œRespect karke dekho acha lagta hā€¦ā€

6 Likes
33

can you pint out what is the mistake here in this code ?CodeChef: Practical coding for everyone

1 Like
34

Hi,Can anyone please explain what actually these two lines are doing. (From editorialistā€™s code).

excess[node] = (parity[node] == prty);
req[node] = (color[node] == 0);

3 Likes
35

If anyone want my clean implementation. I didnā€™t participated yesterday but solved this cute problem today! Also I wonder that how to solve if the edges will be weighted and swap operations are of various costs. That problem would have been very good and may match div1 C level.
Link to cute problemā€™s cute submission!

37129076

4 Likes
36

excellent editorial ā€¦thanks!

1 Like
37

put & in front of s in function solve

1 Like
38

Thanks. :slight_smile:

1 Like
39

Is there any concrete proof to why the minimum operations to swap is equal to distance between the nodes ?
Considering the following case ->
1 0 0 1 0 1 1 0
If we start to swap from the end till the first and then second to last, we get
1 0 0 1 0 1 1 0 ->1 0 0 1 0 1 0 1 -> 1 0 0 1 0 0 1 1 ->1 0 0 0 1 0 1 1 ->0 |1 0 0 1 0 1 1 (4 swaps)
0 |1 0 0 1 0 1 1 ->0 |0 1 0 1 0 1 1 ->0 |0 0 1 1 0 1 1 ->0 0 0 1 0 1 1 1 (3 swaps)
Though it is same as the distance between the first and last, but I am not able to find any proof.

40

I saw this accepted solution in python :accepted sol

After Understanding what the code was doing, I commented one line of it .
And Now its giving WA. Iā€™m unable to understand why this is Happening.
Edited Code(not accepted :frowning: ) : Commented Code

Explanation Of Why I commented the following Lines:
line 64 : As we didnā€™t have to store the parent of a child, this information was of no use

If there is any flaw in my understanding plz let me Know, If not then what is the edge case.

What is the edge case the code is failing on.

Plz Help !! @psychik
Thanks in Advance .

41

Can you please explain your solution

42

If I am not wrong, you commented out line 50. Hence not marking the visited nodes.

43

Thanks for Going through the code @dev_shah_123.

Line 50 -> # finished[start] = True
Above line marks those nodes whose dp values have been calculated
We dont need this as already discussed in previous comments Explanation.

Line 32 -> visited[start] = True
Above Line is not commented , it marks those nodes which have been visited.