DISHOWN - Editorial

devuy11 · July 14, 2014, 3:01pm

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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*). You need to answer 2 queries :

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.
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 :

find(A) : Get the id of the disjoint set to which A belongs(i.e. the chef id which contains that dish).
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  
Let S* denote the initial array.

int find(int i)
	int j
	if(parent*==i)
            	return i
	else
		j=find(parent*)
		//Path Compression Heuristics
		parent*=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:

Author’s solution
Tester’s solution

squal · July 14, 2014, 3:29pm

Hello,

can anyone tell why TLE: http://www.codechef.com/JULY14/status/DISHOWN,squal

Thanks.

rachilies · July 14, 2014, 3:37pm

admins…plz see my code …http://www.codechef.com/viewsolution/4328720 …used same approach …stll TLE.!!..its really annoying …

achaitanyasai · July 14, 2014, 3:38pm

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.

aq_faridi · July 14, 2014, 3:39pm

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

nastra · July 14, 2014, 4:54pm

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?

itsmepsk · July 14, 2014, 5:14pm

Can anyone tell what’s wrong with my code?Getting WA.


[1]


  [1]: http://ideone.com/zsBeu5

knb_dtu · July 14, 2014, 5:19pm

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?

meintoo · July 14, 2014, 7:18pm

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

vaibhav9518s · July 14, 2014, 7:28pm

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…

shivamsharma · July 14, 2014, 8:46pm

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


[1] in which only input is getting take by program and for this it is giving **TLE**.

[1]:http://www.codechef.com/viewsolution/4270212

gkcs · July 14, 2014, 11:35pm

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.

abhishekjhaji · July 15, 2014, 7:46pm

help me in finding why this is giving TLE
http://www.codechef.com/viewsolution/4333486

vedansh · July 15, 2014, 8:21pm

Hi my python code is giving a wrong answer and I am not able to find the problem . please help.


[1]


  [1]: http://www.codechef.com/viewsolution/4333615

y_so_serious · July 15, 2014, 8:36pm

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

kavyanr · July 19, 2014, 2:56pm

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!

kuruma · July 19, 2014, 10:47pm

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 <bits/stdc++.h>
using namespace std;
#define MAXN 100005

vector<int> parent(MAXN);
vector<int> S(MAXN);
int query,x,y,N,Q,px,py;

int find(int i)
{
	int j;
	if(parent*==i)
		return i;
	else
	{
		j=find(parent*);
		parent*=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;
}

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*;
		}
		cin >> Q;
		while(Q--)
		{
			cin >> query;
			solve(query);
		}
	}
	return 0;
}

Thanks in advance,

Bruno

shubham12 · July 20, 2014, 1:36am

@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

tamil_c · June 9, 2015, 12:39pm

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.

vickycod · April 9, 2016, 6:49pm

https://www.codechef.com/viewsolution/9892837
i’m getting tle i used same logic of editorial.Please help me
Thanks in advance.