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

×

CHEFC - Editorial

Problem link:

contest
practice

Difficulty :

Hard

Pre-requisites :

Balanced Binary Search Trees such as Treaps.

Problem:

You are given an array of size N. You need to answer M queries. Each query has one of the two types:

  • 1 l r - Calculate some interesting function F for subarray indexed from l to r inclusive.
  • 2 l r - Modify the given array by removing all elements having indices in range from l to r and then putting these numbers at the beginning of array. Order of all other elements remains same. Definition of F can be found in the problem.

Explanation

We will use treap to solve this beautifull problem. First Let us see the values stored at a node.

  • Val : To keep the value of the node.
  • Cnt : To count the number of nodes in the tree.
  • Prior : To keep the priority of node [ which is a part of treap data structure ]
  • Lval : To keep the value of the leftmost node of the tree.
  • Rval : To keep the value of the rightmost node of the tree.
  • Ans : To Calculate the answer for the tree.
  • Ltree : Keeps a pointer to the left subtree.
  • Rtree : Keeps a pointer to the right subtree.

Let us call pointer to this structure as Tree structure.

The only challenge left in this problem is how to update the data in split and merge operations.

Let us first assume that we are able to do so and procede to give our algorithm keeping this as blackbox. We will make a visit again to it :).

Report Operation:

Split the root in to 3 trees t1,t2 and t3 such that t1 contains node from 1 to l-1 , t2 contains node from l to r, and t3 contains node from r+1 to N. Finally after you answer the query from the tree t2, we return our answer and merge the trees back.

//Aim is to return the value of the function from l to r. Tree t1, t2, t3; //declare 3 trees split(root, t1, t3, r); //Split the trees in to t1 and t3 , t1 has size r and t3 has size N-r. split(t1, t1, t2, l - 1); //Split the trees so that [l,r] is in t2. int ret = t2->ans; //merge the trees back. merge(t1, t1, t2); merge(root, t1, t3); return ret;

Another method for Reporting : Find the prefix sum for the treap upto r and prefix sum upto l and the difference is the answer. You can calculate prefix sum in the following manner :

int TreeNode::QuerySum(int rank) if (this == null) return 0; if (rank <= Ltree->size) return Ltree->QuerySum(rank); return Ltree->ans + diff + Rtree->QuerySum(rank - lch->size - 1);

Update Operation:

We will split the tree into 3 parts t1,t2 and t3 such that t1 contains node from 1 to l-1 , t2 contains node from l to r, and t3 contains node from r+1 to N. When we merge the trees , we will merge t2 and t1 and then this will be merged with t3. [ Swapping the trees t1 and t2 which was needed ]

Tree t1, t2, t3; split(root, t1, t3, r); split(t1, t1, t2, l - 1); merge(t1, t2, t1); merge(root, t1, t3);

Now it's high time to introduce the split and the merge functions.

Split Tree Operation:

Find the number of nodes in the left subtree[let us call it cur_add]. If cur_add is greater than or equal to Key then we split the left subtree otherwise we split the right subtree.

void split(Tree t, Tree &l, Tree &r, int key, int add = 0) if (!t) l = r = NULL; return; int cur_add = add + get_cnt(t->l); if (cur_add >= key) split(t->Ltree, l, t->Ltree, key, add), r = t; else split(t->Rtree, t->Rtree, r, key, add + get_cnt(t->Ltree) + 1), l = t; //To Update the structure upd_cnt(l); upd_cnt(r);

Merge Tree Operation:

If the priority of the left subtree is more than the priority of the right subtree then the root of the tree will be choosen from the left subtree.

void merge(Tree &t, Tree l, Tree r) //Update the structure upd_cnt(l); upd_cnt(r); if (!l || !r) t = l ? l : r; return; if (l->prior > r->prior) merge(l->Rtree, l->Rtree, r), t = l; else merge(r->LTree, l, r->Ltree), t = r; upd_cnt(t);

Updating the Count and the Answer

void upd_cnt(pTree v) if (!v) return; v->cnt = 1 + get_cnt(v->Ltree) + get_cnt(v->Rtree); if (v->Ltree) v->lval = v->Ltree->lval; else v->lval = v->val; if (v->Rtree) v->rval = v->Rtree->rval; else v->rval = v->val; v->ans = 1 + get_ans(v->Ltree) + get_ans(v->Rtree); if (v->Ltree && v->Ltree->rval == v->val) v->ans -= 1; if (v->Rtree && v->Rtree->lval == v->val) v->ans -= 1;

Another Approach

You can use O(N * sqrt(N) ) decomposition to solve this problem. Make sqrt(N) chuncks of size sqrt(N) each and keep the Function value for each sqrt(N) chunck.

For Update operation, you will break atmost 2 sqrt chuncks, so you will create atmost 2 new chunks , so after sqrt(N) queries , rebuild the data structure.

When we update we also update the function value of the four chunks which are splitted in O(sqrt(N)) time.

Moving blocks can be done using brute forces in O(sqrt(N)) time.

For a Query, Iterate over all sqrt(N) blocks and add the answer for each block except the corner ones [ you need to take care for last and the first elements of the blocks ]. For first and last block , you can brute to find the answer in O(sqrt(N)) time.

Overall time complexity : sqrt(N) times rebuilding + sqrt(N) per query + O(N) initialization. Thus a total of O(N * sqrt(N)) time complexity.

Some Interesting Readings

Treap Implementation

Setter and Tester Solutions:

setter
tester

This question is marked "community wiki".

asked 28 Sep '14, 14:01

devuy11's gravatar image

4★devuy11 ♦♦
56273842
accept rate: 0%

edited 28 Sep '14, 14:01


Awesome problem. Congratulations! Too bad you let O(N*sqrtN) pass. It just spoils the fun. My treap implementation ( http://www.codechef.com/viewsolution/4916687 ) since both solutions are unavaible.

link

answered 28 Sep '14, 14:09

alexvaleanu's gravatar image

4★alexvaleanu
5591312
accept rate: 7%

edited 28 Sep '14, 14:19

1

N sqrt(N) solution is not entirely worthless :P

(28 Sep '14, 14:23) dpraveen ♦♦4★

Not at all. Different solutions make problem interesting. Also sqrt decomposition is way more original solution than treap solution.

PS:i've writen treap during contest too.

(28 Sep '14, 14:24) contesant5★

N sqrt(N) is even harder to implement and requires much more clever thinking :P

(04 Oct '14, 14:31) gdisastery14★

Hi,

Can anybody explain to me why have we used Treaps here? I looked at the solution from setter, and I couldnt see the need for priority here. It is set using random number and that is what is confusing.

Thanks

link

answered 02 Oct '14, 19:23

anantkaushik89's gravatar image

4★anantkaushik89
1116
accept rate: 0%

1

I request the admin to please answer some basic queries. It is not really very clear how treaps were used, and how using random priority helped solving the question. If people are to gain from the editorial, then it would be good to have more thorough explanations on things, else the gain is limited to very few people who already are very clear of the concepts.

(04 Oct '14, 13:42) anantkaushik894★

Hello,

This is a very interesting explanation. Thank you for this.

Could you please explain the time complexity in the treap case?

link

answered 03 Oct '14, 06:47

epsilon_0's gravatar image

4★epsilon_0
4527
accept rate: 0%

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:

×15,852
×1,359
×42
×38
×13

question asked: 28 Sep '14, 14:01

question was seen: 4,264 times

last updated: 04 Oct '14, 14:31