Zzyzx's blog

Tree problems
By Zzyzx, 11 years ago, In English

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!

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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).

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think, this problem is a simpler version of FBCHEF, it's a nice problem anyway.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems involving trees are so exciting, it's good to know that someone shares the same feeling!

→ Reply