DISHOWN - Editorial

editorial
, , , , ,
21

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];
    }
}
22

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…

23

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
24

i have tried all your test files for DISHOWN and got all correct output…
but NZEC in codechef …

see the below comment /!\

25

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.

26

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.

27

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.

28

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

29

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

30

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

31

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
32

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

33

System.out.println() is slow … use BufferedWriter or BufferedOutputStream for fast IO
see my code for reference :
http://www.codechef.com/viewsolution/4330077

34

i think you should use BufferdOutputStream instead of System.out.println
see my code for reference : http://www.codechef.com/viewsolution/4330077

1 Like
35

@aq_faridi I took only input then also I got TLE.

36

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!

37

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]==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

38

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

39

@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

1 Like
40

i have posted it as an answer as the word limit on comments is too low
@shivam217 no,thats not the correct reason