11686 - Pick up sticks

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11686 How can

Post by arifcsecu » Sun Oct 18, 2009 5:04 pm

removed
Last edited by arifcsecu on Mon Oct 19, 2009 10:59 am, edited 1 time in total.
Try to catch fish rather than asking for some fishes.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 11686 How can

Post by saiful_sust » Mon Oct 19, 2009 5:33 am

Thanks arifcsecu.......
ur too much helpful........

keep posting ......
Another thing PLz remove ur post .... :D

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

Re: 11686 How can

Post by Bruno » Tue Nov 03, 2009 5:55 pm

I am getting WA, anybody could give me another sample input (one that may fail)?

I tried this:

Code: Select all

4 3
4 1
1 2
3 2
3 2
1 2
2 3
4 4
2 1
3 2
4 3
2 4
0 0
And output is:

Code: Select all

4
1
3
2
1
2
3
IMPOSSIBLE
Just like the toolkit :o
Last edited by Bruno on Wed Nov 04, 2009 12:09 am, edited 1 time in total.

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

Re: 11686 How can

Post by Bruno » Wed Nov 04, 2009 12:09 am

Got accepted, I was forgetting to clear the vectors :oops:

Anyway, I needed to change from cin to scanf! With cin I got TLE! This should be considered by the judges as cin/scanf should not interfere in the algorithm complexity and performance :-? Should it??? :o

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11686 How can

Post by arifcsecu » Wed Nov 04, 2009 6:31 pm

Read previous post
Try to catch fish rather than asking for some fishes.

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

Re: 11686 How can

Post by Bruno » Wed Nov 04, 2009 11:42 pm

arifcsecu wrote:Read previous post
Which one? :o

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11686 How can

Post by arifcsecu » Sun Nov 08, 2009 11:09 am

Cin and cout take more time than scanf and printf
Try to catch fish rather than asking for some fishes.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 11686 How can

Post by serur » Wed Jan 06, 2010 7:07 am

Now I see how that color stunt is helpful in dfs. In the sample input above one edge is given twice, so it is easy to mistake it for a cycle during dfs, if one doesn't use colors.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11686 How can

Post by arifcsecu » Fri Apr 02, 2010 6:04 pm

Exactly correct.
Back edge can easily be detected using color arrary
Try to catch fish rather than asking for some fishes.

Rashad
New poster
Posts: 17
Joined: Tue Dec 22, 2009 4:20 pm

Re: 11686 How can

Post by Rashad » Thu Sep 23, 2010 3:46 am

I am getting WA. Give me some test case. Thanks in advance.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11686 How can

Post by sohel » Thu Sep 23, 2010 7:33 am

You can test your code with your own test cases using this site: http://uvatoolkit.com/problemssolve.php

Rashad
New poster
Posts: 17
Joined: Tue Dec 22, 2009 4:20 pm

Re: 11686 How can

Post by Rashad » Fri Sep 24, 2010 4:14 am

I tried that. But I was getting WA. Now I got AC. I was making some silly mistakes in initialization. Thanks a lot. :)

ujjal.ruet
New poster
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm
Location: Dhaka,Bangladesh
Contact:

11686 TLE

Post by ujjal.ruet » Thu Jan 26, 2012 1:34 pm

Getting tle.
Can anyone give some idea to minimise time?

Code: Select all


#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<vector>
#include<map>
#include<string>

using namespace std;
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define infile(a) freopen(a,"r",stdin)

#define diff(a,b) a>b? (a-b):(b-a)
#define MAXINT (int)(pow(2,31)-1)
#define inf pow(2,31)-1
#define ss 1000002

vector< vector < pair<int,int> > > G(ss);
//int G[ss][ss];
int visited[ss];
int V, E;
int i,j,k,u,v;
int list[ss],indegree[ss];


void init()
{
    for(int i=0; i<ss; i++)
    {
        visited[i]=0;
        indegree[i]=0;
        G[i].clear();
    }
}


void topsort()
{
// when G[a][b] = 1, that means a must come before b
// indegree[i] = number of items that that must come before i
// when taken[i] = 1, means we already have taken ith item
    int invalid = 0,p,l,s;
    for(i=0; i<V; i++)
    {
        for(j=0; j<V; j++)
            if( !indegree[j] && !visited[j] )
            {
                visited[j] = 1;
                list[i] = j+1;
                // in this step we are taking item j
                // we'd update the indegree[k] of items that depended on j

                for(k=0; k<G[j].size(); k++)
                {
                    p=G[j][k].first;
                    s= G[j][k].second;

                    if( !visited[s] && p )
                        --indegree[s];
                }
                break;
            }
        if( j == V )
        {
            invalid = 1;
            break;
        }
    }

    if( invalid )
        printf("IMPOSSIBLE\n");
    else


        for(i=0; i<V; i++)
        {
            printf("%d\n", list[i] );
        }
}

int main()
{

    //freopen("10305.txt","r",stdin);

    int m,n;

    while(scanf("%d %d",&V,&E)==2)
    {


        if(V==0 && E==0)
            break;

        init();


        for(i=0; i<E; i++)
        {
            scanf("%d %d",&u,&v);
            //G[u-1][v-1]=1;   // using 0 to n-1
            G[u-1].push_back(make_pair(1,v-1));

            indegree[v-1]++;
        }





        /* k=0;
         if(E>0)
         {
        //finding the first node which has no predecessor defined.
             for(i=0; i<V; i++)
             {
                 if( (l[i]==1 && r[i]==0 ) )
                     break;
             }
             dfs(i);
         }
         else*/
        topsort();

    }
    return 0;
}

Thanks in advanced.

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11686 How can

Post by Scarecrow » Sun Apr 22, 2012 8:10 pm

can't find the bug in my code. plz help someone..

Code: Select all

AC :D
be sure to clear the vectors before each test case. i got WA for this reason
Do or do not. There is no try.

MauriWilde
New poster
Posts: 14
Joined: Sun Jan 20, 2013 1:58 am

11686 - Pick up sticks WA Please Help

Post by MauriWilde » Sun Jun 01, 2014 9:34 pm

I can't figure out why I'm getting WA :/ could you help me?

My code (c++):

Code: Select all

 Removed after AC
Thank you in advance ^-^

UPD: I was checking cycles existence wrong.

Post Reply

Return to “Volume 116 (11600-11699)”