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.
Great problem! Congratulations!
This can be easily solved with segment trees too , we just need to use a pointer segtree. zhnLKC - Online C++0x Compiler & Debugging Tool - Ideone.com
3 Likes
Why not a direct link to Author + Tester’s solutions, rather than via Ideone?
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
Author’s Solution gives TLE.
1 Like
@rajat1603, can u explain how is your code working , what are you storing in each node of segment tree ?
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 …
Any good tutorials for treap ?
that was the intended solution
Awesome solution. Thanks for sharing!
some problem with the server
it is supposed to. sorry i uploaded the wrong program
You’ve answered your own question!
Can you explain how merge() works efficiently here?
1 Like
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
In the given solution above, union of two sets in case of treaps takes O(M.log(N/M)), whereas the merge operation would take O(M+N) which would be less compared to the one given.
M is always smaller than N. It will be O(N log^2 N) in the end.