DISHOWN - Editorial

editorial
, , , , ,
20

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

21

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.

22

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

23

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

24

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

25

LEARN PATH_COMPRESSION from Topcoder

26

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
27

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
28

I have used same approach but I am getting TLE CodeChef: Practical coding for everyone please help me!

29

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

30

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

31

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

32

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:
CodeChef: Practical coding for everyone
(see the accepted solution).

2 Likes
33

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

1 Like
34

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

35

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

1 Like
36

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

37

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: CodeChef: Practical coding for everyone

38

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

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

see the below comment /!\