DISHOWN - Editorial

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

Author’s solution
Tester’s solution

7 Likes

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

2 Likes

Hello,

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

Thanks.

I have used same approach but I am getting TLE http://www.codechef.com/viewsolution/4294855 please help me!

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

@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 :frowning:

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

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.

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

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

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

2 Likes

http://www.codechef.com/viewsolution/4329418

1 Like

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

yeah …the path compression heuristics…really had an opportunity to learn… btw real thanx. :slight_smile:

1 Like

@sousnake: thanks :slight_smile: bad that i missed this because of System.out.println() :frowning:

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?

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


[1]


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

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?

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

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

//