CHEFDTRE - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Roman Furko
Testers: Pushkar Mishra and Sergey Kulik
Editorialist: Pawel Kacprzak
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

DIFFICULTY:

Medium

PREREQUISITES:

balanced binary serach data structures with fast union (treap, AVL-tree, splay tree), order statistics

PROBLEM:

You are given N sets of integers. Initially each set consists of exactly one element. All elements are unique. Your task is to be able to perform two operations on these sets:

  1. Merge two sets into a new one
  2. For a given set, return the k^{th}
    smallest integer in it

QUICK EXPLANATION:

Use any balanced binary search tree with the ability to perform fast unions to represent each set. Augment each tree in order to provide a method to return the k^{th} smallest element in it.

EXPLANATION:

We will show how to use a treap as the underlaying data structure.

Finding the k^{th} element in a treap

In every node of the treap, store the number of nodes in its left subtree. Notice that this value can be easily updated and maintained during any rotation used in treap implementation. Having this information, we can easily return the k^{th} smallest element in the treap. Starting our recursive procedure in with the whole treap as a current search space, let c be the number of nodes in root’s left subtree. We have 3 cases to consider:

  1. c = k - 1, then element in the
    root is the element we search for,
    because in the current search space.
  2. c >= k, then we know that the
    element we are searching for is in
    the left subtree of the root
  3. c < k - 1, then we search for the
    (k - c - 1)^{th} element in the right subtree
    of the root

This allows us to perform a single query in O(\log(M)), where M is the number of nodes in the treap.

Handling union of two treaps

Using the fact that all our input numbers are unique, we can easily use a recursive algorithm to find the union of two treaps.

These operations were described widely in the past, so I encourage all of you to read about them, for example, here.

A single union takes O(M \cdot \log(\frac{N}{M})), where M and N are the sizes of two treaps and M \leq N.

Time complexity

The exact complexity depends on the operations given in a test file, because different operations provide different treaps sizes, but notice that the time needed for union of two heaps is dominated by the size of the smaller treap. In order to produce two treaps with size \frac{N}{c}, you have to perform 2 \cdot \frac{N}{c} - 2 unions beforehand. In summary, these method will easily pass all testcases.

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester

2 Likes
2

Hello codechef community,

I tried the following solution in this problem and got TLE for the subtask2.
For each union operation i tried to merge smaller size set into bigger size set and added element to the corresponding balanced bst. so for each union operation i will be taking time O((number of element in smaller size set) * (log(element in the bigger size set)) and find the kth element in O(log(size of given set)). what is the worst case complexity of this solution ? I think it is O(Nlog^2(N)) amortized. O(Nlog^2(N)) was it unacceptable ? Please help me.

3

Below is the code I tried Giving runtime error But other code which is almost similar works :

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Sets {
public static void main(String args[])throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = (br.readLine());
StringTokenizer st = new StringTokenizer(s," ");
int numberOfSets = Integer.parseInt(st.nextToken());
int numberOfCases = Integer.parseInt(st.nextToken());
ArrayList[] sets = new ArrayList[100000];
for(int i=0;i<=numberOfSets;i++)
{
sets[i]=new ArrayList();
sets[i].add(i+1);
}

	int newCombine = numberOfSets;
	for(int j=0;j<=numberOfCases;j++)
	{
		String cases = br.readLine();
		StringTokenizer casest = new StringTokenizer(cases," ");
		String condition = casest.nextToken();
		int int1 = Integer.parseInt(casest.nextToken());
		int int2 = Integer.parseInt(casest.nextToken());
		if(condition.equals("UNION"))
		{
			int set1 = int1;
			int set2 = int2;
			sets[newCombine] = new ArrayList<Integer>();
				sets[newCombine].addAll(sets[set1-1]);
				sets[newCombine].addAll(sets[set2-1]);
				Collections.sort(sets[newCombine]);
				sets[set1-1].clear();
				sets[set2-1].clear();
				newCombine++;
		}
		else if(condition.equals("GET"))
		{
			int set1 = int1;
			int minNum = int2;
			int Display = sets[set1-1].get(minNum-1);
			System.out.println(Display);
		}
		else
		{
			//System.out.println("Something wrong");
		}
	}
}

}

Please point out what I am doing wrong.

4

Any good tutorials for treap ?

5

that was the intended solution

6

STOP posting code!

7

Great problem! Congratulations!

8

This can be easily solved with segment trees too , we just need to use a pointer segtree. http://ideone.com/zhnLKC

3 Likes
9

Awesome solution. Thanks for sharing!

10

Why not a direct link to Author + Tester’s solutions, rather than via Ideone?

11

Why can’t we use merge operation as we do in merge sort for the union of two sets (O(n) ? I tried to use it, but it is giving TLE in subtask2. Even author also gave the same solution.

1 Like
12

some problem with the server

13

Author’s Solution gives TLE.

1 Like
14

it is supposed to. sorry i uploaded the wrong program

15

You’ve answered your own question!

16

Ideone is great!

17

@rajat1603, can u explain how is your code working , what are you storing in each node of segment tree ?

18

why author has added priority tag in his solution is there any use of tht… i think we can solve it without tht also … also right rotation and left rotation doesn’t seems to have any usefull…
please answer …

19

Can you explain how merge() works efficiently here?

1 Like
20

The merge is kind of brute force merge, let me explain it line by line.
node* merge(node* other)->this takes in the node to which we need to merge the current segtree and returns a pointer to the current segtree.
cnt+=other->cnt-since both nodes correspond to the same segment (l to r) we can just add the count of the other node to this.
if(other->left!=NULL)->if the left subtree exists in the other segtree , add that
if(left==NULL)left=other->left-instead of merging with brute,if current node doesnt have a left node we can just copy that node
left=left->merge(other->left) merge recursively.

1 Like