DISHOWN - Editorial

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.

can anyone tell me whats wrong in solution :
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define FOR(a,b) for(i=a;i<b;i++)
#define RFOR(a,b) for(i=a;i>=b;i–)
#define MOD 1000000007
using namespace std;
typedef vector 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®;
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;
}
}
}
}

Can Someone point out the mistake in my code?plz
https://www.codechef.com/viewsolution/14346397

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

LEARN PATH_COMPRESSION from https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/

Hey I’m getting WA for the following


[1]. What could be the problem? 
I'm using path compression in root function.


  [1]: https://www.codechef.com/viewsolution/23624285

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

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:

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

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

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

see the below comment /!\

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.