×

DISHOWN - Editorial

Author: Vivek Hamirwasia
Tester: Shang Jingbo and Gerald Agapov
Editorialist: Devendra Agarwal

Easy

PREREQUISITES:

Set Union Data Structure

PROBLEM:

N chef's are there. Each chef has a dish which is given a value (denoted by S[i]). You need to answer 2 queries :
1. 0 x y : Chef containing dish x competes with chef containing dish y. If both dishes belong to same chef print "Invalid Query!" , otherwise the winner of the round will obtain all the dishes of the loser which will then be eliminated.
2. 1 x : Output the chef which contains the dish x.

Explanation

This problem can be solved using Disjoint set data structures.

Union Find or Disjoint Set Data structures allow you to merge two sets of items together dynamically and maintain for each item - to which set set does it belong.

This is exactly what we need in the problem , i.e. dynamically merging two sets and querying which set does an element belong.

We will be using Disjoint Set Data Structure that supports the following :

1. find(A) : Get the id of the disjoint set to which A belongs(i.e. the chef id which contains that dish).
2. union(A,B) : Merge the two disjoint sets in which A and B belong respectively.

Initially, we will create N disjoint set , each set contains 1 dish and it's owner.
Let dish x be in setA and dish y be in setB.
If the dish contained by the owner of setA has score higher than the dish contained by the owner of setB , then we will merge setA and setB and set the owner of setA as the overall owner of the merged set.
If the dish contained by the owner of setB has score higher than the dish contained by the owner of setA , then we will merge setA and setB and set the owner of setB as the overall owner of the merged set.

Note : You can easily prove from this that the owner of the set has dish whose score is higher than all other dish of the set.
We will be using only Path Compression heuristics to solve the problem.

Pseudo Code

Initialize parent[i] = i
Let S[i] denote the initial array.

int find(int i)
int j
if(parent[i]==i)
return i
else
j=find(parent[i])
//Path Compression Heuristics
parent[i]=j
return j

set_union(int i,int j)
int x1,y1
x1=find(i)
y1=find(j)
//parent of both of them will be the one with the highest score
if(S[x1]>S[y1])
parent[y1]=x1
else if ( S[x1] < S[y1])
parent[x1]=y1

solve()
if(query == 0)
Input x and y
px = find(x)
py = find(y)
if(px == py)
print "Invalid query!"
else
set_union(px,py)
else
Input x.
print find(x)


AUTHOR'S and TESTER'S Solution:

This question is marked "community wiki".

56273842
accept rate: 0%

19.8k350498541

2

I have solved with the same approach but was getting TLE as i was using Console.WriteLine to print all the output in C# . When i used the StringBuilder to store the messages and output in the last it passed the test cases. I am not sure if we have to consider this small optimization also

(14 Jul '14, 15:22) 2★

(14 Jul '14, 15:31) 2★

@mtbar131 : You didnt use path compression. That's what I could notice.

(14 Jul '14, 15:33)

@dev8546: Thanks for your comment. Now I understand the reason that I never got it AC. I couldn't think that Console.WriteLine() might be causing the problem. I kept on hitting my head thinking there might be a better optimized way to solve the problem and finally gave up on it after trying some micro optimizations :(

(14 Jul '14, 15:35)

Did the same in Java as dev8546 described. By printing System.out.println() it gets TLE. If i use a stringbuilder and output it at the end it passes. (I used both path compression and union by rank).

(14 Jul '14, 15:43) 4★

Just a quick check - Is this true with all languages or just the managed ones like C#/JAVA?

(14 Jul '14, 16:13)

author's solution is giving TLE. i think path compression technique is not working. i also used that method and got tle. pls check it.

(14 Jul '14, 23:56)

this code is giving TLE i cant understand why. http://www.codechef.com/viewsolution/4333486

(15 Jul '14, 19:48)
2

Authors' solution for this problem is wrong. It gives TLE because it doesn't use path compression.

(23 Jul '14, 02:12) 5★

What is the need of using find() function again in set_union() when we are already passing set_union() the parents of the 2 dishes?

(03 Sep '14, 18:42)
showing 5 of 10 show all

 1 @kuruma thanks for this question i learnt something new. first tiny mistake is the output of second query type you should print find(x)+1 as your numbers are 0-based . secondly you have used "ios_base::sync_with_stdio(false)" that seems to cause your output to be buffered and is printed together only when the program terminates. this would have been correct had you used puts/printf in output of 2nd query as well. since you used cout that output is not buffered and printed instantly while the output of all first queries is printed in the end. So what you can do: 1.use fflush(stdout) after puts statement 2.use cout 3.NOT use ios_base::sync_with_stdio(false); 4.use puts/printf in the output of 2nd query as well answered 20 Jul '14, 01:36 442●1●6●10 accept rate: 13% Thanks a lot @shubham12 , I switched puts to cout and used the +1 trick and got AC :D Really, really thanks a lot :) And the seudo-code from editorial was also really well written :D Hope I can start doing this more often (20 Jul '14, 01:48) kuruma3★ glad i could help :). though i had some incorrect understanding of the effect of "ios_base::sync_with_stdio(false)". i have to read it up. (20 Jul '14, 01:51)
 0 Hello, can anyone tell why TLE: http://www.codechef.com/JULY14/status/DISHOWN,squal Thanks. answered 14 Jul '14, 15:29 4★squal 1.2k●4●15●33 accept rate: 14% 2 don't use System.out.println(), instead use StringBuilder to store answers and then in the end use System.out.println() to print StringBuilder object. I have modified your code it has got accepted. Link to ur code: http://www.codechef.com/status/DISHOWN,sousnake (see the accepted solution). (14 Jul '14, 16:03) sousnake3★ @sousnake: thanks :) bad that i missed this because of System.out.println() :( (14 Jul '14, 16:49) squal4★
 0 admins...plz see my code ..http://www.codechef.com/viewsolution/4328720 ..used same approach ..stll TLE.!!..its really annoying .. answered 14 Jul '14, 15:37 114●1●4●7 accept rate: 11% 1 http://www.codechef.com/viewsolution/4329418 (14 Jul '14, 16:05) 1 yeah ..the path compression heuristics...really had an opportunity to learn.. btw real thanx. :) (14 Jul '14, 16:32)
 0 Hai, I don't know whether I can post this or not ,Here are some unofficial test cases categorised into small,medium,large.Who are getting mainly WA but also RTE,TLE,... can also check.You may need not worry about the constraints.the values are guarenteed to be in the given constraints. answered 14 Jul '14, 15:38 2.2k●6●17●48 accept rate: 10% i have tried all your test files for DISHOWN and got all correct output.. but NZEC in codechef .. see the below comment /!\ (14 Jul '14, 22:04)
 0 Can anybody tell me why i was getting Runtime Error(NZEC) in java (i have used the same union-find logic)?? here is the code => http://www.codechef.com/viewsolution/4303110 When i transformed the same logic in c++, it got accepted... here is ACed c++ code => http://www.codechef.com/viewsolution/4303214 Thanx in Advance :) answered 14 Jul '14, 15:39 1 accept rate: 0% I think the problem was in your function owner. I have modified that function just a bit and it got accepted. Here's the link: http://www.codechef.com/viewsolution/4329762 (14 Jul '14, 17:39) sousnake3★ what is the difference between these two functions?? : function 1 : gave AC static int owner(int x) { if(p[x] == x) return x; else { int var = owner(p[x]); p[x] = var; return p[x]; } }  function 2: gives NZEC static int owner(int x) { if(p[x] == x) return x; else { p[x] = owner(p[x]); return p[x]; } }  (14 Jul '14, 19:19) no I think the problem was that: (this was your original code) static int owner(int x) { if(p[x] == x) return x; else return p[x]=owner(p[x]); } here may be the problem was with assignment operator (i am not sure how it works but it works differently in java and C++). (15 Jul '14, 18:58) sousnake3★
 0 I used UF data structure with path compression but still got TLE. Why would the program run into TLE when using System.out.println()? Can anybody explain that? answered 14 Jul '14, 16:54 2★nastra 15●3●3●5 accept rate: 0% System.out.println() is slow .. use BufferedWriter or BufferedOutputStream for fast IO see my code for reference : http://www.codechef.com/viewsolution/4330077 (15 Jul '14, 21:37)
 0 Can anyone tell what's wrong with my code?Getting WA. Code answered 14 Jul '14, 17:14 3★itsmepsk 162●1●2●6 accept rate: 0%
 0 anyone would tell wats wrng in my code .. its same as that of the editorial !!!!! the link of the solution is http://www.codechef.com/viewsolution/4326802 .. any help is seriously welcomed answered 14 Jul '14, 19:18 5★meintoo 33●1●3●6 accept rate: 16% http://ideone.com/jN6HUM You code gives WA for the test case Mentioned on this link. Also i have commented in one line where i have done the edit. After this, use fast I/O and it should give AC. (14 Jul '14, 23:53) damn_me3★
 0 i don't know about how the test cases were designed but still if this algorithm is implemented with union by rank it will give better performance.I am a bit disappointed that my code that should have been accepted with better performance gave TLE if anybody can explain the reason for this do reply.... answered 14 Jul '14, 19:28 46●2 accept rate: 0%
 0 In Java BufferedReader is giving TLE. Even taking only input without processing anything it gives TLE.Why this happened for java Language. It run smoothly for scanf in c if it fastio problem then it should give TLE for scanf also. This is my code in which only input is getting take by program and for this it is giving TLE. answered 14 Jul '14, 20:46 1●2 accept rate: 0% 1 i think you should use BufferdOutputStream instead of System.out.println see my code for reference : http://www.codechef.com/viewsolution/4330077 (15 Jul '14, 21:41) @aq_faridi I took only input then also I got TLE. (15 Jul '14, 22:06)
 0 http://www.codechef.com/viewsolution/4280360 I didn't use set operations as I was worried about the time required and all that memory allocation. Simply used the transitive relations between dish owners as owner(a)-->owner(b). Simple and alternate solution. answered 14 Jul '14, 23:35 4★gkcs 2.6k●1●11●28 accept rate: 9%
 0 help me in finding why this is giving TLE http://www.codechef.com/viewsolution/4333486 answered 15 Jul '14, 19:46 1 accept rate: 0%
 0 Hi my python code is giving a wrong answer and I am not able to find the problem . please help. code answered 15 Jul '14, 20:21 2★vedansh 1 accept rate: 0%
 0 http://www.codechef.com/viewsolution/4315955 Can anyone help me....i used same approach but get WA!!!! yes WA 3 times....um totally bang!!PLs help :( answered 15 Jul '14, 20:36 1 accept rate: 0%
 0 Can anyone tell me why I am getting Run time error (seg segv) even after getting the correct output? http://www.codechef.com/viewsolution/4344251 Thanks in advance! answered 19 Jul '14, 14:56 2★kavyanr 1 accept rate: 0%
 0 Hello, I tried to follow the pseudo-code given above and implement the code for UF... But I'm getting WA... Can anyone tell me if something is very, very wrong here? #include using namespace std; #define MAXN 100005 vector parent(MAXN); vector S(MAXN); int query,x,y,N,Q,px,py; int find(int i) { int j; if(parent[i]==i) return i; else { j=find(parent[i]); parent[i]=j; return j; } } void set_union(int i, int j) { int x1,y1; x1 = find(i); y1 = find(j); //parent of both of them will be the one with the highest score if(S[x1]>S[y1]) parent[y1]=x1; else if(S[x1] < S[y1]) parent[x1]=y1; } void init(int N) { S.resize(N); parent.resize(N); for(int i = 0; i < N;i++) parent[i]=i; } void solve(int query) { if(query == 0) { cin >> x >> y; x--; y--; px = find(x); py = find(y); if(px == py) puts("Invalid query!"); else set_union(px,py); } else { cin >> x; x--; cout << find(x) << endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--) { cin >> N; init(N); for(int i = 0; i < N; i++) { cin >> S[i]; } cin >> Q; while(Q--) { cin >> query; solve(query); } } return 0; }  Thanks in advance, Bruno answered 19 Jul '14, 22:47 3★kuruma 17.7k●72●143●209 accept rate: 8% I think you should call your set union function with x and y...(not px and py)...and start your indices from 1(not 0) in array.....look this solution http://www.codechef.com/viewsolution/4333293 (20 Jul '14, 00:37) i have posted it as an answer as the word limit on comments is too low @shivam217 no,thats not the correct reason (20 Jul '14, 01:36) @shubham12 thanks for pointing out the mistake.. (20 Jul '14, 02:25)
 0 http://www.codechef.com/viewsolution/7146440 I am getting runtime error. can any check my code, i don't know in what test case i am getting this error. answered 09 Jun '15, 12:39 2★tamil_c 1●1 accept rate: 0%
 0 I don't know while my code is getting TLE. Can anyone please help? Here is my link of code: https://www.codechef.com/viewsolution/10644025 Thanks. answered 30 Jun '16, 13:11 0★apurdas 1 accept rate: 0%

can anyone tell me whats wrong in solution :

define MOD 1000000007

using namespace std; typedef vector<int> V; typedef long long i64; const long long LINF = (long long)1e16 + 5; const int maxn=1e5+1; int arr[1000000],score[1000000],n; void initialize() { for(int i=0;i<n;i++) { arr[i]=i; } } int root(int x) { int y = x; while (x != arr[x]) { x = arr[x]; } for (;y != x;) { int t = arr[y]; arr[y] = x; y = t; } return x; }

int main() { int t; cin>>t; while(t--) { int i,q,root_l,root_r; cin>>n; for(i=0;i<n;i++) {="" cin="">>score[i]; } initialize(); cin>>q; while(q--) { int x,l,r; cin>>x; if(x==0) { cin>>l>>r; --l,--r; root_l=root(l); root_r=root(r); if(root_l==root_r) cout<<"Invalid query!\n"; else { if(score[root_l]>score[root_r]) { arr[root_r]=root_l; } else if(score[root_l]<score[root_r]) {="" arr[root_l]="root_r;" }="" }="" }="" else="" {="" cin="">>l; root_l=root(l); cout<<root_l+1<<endl; } } } }

2★vickycod
21112
accept rate: 6%

 0 Can Someone point out the mistake in my code?plz https://www.codechef.com/viewsolution/14346397 answered 26 Jun '17, 16:38 166●7 accept rate: 0%
 0 Can anyone explain me the meaning of this statement? . Each of the chefs can then choose any one dish to battle against the other chef and the one having the dish with the higher score will win this round answered 30 Jan '18, 10:04 1 accept rate: 0%
 0 LEARN PATH_COMPRESSION from https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/ answered 25 Mar '18, 19:55 4★siva2697 21●3 accept rate: 0%
 0 Hey I'm getting WA for the following code. What could be the problem? I'm using path compression in root function. answered 19 Mar, 16:57 1 accept rate: 0%
 -1 I have used the same algorithm.It gives AC in C++ while the same algorithm when coded in scala gives TLE. Link of AC submission :http://www.codechef.com/viewsolution/4229817 Link of scala submission :http://www.codechef.com/viewsolution/4230294 Can anyone tell me what's wrong with the submission in scala? answered 14 Jul '14, 17:19 2★knb_dtu 410●6●20 accept rate: 22%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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
×3,820
×121
×67
×24
×20

question asked: 14 Jul '14, 15:01

question was seen: 13,535 times

last updated: 19 Mar, 16:57