By SecondThread, history, 21 month(s) ago,

# Algorithms Thread Episode 8: Tree Basics

Episode 8 of Algorithms Thread comes out in <90 minutes! This one is a bit more beginner-friendly and covers the following ideas:

• Graph/Tree Diameters
• Binary Lifting
• Tree Flattening with Euler tours

Also, to make sure you have actually learned that stuff, I made a custom Gym set on CodeForces that will last two weeks that hopefully is really good practice for making sure you have learned this stuff. Here is a link to the gym set; it will be available 45 minutes after the video comes out so that people have time to watch the video before starting the set, if they are interested in penalty points. All of the problems in the gym are original to this set (in their flavortext at least, some are simple enough that I'm sure they have appeared in other contests before).

The new gym integration was heavily inspired by Errichto's Matrix Expo set format. Let me know whether it's helpful. I think it might be, but also it's a pretty big time commitment to make it, so whether I keep doing them depends on how helpful they are to people.

If you have any questions or suggestions, feel free to leave them below. I hope you enjoy the problem statements, and I'll leave you all with this:

## Solutions

Update:

• +1924

 » 21 month(s) ago, # |   +50 Really appreciate your effort for helping beginners to learn new concepts and improve!
 » 21 month(s) ago, # |   -7 Looking forward to it!
 » 21 month(s) ago, # |   +66
•  » » 21 month(s) ago, # ^ |   +54 Hey, I understand that you want to make a point, but don't you think tagging them is unnecessary? I believe noone likes to be tagged just to see random people being orzed.
•  » » » 21 month(s) ago, # ^ |   +225 Guys, please listen to Sexpert, don't tag anyone unnecessarily.
•  » » » » 21 month(s) ago, # ^ |   -47 Stop tagging Sexpert, She doesn't like it
•  » » » » » 21 month(s) ago, # ^ |   +60 Hey, I understand that you guys want to make a point, but don't you think tagging Sexpert is unnecessary? I believe no one likes to be tagged just to see themselves being joked about by random people.
•  » » » 21 month(s) ago, # ^ |   -10 I fully support condemnation of this practice. Looking at a notification just to see myself being tagged unnecessarily by random people is sure to be tiring.In this case, however, I do not think it is a harm. It is a blog written by the "orzed" person, and he (assumingly) reads and enjoys comments here.
•  » » » 21 month(s) ago, # ^ |   +211 No, no, why are you saying this? I'm pretty sure that neugis tagged me for a really good reason.
•  » » » 21 month(s) ago, # ^ |   +64 Or SecondThreaded
•  » » » 21 month(s) ago, # ^ |   +184 For the record, I like being pinged so that I know when people are talking about me. At least, I certainly don't mind.
•  » » » » 21 month(s) ago, # ^ |   +48 SecondThread We have company! Amazing videos, please continue.
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   -19 Nobody: Sexpert: Wait. what r u talking about?
 » 21 month(s) ago, # |   +104 Wait..... How come this is on the frontpage of CF?
•  » » 21 month(s) ago, # ^ |   +139 Wait, I have no idea...
•  » » » 21 month(s) ago, # ^ |   +26 Looks like SecondThread's contribution will become highest on Codeforces shortly :)
•  » » 21 month(s) ago, # ^ |   +20 probably a combination of post time and up-votes, plus SecondThread is getting more recognition in this community for good contents :)
•  » » » 21 month(s) ago, # ^ |   0 yap
 » 21 month(s) ago, # |   +4 Errichto and Thread are changing the learning game istg.
 » 21 month(s) ago, # |   +94 At this point, since everything's already prepared for it, they might as well add your stuff to EDU
»
21 month(s) ago, # |
+198
##### Spreading CP knowledge!
•  » » 21 month(s) ago, # ^ |   +22 What is the problem with Codeforces EDU? I enjoyed all of their lessons so far. They are all doing a great job. No need to compare 3 great resources.
•  » » » 21 month(s) ago, # ^ |   +6 I'm not criticizing EDU or saying it's inferior to others.I'm talking about the quantity of videos/resources or more like time taken to make new educational videos.
•  » » 21 month(s) ago, # ^ |   +341 Fortunately, it's not a competition. It's more like we push one racing car together (because the community gets the sum of all resources).Also, there are people like Mike or awoo who actually do significantly more, it's just not in form of videos.
•  » » » 21 month(s) ago, # ^ |   +132 Sexpert just told you not to do that.
•  » » » » 21 month(s) ago, # ^ |   +3 LOL
•  » » » » 21 month(s) ago, # ^ |   +40 Yeah, listen to Sexpert, no unnecessary tags.
•  » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Don't spam.
•  » » » 21 month(s) ago, # ^ |   0 Well said.
•  » » 21 month(s) ago, # ^ |   0 If they are ferraris , then mike has to be the mercedes , it's the hybrid era
 » 21 month(s) ago, # |   +10 Thanks, we will try our best to learn new and interesting concepts.
 » 21 month(s) ago, # |   +11 Loved the new format ! This helps gain much more confidence in the covered than just watching a tutorial on some topic and not getting custom problems on that topic.
 » 21 month(s) ago, # |   +4 Thanks, that’s exactly what I need.
 » 21 month(s) ago, # |   +1 The gym problems are very nice for reaffirming one's understanding of tree basics!For problem D, what was the offline solution you had in mind? The text at the top implies that there exists an offline solution that's simpler than the online solution, but the only thing I could think of is some wack dfs + segtree solution where you update the answer for a query whenever you reach one of its endpoints. That seems way too complicated to warrant explicitly disallowing offline solutions lol.
•  » » 21 month(s) ago, # ^ |   +18 Yeah it's definitely harder to do offline than online. I was also considering at a small-to-big + dfs with a treeset/segtree which I'm pretty sure is possible and can be done in n*log^2(n) without too much difficulty. The main thing is that this might show up as a sub-problem that you have to answer online, so it's good to be able to do that, rather than finding some complex way that ACs but doesn't actually use the new topics at all.
 » 21 month(s) ago, # |   +11 I really love your content
 » 21 month(s) ago, # |   0 Your screencast(s) are really helpful.
 » 21 month(s) ago, # | ← Rev. 2 →   0 Hello SecondThread . Thanks for your videos and problems I have a question I submitted this code and get AC. I am in wonder why its true Is it true ? If yes Why ? again thanks. my code
 » 21 month(s) ago, # |   0 Please give any hints for second problem.
•  » » 21 month(s) ago, # ^ |   0 https://www.geeksforgeeks.org/find-farthest-node-from-each-node-in-tree/By the way, can you help me out with my implementation? It's giving WA on test 4..
•  » » » 21 month(s) ago, # ^ |   0
•  » » » » 21 month(s) ago, # ^ |   0 ty, forgot to update max with the old diameter..
•  » » » » » 21 month(s) ago, # ^ |   0 what could be the possible 4th test case getting WA here...
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Just find the start and end vertex of the path having a maximum diameter. Because if you add (n+1)th vertex the diameter will only increase if it was added to start or at the end of the path. Also, there could be many possible paths with the maximum diameter so consider all of them.
 » 21 month(s) ago, # |   0 Hi, I am getting "You should be registered for the contest to be able to submit" while trying to submit the problem. Where should that be done?
•  » » 21 month(s) ago, # ^ |   0 Go to the gym and register from there.
 » 21 month(s) ago, # |   0 thanks for providing us this opportunity to learn
 » 21 month(s) ago, # |   +21 Dear SecondThread,Thank you for all the hard work you put in daily! Know that it is recognized and greatly appreciated, It’s an honor for our codeforces community to have someone like you.May you reach every height of success!
 » 21 month(s) ago, # |   +1 Hey nice video,In the tree shown at 36:11, how can I find the sum over the path starting at the node with input time 3 and the node with input time 13? I can think of a way to do it but it requires calculating LCA of the endpoints, is there a way to do it without LCA?
•  » » 21 month(s) ago, # ^ |   +15 Thanks! Correct, if you need to find some path aggregate in which one node isn’t an ancestor of another, you need to split it into two paths using LCA. (Unless there is some other more clever way that I’m not aware of)
•  » » » 21 month(s) ago, # ^ |   0 In problem C i think in the constraints section u,v is not necessary. Great work btw enjoying your content a lot :)
 » 21 month(s) ago, # |   +3 Can Someone Explain the Samples of Problem F Please
•  » » 21 month(s) ago, # ^ |   +1 Yeah, maybe part of it isn't super clear: for each query where x = 0, you can consider pairing things however you want just before for that query. These pairings aren't permanent, they are just considerations for that query. The way of making the pairings is to do minimize the sum of distances between every pair of paired seeds/pots.
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Thank you !! , Great ProblemSet btw !!
 » 21 month(s) ago, # |   0 expecting more and more from all of you thanks SecondThread
 » 21 month(s) ago, # |   +8 The gym-set along with the usual videos format is indeed really nice. Thank you for your hard work.
 » 21 month(s) ago, # |   -17 I've just failed my math exam because of secondthread, he says that pi = 3 in 102694A - Circumference of a Tree, so I used pi = 3 to calculate the volume of a sphere and I got 0 marks on that problem. Guys, don't trust secondthread.
•  » » 21 month(s) ago, # ^ |   0 this is not twitter, musk !
•  » » 21 month(s) ago, # ^ |   +28 Clearly the teacher's solution is wrong then. I have an elegant proof that pi is equal to 3, but it's too long to fit in the margin of this comment thread.
•  » » » 21 month(s) ago, # ^ |   0 For people not getting this,its a reference to Fermats theorem
•  » » » 21 month(s) ago, # ^ |   0 I guess you also have the proof of pi = e = 3 ?
•  » » 21 month(s) ago, # ^ |   0 PI=3 is dream come true for every programmer who often works on geometry, so much of frustration on floating point errors would be spared.
 » 21 month(s) ago, # |   0 A bit off topic, but can we expect a video on round 1 problems of hackercup, SecondThread ?
•  » » 21 month(s) ago, # ^ |   +10 He said he won't be taking part in hacker cup in one of his streams.
•  » » » 21 month(s) ago, # ^ |   0 I think...he said something along the lines that he wasn't sure if would be allowed to....but I might be wrong...Also, I found a comment on youtube...where he answered it so I guess that's it for this thread! (which is a cool line that I am hoping will catch on...lol)
•  » » 21 month(s) ago, # ^ |   +11 I’m not allowed to compete in hackercup, so probably not from me. I know Errichto has videos of him solving them, and there are some nice solutions on the Hacker cup website, too.
•  » » » 21 month(s) ago, # ^ |   +13 Why aren't you allowed to compete in hackercup?
•  » » » » 21 month(s) ago, # ^ |   +6 He works at Facebook. Employees are not able to compete, similar to the policy for GCJ
 » 21 month(s) ago, # | ← Rev. 7 →   0 Hey guys, I am bit stuck on prblem B, my approach was: start from arbitary node and find the farthest node, call it 'root' from 'root' , do a bfs and find the distance of all other nodes The maximum distance now will be the diameter,now, If distance of some node from 'root' is same as diameter or zero, the answer for this will be diameter+1 , else the answer for this node will be same as diameter I am getting a wrong answer on test 6. Can someone plz help?Any general tips to debug will also be appreciated.
•  » » 21 month(s) ago, # ^ |   +1 There can be multiple "root". Take care of that also
•  » » » 21 month(s) ago, # ^ |   0 I took care for that. I tried DFS from any general node..got all the max distant nodes.. Then ran a dfs from all of them to get their end points...of maxDiam..Then simply checked if for i is it in the stored points..I added diam+1 as asnwer..else diam is answer. Getting TLE for TC4 https://codeforces.com/gym/102694/submission/90401537
•  » » » » 21 month(s) ago, # ^ |   0 Make sure you dont linearly check, probably some faster way Spoilerbinary search
•  » » » » » 21 month(s) ago, # ^ |   0 I didn't get the spoiler hint..It would be great if you could eleborate with some another example which could relate things up.As I got that searching linearningly for N nodes would difinately be TLE...
•  » » » » » » 21 month(s) ago, # ^ |   0 Find the boundary points. Think of a better way than a linear search. SpoilerSort the boundary points and binary search
•  » » » » » » » 21 month(s) ago, # ^ |   0 There is little confusion. I am using Set for finding the elements if the element is end point of diameter. The only linear part I am doing is with find function which calculates the dep and diam initially.
•  » » » » » » » » 21 month(s) ago, # ^ |   +3 Yeah, that's not the intended solution at all. There shouldn't be any need for a log factor here. SpoilerYou know that the farthest node from any node on a tree is an endpoint of a diameter (as described in the video), right? It's also true that for any diameter and any node x, one of the endpoints of that diameter is the farthest node [technically at least ties to be farthest] in the tree from x.So you should only need to check the distance between the node you added and two other nodes in the tree. After some linear precomp, you should be able to answer this in O(1).
•  » » 21 month(s) ago, # ^ | ← Rev. 5 →   +3 What if the tree is like this? Tree8 1 2 2 3 3 4 4 5 5 6 6 7 6 8 From node 1 you will find 7 (or 8) as the farthest node. And then from 7 (or 8) you will find 1 as the only farthest node. The problem is that your algorithm will consider only 1 and 7 (or 1 and 8) as all the possible nodes which should increase the diameter by 1, but actually all of them will increase it (1, 7, 8). You can try this example yourself for more details.
•  » » » 21 month(s) ago, # ^ |   0 Thanks a lot guys, i got the mistake.
•  » » » 21 month(s) ago, # ^ |   0 Thanks for the testcase :)
•  » » » 21 month(s) ago, # ^ |   0 Hey Brodicico! Could you(or anyone) please tell me what mistake I am making. (I am continuously getting WA on test 5 and I am unable to figure out what mistake I am making — whether it is the implementation or the logic) LOGIC :Find the diameter of the tree. For all nodes if its degree is one(or zero) then output (diameter + 1) else output (diameter) CODE :#include using namespace std; #define FileIO freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); ios_base::sync_with_stdio(0); #define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define endl "\n" #define mod 1000000007 #define maxN 300003 vector adj[maxN]; int dis[maxN]; void dfs(int s, int par, int l) { dis[s] = l; for(int i : adj[s]) { if(i == par) continue; dfs(i, s, l+1); } } int main() { int n; cin>>n; int degree[n+1] = {}; for(int i = 1; i < n; i++) { int u, v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); degree[u]++; degree[v]++; } dfs(1,0,0); int maxDis = INT_MIN, node = INT_MIN; for(int i = 1; i <= n; i++) { if(maxDis < dis[i]) { maxDis = dis[i]; node = i; } } dfs(node,0,0); int diameter = INT_MIN; for(int i = 1; i <= n; i++) { diameter = max(diameter, dis[i]); } for(int i = 1; i <= n; i++) { if(degree[i]==1 || degree[i]==0) cout<<(diameter+1)<
•  » » » » 21 month(s) ago, # ^ |   0 Try a case where you have a tree in a chain form like 1-2-3-4-5-6-7-8-9. Then connect node 10 with vertex 5.The tree will be : 1-2-3-4-5-6-7-8-9 | 10 For node 10 it isn't correct to output diam+1.
•  » » » 21 month(s) ago, # ^ |   0 bro i am getting correct answer for this one but still my code fails no 4th test case
•  » » » » 21 month(s) ago, # ^ |   0 Send me your code in private.
•  » » » » » 21 month(s) ago, # ^ |   0 done.
•  » » 21 month(s) ago, # ^ |   0 There's a hint in the video..watch it again....
 » 21 month(s) ago, # |   +10 This was a wonderful effort . can anyone give me the link for other episodes.
•  » » 21 month(s) ago, # ^ |   +4
 » 21 month(s) ago, # |   +3 Your screencast are really helpful. Thank You!
 » 21 month(s) ago, # | ← Rev. 2 →   0 1006E - Military Problem Great problem on one of the concepts explained in the video. Highly recommend it! My solution for reference: 90223865
 » 21 month(s) ago, # |   0 Someone give me a hint on E, please
•  » » 21 month(s) ago, # ^ |   +11 I tried to find the topological order and size of each subtree. Then did used segment tree for updating and range queries. But it fails in test 4. Any idea guys?
•  » » » 21 month(s) ago, # ^ |   0 Overflow issues .. Even i am not getting how to do that .
•  » » » » 21 month(s) ago, # ^ |   +3 Maybe we should divide all node values by 10^6 and then build ST on doubles? If product on subttee is bigger then 1000, print 100000000, else print result
•  » » » » 21 month(s) ago, # ^ |   +17 SpoilerLogarithms
•  » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 thank you so much!!! it worked!!! you are amazing
•  » » » » » » 21 month(s) ago, # ^ |   0 How did you deal with log and pow function precision issues??
•  » » » » » » » 21 month(s) ago, # ^ |   +6 There were no issues for me with pow and log2. Code
 » 21 month(s) ago, # |   +10 As a beginner, your episode has really taught me a lot about the many application of trees. Thanks a ton for this!
 » 21 month(s) ago, # |   0 Hey can someone recommend a good list of problems which contains different( hopefully all theory) types of problems on graphs and/or trees....It would be much appreciated....
 » 21 month(s) ago, # |   0 can someone help me , I am getting memory limit exceeded in B. https://paste.ubuntu.com/p/6B8kdrvkyh/
•  » » 21 month(s) ago, # ^ |   0 Hey buddy, I saw your code, actually I think you can simplify the structure itself. Also the variable parent can be avoided, vis can be made boolean. Have you checked if the bfs doesn't explodes the queue?
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 I made vis boolean , now i getting tle. thanks man ,Changing the structure now. changed endl to "\n" got accepted.
•  » » » » 21 month(s) ago, # ^ |   0 Great!
•  » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Didn't know "\n" could change a whole lot of things. Followed some blogs on CF on this. Finally got AC after all the TLEs.
•  » » » » » 21 month(s) ago, # ^ |   0 The thing is that endl flush the output and that is slow...
 » 21 month(s) ago, # | ← Rev. 7 →   0 Hello, very nice problemset ! :)Also, i am having trouble understanding why This RTE on test 4 of the problem C. Anyone could please help me ?UPD : I think thats cause im only going up when traversing the tree, however the node that we need to reach might not be in this way and it might get OOB. But still, idk how to do this fast enough :(New UPD: Fixed !
 » 21 month(s) ago, # | ← Rev. 4 →   0 SecondThreadAny idea for D. Till now , this is how I am going: ( I guess m is always n-1). we need to find the minimum valued edge between sources and destination of the flow network, (as its a tree and only one path is present between any two nodes). we can do this by storing values of minimum for 1,2,4,8,16.. jumps above for each node, and find them just like we build the jump array in binary lifting. Now we can move to the lca and keep calculating the minimum along both souces to lca and destination to lca, again using the binary lift technique. Am I going the right way ? ( Wrong answer on 6)
•  » » 21 month(s) ago, # ^ |   +13 I do actually have an idea of how to solve D, yeah. Your general approach seems right, but I’m not going to discuss solution details too in depth for a week or so.
•  » » » 21 month(s) ago, # ^ |   0 Ya, there was some implementation flaw. Thanks a lot.
 » 21 month(s) ago, # |   +9 Someone give me a hint on F, please
 » 21 month(s) ago, # | ← Rev. 2 →   0 My 2-dfs calls in B is receiving TLE, is it expected ?
•  » » 21 month(s) ago, # ^ |   0 Nope! Use "\n" instead of endl, if you're using endl.
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 I am not using "\n"
•  » » » » 21 month(s) ago, # ^ |   0 https://codeforces.com/blog/entry/43780I faced many TLEs yesterday due to endl. Followed these blogs mentioned above then got the ans.
•  » » » » » 21 month(s) ago, # ^ |   0 This is not the reason for my TLE verdict
•  » » 21 month(s) ago, # ^ |   +3 I did 2 BFS calls too and it's getting TLE for test case 16. Can't seem to figure out why its TLE tho when at max the complexity would be O(2*(6*10^5)) which is around 10^6. Can anyone help?
•  » » » 21 month(s) ago, # ^ |   +3 figured it out now, indeed changing endl to "\n" helped. Thanks!
•  » » 21 month(s) ago, # ^ |   -8 It might be because your dfs function is not optimal, you might have forgot void dfs(int node, int p) { for(int i:tree[node]) { if(i == p) continue; // this line dfs(i, node); } } 
 » 21 month(s) ago, # |   +6 My code for problem B https://ideone.com/dd5gOx with poor English commentary :)
 » 21 month(s) ago, # | ← Rev. 2 →   +4 Math burned me, yet again!!SecondThreadFor E the products can be as large as 10^500000 ( that is ((10^5)^(10^5)) ) and we have to store approx 10^6 of those.....how can it be done....can I get a hint?
•  » » 21 month(s) ago, # ^ |   0
•  » » 21 month(s) ago, # ^ |   0 you can use logarithm to store the values, and then restore the value with a power of 2
•  » » » 21 month(s) ago, # ^ |   0 Wouldn't we loose precision? Can you plz elaborate...?
 » 21 month(s) ago, # |   +8 The problems are really, really good. Even if they use basic concepts they were not actually so easy (at least for me). I found the fifth problem very cool and challenging if you don't have experience using mathematical functions (I didn't until this problem :D). I give all my respects to the creator of this problemset. Thanks for investing your time in helping others.
•  » » 21 month(s) ago, # ^ |   +12 Thanks, I’m glad you enjoyed them :)
 » 21 month(s) ago, # |   0 For question C the code is running on my computer btt it shows runtime error for test case 390309168
•  » » 21 month(s) ago, # ^ |   0 since contest is running, nobody can open the link you posted. Also since test case 3 is visible you can directly debug in local environment to find reason for RE.just use gdb/lldb to step through code.
•  » » » 21 month(s) ago, # ^ |   0 test case 3 is running in my local env just fine. btt it shows runtime error whwn i submit.
•  » » » » 21 month(s) ago, # ^ |   0 That can happen because of multiple reasons. One of the reason can be accessing out of bound elements in array which sometimes leads to Seg fault and sometimes doesn't. maybe check that
 » 21 month(s) ago, # |   0 I haven't registered yet does that mean i'll have to wait for next 12 days?
•  » » 21 month(s) ago, # ^ |   0 You can register by going to the gym tab.
•  » » » 21 month(s) ago, # ^ |   0 Thanks got it!
 » 21 month(s) ago, # |   0 Image:Hello, i am currently at problem E and i dont understand how does it is not 1.5 in the second example, at the second line.Since it is 1-rooted, 1 has value 3, 2 has value 2 and 3 has value 1 , no ??? what did i missed here ??
•  » » 21 month(s) ago, # ^ |   +1 In the second sample, none of the nodes are ever updated, so all nodes have a value of 1. (Since the product of 1*1*1... is 1)
•  » » » 21 month(s) ago, # ^ |   0 woops, my terrible english made me thought it was the sum and not the product even tho i've re-red the problem multiple times... :') Thanks
 » 21 month(s) ago, # |   0 Could anyone please help me with problem E?How to handle such big numbers?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   -10 Spoileruse logarithms
•  » » 21 month(s) ago, # ^ |   +10 this is answered above : SpoilerLogarithms
•  » » » 21 month(s) ago, # ^ |   0 Oh! thank you.
 » 21 month(s) ago, # |   +13 I realy enjoy E, although I've made 17 WA.
 » 21 month(s) ago, # | ← Rev. 2 →   0 Can someone tell me why bfs doesn't work in promlem A to calculate the diameter. It is giving me tle.
•  » » 21 month(s) ago, # ^ |   0 It worked for me, maybe because you're using python and the time is a little tight, try reading this blog to speed up the input and the output. If it doesnt work to you, maybe trying with c++ will be a better way, because I see that the few persons that got AC, their execution time is around to 900ms
•  » » » 21 month(s) ago, # ^ |   0 Thank you.
 » 21 month(s) ago, # | ← Rev. 2 →   0 Hi, this is my first time solving Tree based problems on CF. I am having trouble understanding how to give the edges so that I can construct a tree. For example in the first question, the test case is33 22 1How will we construct a tree with 3,2 as edges and which node will they belong to? How will we construct a tree with this? I have seen some other solutions using arrays but i can't understand them.Leetcode does it like this- struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; I have previously solved on LeetCode where we had to just write the function so I am very new to this.
•  » » 21 month(s) ago, # ^ |   +4 The one you are constructing in LeetCode is Binary Tree having almost 2 children.Here you need to use Adjacency list, which can be implemented via vectors in C++. You should read about it.
•  » » 21 month(s) ago, # ^ |   0 Just use an adjacency list. Remember that tree is just a special graph, so you really don't have to anything else, just use bfs, dfs just like you would do in a graph.
•  » » » 21 month(s) ago, # ^ |   0 will this be a unidirected or a directed graph? they have specified this is a tree so it should be a directed graph right?sorry i am very new to this.
•  » » » » 21 month(s) ago, # ^ |   0 I recommend glancing over this : DFS n-ary treeNotice how for every connection, the changes are being made. It would be undirected graph.
 » 21 month(s) ago, # |   0 https://www.hackerrank.com/coding-practice-1597842464Contest starting at 7. Join fast!
 » 21 month(s) ago, # |   +3 Any hint for problem F? (getting wrong answer)
•  » » 21 month(s) ago, # ^ |   +3 SpoilerFix some root. Assign +x to seed and -x to pot. The edge a — b will only be used if there is net positive/negative sum in the subtree of a or b (whichever on more depth).
•  » » » 21 month(s) ago, # ^ |   0 My approach was similar, probably need to debug it more
 » 21 month(s) ago, # | ← Rev. 4 →   0 Thank you very much for this effort. I really liked the problems.
 » 21 month(s) ago, # |   0 I solved F by observing some examples, can somebody give proof for F, why this works?
•  » » 21 month(s) ago, # ^ |   0 if you supposed a minimal matching where there are only two nodes on each side , and you paired each node with the one in opposite side you'll find that you can minimize more the distances by pairing each node with the one on it's side.
•  » » » 21 month(s) ago, # ^ |   0 "you can minimize more the distances by pairing each node with the one on its side." I am looking for why this is always true. Maybe here it is easy to observe.
•  » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   +3 Consider the graph: 1-2, 2-3, 2-4Node 1 and node 3 have one seed each. Let us consider that there is a pot in the subtree of node 4 (let's call this node A) and a pot in the rest part of the tree above of the node 1 (let's call this node B).Optimal solution is to match seed-3 with pot-A and seed-1 with pot-B, because the sum of distances is equal to dist(3, 2) + dist(2, A) + dist(1, B). If you try to "cross" the edge (1-2) and match the seeds in a different way, then the sum would be equal to dist(3, 2) + dist(2, 1) + dist(1, B) + dist(1, 2) + dist(2, A) which is larger than before by 2 * dist(1, 2).As you can see, you can never avoid some distances, so there is no reason to try to match a seed with an other pot when there is already one available in its subtree.
•  » » » » » 21 month(s) ago, # ^ |   +3 Thanks, That makes sense.
•  » » » » » » 21 month(s) ago, # ^ |   0 You are welcome !
•  » » 21 month(s) ago, # ^ |   0 I'm failing to understand the input test cases in problem F, where queries are : 1 6 2 2 5 3 4 3 0 Above, 2 seeds at node 1 and 2 pots at node 6 make 2 valid pairs(path 2->6 goes through edge 3-4). Similarly, 3 seeds at node 2 and 3 pots at 5 make 3 valid pairs. This path goes through edge 3-4. This makes a total of 5 valid pairs. 6 2 2 4 3 0 Similarly, 2 seeds at node 6 and 2 pots at node 2 make 2 valid pairs and this path connecting 2 and 6 also cross the edge 4-3. So, total of 5+2=7 valid pairs. But, why is the answer for that query 3?I'm missing something here, kindly help!!Also, it's written The total sum of the distances between every pair must be minimized to keep clean the air. Does this mean something? I didn't get it.
•  » » » 21 month(s) ago, # ^ |   0 It's not required that seeds should placed in the respective same pots which were created while creating seeds in each query. In the above example for the last query we can use 2 pots at node 2 for placing seeds from node 1 or 2. The total sum of the distances between every pair must be minimized to keep clean the air This means that sum distance travelled by each seed from the source node to node which contains pot should be minimized.
 » 21 month(s) ago, # |   0 Will all the test cases be made public after the contest ends?
•  » » 21 month(s) ago, # ^ |   0 Sure, I can do that. Ping me after if I forget :)
•  » » » 21 month(s) ago, # ^ |   0 Thanks for the support!
•  » » » 21 month(s) ago, # ^ |   +5 ping
•  » » » 21 month(s) ago, # ^ |   0 Thanks for the cool problems!I couldn't figure out D. So I'm waiting to check other solutions for some insight.
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 please make the test cases public.SecondThread
•  » » » » 21 month(s) ago, # ^ |   0 How do I do that?
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 SecondThread, Can you make the test cases public now?
 » 21 month(s) ago, # | ← Rev. 2 →   0 I am getting TLE in TC 4. I stretched the tree along the diameter and after that if node is added to the end points of diameter then dynamic diameter will increase by 1 otherwise not. My solution is here. Please somebody tell me error in my approach.
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Your solution can't be opened until the contest ends. But the solution for your problem is answered above. Link to comment
 » 21 month(s) ago, # |   0 1 sec time limit is pretty rough for java?
•  » » 21 month(s) ago, # ^ |   +3 For which problem? I think all the judge solutions are in Java, but I can bump it up if it’s too tight.
•  » » » 21 month(s) ago, # ^ |   0 For B, i feel like my sol would pass with 2 sec limit, but if not that is fine, I can move on
•  » » » » 21 month(s) ago, # ^ |   +37 global_optimum you now have 3x the time limit (3s). One might say it's now a big_boy_time_limit.
 » 21 month(s) ago, # |   0 Can someone please explain me what's wrong in my logic for B ? I seem to be repeatedly failing test case #6. LogicFind the diameter of the tree and one possible endpoint of it, as mentioned in the video. Then, for each node just check if it's distance from the start node (which is the endpoint/start point of some diameter of the tree) in 2nd BFS (referencing from the tutorial video) equals the diameter; if it does the answer is diameter + 1, else it is the diameter itself.
•  » » 21 month(s) ago, # ^ |   +3 This will not give you the correct answer. SpoilerLet's say you have the following tree: 7 1 2 2 3 3 4 4 5 5 6 5 7 Your approach would not give diameter + 1 for all the relevant nodes i.e. 1, 6 and 7
•  » » » 21 month(s) ago, # ^ |   0 Thanks a lot, that helped!
 » 21 month(s) ago, # |   +1 Can anyone pls provide some test case for problem C? im getting WA on test 4
•  » » 21 month(s) ago, # ^ |   0 I am also stuck on test case 4 with problem C
•  » » » 21 month(s) ago, # ^ | ← Rev. 3 →   0 SecondThread any hints?
•  » » » » 21 month(s) ago, # ^ |   0 I'm not sure if it helps, but I recommend you take a look at the cp-algorithms.com lca tutorial if you're stuck.
•  » » » » » 21 month(s) ago, # ^ |   0 silverfish No I know about lca and other algorithm to solve it. It is just there must be a corner case that I am missing. Hence wanted some hints
•  » » » » » » 21 month(s) ago, # ^ | ← Rev. 3 →   0 Kush.code Can you link your code?Most likely your logic for calculating c'th node on the path from a to b is wrong. Key is to use LCA to determine whether c'th node is from path (A -> LCA) or (LCA -> B).
•  » » » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 sjay05 https://ideone.com/A9iHTM I tried but I could not find any issues. can u take a look
•  » » » » » » » » 21 month(s) ago, # ^ | ← Rev. 3 →   +1 I solved the problem from a bit by the same idea as you. but i was getting Wr4 because the function that lift the node up by c. so, i advise you to check it, this is my submission, i hope it helps you. - wrong submission - Ac submission
•  » » » 21 month(s) ago, # ^ |   0 Draw a tree and make all possible cases for k, that's all you need to do.
•  » » » » 21 month(s) ago, # ^ |   0 FinalBoss_ there is no k in problem c
•  » » » » » 21 month(s) ago, # ^ |   0 "C" energy value.
•  » » 14 months ago, # ^ |   0 Stuck out here too. Any tips? I am simply calculating the node we can reach from euler's tour.
•  » » » 14 months ago, # ^ |   0 I got AC by using binary lifting to calculate the parents. Before I was using the Euler tour to find the parent on which the sloth will stop. But I am not getting why it was wrong.Three cases: Spoiler if(distance[u, lca] == c) -> lca if(distance[u, lca] > c) -> euler[first[u] + c] if(distance[u, lca] < c) -> euler[first[v] - (dist[v, lca]) - (c - dist[u, lca])] Here first[u] gives the index of the first time we found u during our tour, and, euler[id] gives the node we visited during our Euler tourIf anyone could provide any test case where calculating parent from the Euler tour turns out to be incorrect, it would be great.
 » 21 month(s) ago, # | ← Rev. 3 →   0 In question no C these are the arrays in my programm my code is runnig is fine in my system btt shws runtime error when i submit can this be a memory issue?? int N, D; int depth[300010];//depth of node vector adj[300010]; int par[20][300010];//binary lifting table Inside main  memset(depth, 0, sizeof(depth)); for (int i = 0; i < 300010; i++) { adj[i].clear(); } memset(par, -1, sizeof(par)); 
 » 21 month(s) ago, # |   0 SecondThread, what's the constraint of q in D?
•  » » 21 month(s) ago, # ^ |   +1 Oh, good question. I’m pretty sure it’s 3*10^5. But like, answer each query in sublinear time please and you should be good to go.
 » 21 month(s) ago, # |   0 Thank you very much for the problemset, it's very helpful! I like how it's not just straightforward "implement LCA and be done with it", but includes some modification that forces you to understand the concept behind it.I have a question about F. It seems that the observation is SpoilerFor a subtree rooted at node $v$, if there are $x$ seeds and $y$ pots in a subtree, it's optimal to match $min(x, y)$ within the subtree, and the rest will have to go through the edge between $v$ and its direct ancestor. This reduces the problem to simple subtree sum.Which seems intuitively true, but how to prove it?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +3 SpoilerAssume it's not true (i.e. it's better to match pots/seeds from different subtrees):Now if you try to match the pots from subtree rooted at $v$ with the seeds from subtree rooted at $u$ your distance would be the distance from the pot nodes to $v$ + distance from the seed nodes to $u$ + $x$ (the number of matched pots/seeds) times the distance from $u$ to $v$;Note that you would also need to match the seeds from subtree rooted at $v$ with the pots from other subtree (let's say $u$ in this case) and by the same account it would result in the distance from the seed nodes to $v$ + distance from the pot nodes to $u$ + $x$ (the number of matched pots/seeds) times the distance from $u$ to $v$.This would give us, in total, at least $X$ (total number of matched seeds/pots) times more the distance from $u$ to $v$ by matching seeds/pots from different substrees than if we were matching in the same subtree.
•  » » » 21 month(s) ago, # ^ |   0 Can i get a hint for problem F.
•  » » » » 21 month(s) ago, # ^ |   +12 The problem is strictly linked with the idea of minimizing the sum of distances between seeds and pots, thus the first thing to think is "when is it necessary to cross edge $E$ when matching a seed with a pot?".This is not likely a hint, but let's try to see something intuitively in the following cases:  R -> root. / \ P S Here you have a pot and a seed in the leaf nodes, thus the result in any edge would be 1 since there's no other matching possible/closer/minimum. This would give us a total sum of 2.  __R__ -> root. / \ N1 N2 -> nodes. / \ / \ 2*P 1*S 1*P 2*S -> amount of seeds/pots. N3 N4 N5 N6 -> nodes. Here our options would be: Match all pots from $N3$ with all seeds in $N6$ and the seed in $N4$ with the pot in $N5$. This would give us a total distance sum of 4*2 + 4*1 = 12 and the following edge values:  __R__ -> root. 3/ \3 -> edge values. N1 N2 -> nodes. 2/ \1 1/ \2 -> edge values. N3 N4 N5 N6 -> nodes.  Another option would be to match 1 pot from $N3$ with the seed in $N4$, the remaining pot from $N3$ with a seed in $N6$, the pot from $N5$ with the remaining seed in $N6$. This would give us an smaller total distance sum of 2*1 + 4*1 + 2*1 = 8 and the following edge values:  __R__ -> root. 1/ \1 -> edge values. N1 N2 -> nodes. 2/ \1 1/ \2 -> edge values. N3 N4 N5 N6 -> nodes. Note that the second option is better because we don't need to cross the root edges multiple (extra) times. Thus, matching seeds/pots locally (closer matches) might reduce the total sum. Also, looking at the last example, try to answer the question "when is it necessary to cross edge $E$ when matching seeds and pots?" thinking locally.After solving (or if you still can't solve) the problem look at the spoilers on this thread to clear any doubt.
•  » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   +6 Thanks bro for your effort, I think i got the key now. My IdeaLet's fix the tree to be rooted at node 1, then for each query with type(1) add +X on seed node and -X for pot node. Now, we need to pass through the edge from a — b, iff the total absolute sum of seeds and pots in subtree of node with max depth between a, b is greater than zero and this will be the number of time to pass through this edge also. UPD: Solved!, Thank you bro. 
 » 21 month(s) ago, # |   0 Could anyone clarify the problem E for me? From what I understand, in the first test case the tree is just a straight path 1 — 2 — 3. So if every node has value 1 at the beginning then subtree rooted at node 1 has moola value 3, at node 2 : 2 and at node 3 : 1. so why the answer for two different subtrees is 1.000000? Shouldn't it be something different if every subtree has different moola value value?
•  » » 21 month(s) ago, # ^ |   0 Nevermind, its product not a sum. It turns out I am poor at reading.
 » 21 month(s) ago, # |   0 I am not able to solve circumference of tree problem .. also there is no editorial available .. what to do ?
•  » » 21 month(s) ago, # ^ |   +23 Watch SecondThread Trees video ?
 » 21 month(s) ago, # |   +1 It's really helpful! Thank you !
 » 21 month(s) ago, # |   0 Your effort is much appreciated. It will help us learn new algorithms used in competitive programming.
 » 21 month(s) ago, # |   0 Can some one plz provide a link to their submission for E. I have understood the approach (partially), but having problem to implement it.
•  » » 21 month(s) ago, # ^ |   +3
•  » » » 21 month(s) ago, # ^ |   0 Why are you directing me to my own comment?
•  » » » » 21 month(s) ago, # ^ |   +3 Click on the link and see the topmost comment on the screen. Its tumaryui's comment.
•  » » » » » 21 month(s) ago, # ^ |   0 oh, thanks a lot!
 » 21 month(s) ago, # | ← Rev. 2 →   0 Can anyone give me a hint on problem D? how to flatten a tree and have edge weights in it's euler tour?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0
 » 21 month(s) ago, # |   0 Can someone help, why this code fails on test case 8? Please help Code#include using namespace std; #define fastio ios_base::sync_with_stdio(0); cin.tie(0) #define LL long long #define FOR(i, j, k) for (auto i=j ; iadj[2*MAX]; vectorvis(2*MAX,0); vectord1(2*MAX,0); vectord2(2*MAX,0); vectord3(2*MAX,0); int di=0; int dfs(int u , int h){ vis[u]=1; d1[u]=h; int f=0,s=0; for(auto v :adj[u]) if(!vis[v]){ int sub = dfs(v,h+1); if(sub>f) s=f,f=sub; } d2[u]=f,d3[u]=s; di = max({di,d2[u]+d3[u]}); return max(1+d2[u],1+d3[u]); } int main(){ fastio; int t=1;// cin>>t; while(t--){ int n ; cin>>n; FOR(i,0,n-1){ int x,y; cin>>x>>y; adj[x].push_back(y);adj[y].push_back(x); } dfs(1,0); cout<<3*di; } } 
 » 21 month(s) ago, # |   0 Great video, thank you!Also, I think a thing worth mentioning is that segment trees can be directly utilized on incomplete rooted binary trees, while this tree -> Euler path -> segment tree approach helps us reduce the complexity when trees aren't necessarily binary.
 » 21 month(s) ago, # | ← Rev. 2 →   0 In problem E SecondThread, I got 4 WA's using Fenwick/BIT Tree but as soon as I changed it to Segment Tress, it got accepted.Solution using BIT/Fenwick TreeSolution using Segment TreeI am unable to understand why it is happening. If anyone has solved this question using fenwick tree, please look at the code and tell where is it going wrong or share your code.UPD: I got the error. I was constructing the fenwick tree in a wrong manner.
•  » » 21 month(s) ago, # ^ |   0 Hmm, my model solution uses a fenwick tree. That’s odd for sure...
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 If that's so, then I must be doing some silly/ gross mistake that I am unable to find. I hope you wouldn't mind to taking a peek at my code unless you're busy.Anyway, thanks for the clarification.UPD: I got the error, I was construting the Fenwick Tree in a wrong way.
 » 21 month(s) ago, # |   +9 Nice guide, really appreciated.For everyone looking for other problems to apply the tree flattening trick, here are some from CSES problem set:
 » 21 month(s) ago, # |   +1 Can someone please let me know why My code fails on test 5(Problem B)code
 » 21 month(s) ago, # | ← Rev. 3 →   0 For problem C: Assume tree like following. 7 1 2 1 3 2 6 2 7 3 4 3 5 2 7 5 1 7 5 3 Is the answer (2, 1) or (2, 3)?
•  » » 21 month(s) ago, # ^ |   +3 2, 3
•  » » » 21 month(s) ago, # ^ | ← Rev. 4 →   +4 Can you hint me, what is the wrong here (if you solved the problem). My solution UPD: SOLVED!
 » 21 month(s) ago, # | ← Rev. 4 →   0 Can anyone tell me why I am getting the wrong answer for testcase-4 in problem E, or give me any test case? SecondThreadcode
•  » » 21 month(s) ago, # ^ |   +4 It is due to overflow issue. You can see this thread for fixing it
 » 21 month(s) ago, # | ← Rev. 4 →   0 Can i get hint for problem F.
•  » » 21 month(s) ago, # ^ |   +4 Being discussed here.
 » 21 month(s) ago, # |   0 Can someone please explain me the way to approach problem F.I have been stuck at it for quite some time now !!
•  » » 21 month(s) ago, # ^ | ← Rev. 3 →   -9 .
 » 21 month(s) ago, # |   0 can anyone tell how to do c
 » 21 month(s) ago, # |   0 Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).
 » 21 month(s) ago, # |   0 Really enjoyed thanks.
 » 21 month(s) ago, # | ← Rev. 3 →   0 Enjoyed and learned alot!!
 » 21 month(s) ago, # | ← Rev. 2 →   0 SecondThreads java solutions were posted, but if you need A-E in c++: A B C D E F
•  » » 21 month(s) ago, # ^ |   0 Could u pls help me, I am in dire need https://codeforces.com/gym/102694/submission/91916488 here is my solution link
 » 21 month(s) ago, # |   0 Would u pls open the solutions for others, it would really help the beginners like me
 » 21 month(s) ago, # |   0 n=int(input()) adj=[[] for i in range(n+1)] for i in range(n-1): n1,n2=list(map(int,input().split())) adj[n1].append(n2) adj[n2].append(n1) ans=[0,1] def dfs(n1,parent,level): for i in adj[n1]: if i!=parent: dfs(i,n1,level+1) if ans[0]<=level: ans[0]=level ans[1]=n1 dfs(1,-1,0) dfs(ans[1],-1,0) print(3*ans[0]) /*My solution for the first problem*/ /* Got a runtime error in hidden testcase*/ /*Pls help*/
 » 20 months ago, # | ← Rev. 2 →   0 Can someone help me what was wrong in this ? Question C (Sloth) : 4th Test Case, failing with runtime error.https://codeforces.com/gym/102694/submission/92562480
 » 20 months ago, # | ← Rev. 2 →   0 I'm facing a weird error. The same solution is getting accepted in C++14 and getting RE in C++17 for Problem B. Accepted code#include using namespace std; typedef long long ll; typedef vector vi; typedef pair ii; typedef vector vii; const int mod = 1e9+7; const int N = 3e5+1; vi edges[N+1]; int dist[N+1],distfromanother[N+1]; void dfs(int s,int p){ for(auto x : edges[s]){ if(x==p) continue; dist[x] = dist[s]+1; dfs(x,s); } } void dfs2(int s,int p){ for(auto x : edges[s]){ if(x==p) continue; distfromanother[x] = distfromanother[s]+1; dfs2(x,s); } } main(){ int n;cin>>n; int edge = n-1; while(edge--){ int u,v;cin>>u>>v; edges[u].push_back(v); edges[v].push_back(u); } dfs(1,0); int farthestnodefrom1,distance=0; for(int i=1;i<=n;i++){ if(distance
•  » » 20 months ago, # ^ |   0 That sounds more like a C++ issue to me than anything else. If I had to guess, I would say it's likely a stack-space configuration issue. I think the RTE is probably that your recursion goes too deep on the rope case for instance, which causes you to run out of stack space.I don't know what differences there would be otherwise, although I was under the impression that your main was always suppose to return 0...
•  » » » 20 months ago, # ^ |   0 SecondThread It throws RTE even for n=1, So I don't think it's a stack space issue. Ya main always return 0.Maybe any C++ experts could help us Errichto
•  » » » » 20 months ago, # ^ |   0 Guess who was right: https://codeforces.com/blog/entry/81527?#comment-682038
•  » » » » 20 months ago, # ^ |   +10 For n=1 farthestnodefrom1 will not be initialized before the second dfs, which is the cause of RE I think (undefined behavior)
 » 20 months ago, # |   0 SecondThread the problems aren't available in the gym contest
•  » » 20 months ago, # ^ |   0 What do you mean? The problems look available to me...
 » 20 months ago, # |   0 SecondThread if possible, maybe u can link the video editorial as editorial in the problemset. That may help a little bit
 » 19 months ago, # | ← Rev. 3 →   0 Memory limit exceeded for problem D. Can anyone provide a way to access particular element (i.e. weight) from a pair of a 2D vector?My submission: https://codeforces.com/gym/102694/submission/95058645UPD: Solved it.
 » 19 months ago, # |   0 SecondThread Can we not see the input for the test case the code is failing? https://codeforces.com/gym/102694/submission/95846667 --> "Runtime error on test 4" but how do I debug? Input is not shown.
 » 19 months ago, # |   0 do i need tree and graph to be green?
 » 16 months ago, # |   0 I think 1 second it's too short for python. I'm getting TLE for TC4 on A and it's puzzling because it's definitely the right approach. Can anyone help? 105103742
 » 16 months ago, # | ← Rev. 6 →   0 hey, can any body say the reason for TLE in problem 4... https://codeforces.com/gym/102694/submission/105264454 i think mine is nlogn but getting TLE.
 » 11 months ago, # |   0 I am getting wrong answer in test case-6 in the second problem from your gym problem set. Someone please tell me whats wrong in the code. Here's the submission Link