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.
http://www.codechef.com/NOV13/problems/GERALD2 http://www.codechef.com/MARCH14/problems/GERALD07 http://www.codechef.com/APRIL14/problems/FBCHEF
Do you know where I can find more of such problems? Thanks and have a great day!
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.
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).
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.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.
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
Thanks! :D
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
i think, this problem is a simpler version of FBCHEF, it's a nice problem anyway.
Problems involving trees are so exciting, it's good to know that someone shares the same feeling!