### Zzyzx's blog

By Zzyzx, 6 years ago, ,

Hello World!

Recently, I've found a deep interest in problems involving queries on Trees (Have you tried the ones on the monthly Codechef Long Contests? They are too good!) I want to practice more of them. Since this doesn't fall into a proper category per say, I wanted to ask if anybody can give me good links to similar problems for practice and resources if possible.

Here are a few examples of problems in recent contests that I found to be very interesting.

Do you know where I can find more of such problems? Thanks and have a great day!

• +15

 » 6 years ago, # |   0 Also http://www.codechef.com/APRIL14/problems/GERALD08, which looks like a game theory problem but there's a neat tree algorithm that solves it.
•  » » 6 years ago, # ^ |   0 I tried to solve it using Red-Blue hackenbush tree algorithm. If I use double in C++, then it becomes a precision problem. If I use BigInteger in Java, it weirdly gives NZEC runtime error. (I don't know the reason for this).
•  » » » 6 years ago, # ^ |   +3 If you use a trick that's similar to HLD (add the numbers from smaller sons into the number for the larger son and remember just an array index of the result) and represent the binary numbers as bits in a map<> + exponent, it gets AC in 2 seconds total.
•  » » » 6 years ago, # ^ |   +3 You must be using a recursive algorithm, and then running out of stack space, hence the NZEC. JAVA and Python have lesser default stack size than C++. You can confirm this by surrounding the recursive code call with a try block and catching StackOverflow error. You'll start getting WA/TLE instead of NZEC. To use more stack space in JAVA, you need to create a new thread with the desired stack size and then call the recursive code from that thread.
•  » » » » 6 years ago, # ^ |   0 Woah, I never imagined I'd have to do all that to get it working. Thanks for sharing. Congrats on your performance, you've done insanely well :D
•  » » » » » 6 years ago, # ^ |   0 Thanks! :D
 » 6 years ago, # |   0 try this problem (also from a Codechef long). P.S. i'm not really sure if u meant trees or segment trees, but this problem involves both. :D
•  » » 6 years ago, # ^ |   0 i think, this problem is a simpler version of FBCHEF, it's a nice problem anyway.
 » 6 years ago, # |   0 Problems involving trees are so exciting, it's good to know that someone shares the same feeling!