INTRPATH - EDITORIAL

[venkycodes]

this problem tested contestants to extremes

[shoom]

Good point about “\n” instead of endl. This change makes it AC as well. And even a bit faster than printf/scanf (2.23 s vs 2.47s).
https://www.codechef.com/viewsolution/24862468

[l_returns]

I think it’s endl which is causing TLE ??

[ganesh92]

@aman_robotics or any java bros
would u give us some tips on java
for INTRAPATH
my java soln gave tle while cpp passed
https://www.codechef.com/viewsolution/24808106

complexity is same as mentioned in official editorial i.e . logn for queries and nlogn for preprocessing
but still my c++ soln took time 3.7sec whereas java gave tle

You dont need to check logic. Jst see if am doing any stupidity which is increasing my program’s exec time
am using Fast IO from geeksforgeeks for taking inputs and StringBuilder for output
also tried BufferedWriter, PrintWriter

[aman_robotics]

JAVA’s ArrayList and HashMap(to be specific the whole java.util package) are really inefficient, its not always amortized O(1) operation. I see that you are using extensively these classes in your code(e.g. using HashMap for child count which could have had been easily replaced with arrays).

Anyways you can have a look at my solution

[gjaiswal108]

That is because even after using ios_base endl flushes the output everytime it’s encountered, that’s why it makes the total time slow for a solution with huge number of outputs.
So to make program use ios_base, it fasten the input process even better than scanf, and also use ‘\n’ instead of endl;

[kishan2343532]

can anyone please provide python solution .

[wingman_7]

Can someone please explain the 3, 4, 5 and 6 question in more detail ?

[idgaf_99]

If anyone’s still stuck, look at my explanation

[wingman_7]

Thanks a lot, it’s a great explanation

[jus_a_noob]

I did it using binary lifting for each query(besides lca), so it cost me logn per query.

[wingman_7]

++ count of paths passing through c1c_1 and c2c_2 and uu.

Why are we adding the number of paths passing through c1 and c2 and u ??? Can someone please explain with the help of an example ?

[adi_tdkr]

@teja349 If possible can you please add pictures for visualisation in editorial.

[prakhar17252]

Only cin.tie(NULL) works the same way as both statements. cout.tie(NULL) is redundant if the former is used.

[adi_tdkr]

@teja349 Waiting for pictures editorial is still not clear without pictures

[knakul853]

see his explanation

Unofficial INTRPTH Editorial/Explanation

Problem : INTRPATH (JUNE 19) Problem Link : https://www.codechef.com/problems/INTRPATH Prerequisite : DFS , LeastCommonAncestor. Before starting I would like to give an overview of problem. Given 2 nodes (Src and Des) , we have to find the total number of paths which will contain only 1 node common with the path from Src to Des. Here we will assume that the tree is always rooted at node 1. Also for every node across the tree we will find Lvl[N], Size[N], Par[N] which will store the Level, Si…

[wingman_7]

You mean that using cin.tie(NULL) is same as using both the statements cin.tie(NULL) and cout.tie(NULL) ?
we just need to use cin.tie(NULL) because it will work for both whereas cout.tie(NULL) won’t work for both ?

[saurabh1402]

I was writing the solution in JAVA. It was getting TLE. So, I commented all of my logic just reading the input and its still getting TLE issue. What is the wrong with JAVA goin on in CODECHEF.
https://www.codechef.com/viewsolution/25435529

[aman_robotics]

For each query, you declare a boolean array of size N. Complexity = O(NQ).

[anon51380106]

I cannot see the tree image which explains 6 questions paths, i am unable to understand it like this, what should i do?