You are not logged in. Please login at www.codechef.com to post your questions!

×

Abacus'17-OLPC Geek Tree Solution

Hello, the contest Abacus'17 has just finished. Can somebody tell how to solve the problem, Geek Tree.

link - https://www.codechef.com/ABCS2017/problems/ABCS01

asked 18 Mar '17, 00:01

mathecodician's gravatar image

6★mathecodician
2.6k11034
accept rate: 7%


link

answered 18 Mar '17, 01:59

aminuteman's gravatar image

1★aminuteman
1745
accept rate: 13%

This u can do easily bu using a dfs and BIT or segment tree.Basically as u go into a branch during dfs u update the node value in BIT.Then u do a search for all values in the range [s-k,s+k] in the ancestors where "s" is the current node value because all those values will be counted as pairs with s. Here is when u will use BIT to find this value:

ans+=query(s+k)-query(s-k-1);

U find this in O(log n).Then update this current node's value in BIT before going to its children. By doing this u can find the answer for all vertices and hence for the whole subtree.

See my code for reference : https://www.codechef.com/viewsolution/13109792

Happy coding ;)

link

answered 18 Mar '17, 00:50

aloochaat1998's gravatar image

5★aloochaat1998
995
accept rate: 16%

Thanks although I don't know BIT or segment trees yet. So, I'll probably try this problem later.

(18 Mar '17, 01:06) mathecodician6★

Can you please elaborate your answer? What will you get in ans after performing this query? And why there is a need of update in this offline query?

(18 Mar '17, 01:38) bansal12325★

Can someone tell the solution for this problem too : https://www.codechef.com/ABCS2017/problems/ABCS05

link

answered 18 Mar '17, 00:11

tihorsharma123's gravatar image

2★tihorsharma123
49718
accept rate: 15%

@tihorsharma

In this problem,try drawing a matrix to come up with a solution. You will observe a pattern.

If u still can't figure it out, tell me and I'll tell u the full solution.

link

answered 18 Mar '17, 00:21

mathecodician's gravatar image

6★mathecodician
2.6k11034
accept rate: 7%

Okay I will try Thanks :)

(18 Mar '17, 00:27) tihorsharma1232★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×218

question asked: 18 Mar '17, 00:01

question was seen: 367 times

last updated: 18 Mar '17, 01:59