10557 - XYZZY

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

Moderator: Board moderators

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Mon Oct 31, 2005 8:39 pm

I used Bellman-Ford algorithm with some modifications. Here's a sample input/output:

Input

Code: Select all

5
0 1 2
-60 1 3
-60 1 4
20 1 5
0 0
5
0 1 2
20 1 3
-60 1 4
-60 1 5
0 0
5
0 1 2
21 1 3
-60 1 4
-60 1 5
0 0
5
0 1 2
20 2 1 3
-60 1 4
-60 1 5
0 0
7
0 1 2
-98 2 3 5
-1 1 4
101 1 1
-60 1 6
-60 1 7
0 0 
8
0 1 2
0 1 3
-5 1 4
-50 1 5
-40 2 6 7
110 1 3
0 1 8
0 0
1
0 0

7
0 2 2 6
-60 1 3
100 1 4
100 1 5
100 1 2
-120 1 7
0 0

-1
Output

Code: Select all

hopeless
hopeless
winnable
winnable
winnable
winnable
winnable
hopeless
Daniel
UFRN HDD-1
Brasil

deadlineruhe
New poster
Posts: 2
Joined: Fri Sep 11, 2009 10:00 am

Re: 10557 - XYZZY

Post by deadlineruhe » Sat Nov 13, 2010 11:16 am

I am getting WA...
Please someone help me...

Code: Select all

AC

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10557 - XYZZY

Post by Shafaet_du » Fri May 06, 2011 10:46 pm

I ran floyed modified and dijikstra to solve the problem. You CanT guarantee a win only if a positive cycle exists,thats the case which caused me wa.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 10557 - XYZZY

Post by Imti » Wed May 18, 2011 10:30 am

My code passed all the input found here.But still getting WA...I tried it by BFS and Floyod..Please give me some test case...

Code: Select all

#include<cstdio>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
#define MAXINT -1000000000
#define MAX 2000000000
typedef vector<long>vi;
vi adj[120],cost[120];
queue<long>q;  
long total,w[120],d[120],e,P[120][120];
bool C[120][120];
void floyod()
{
     long k,i,j;
     for(k=1;k<=total;k++)
      for(i=1;i<=total;i++)
       for(j=1;j<=total;j++)
       {
         if(P[i][j]<P[i][k]+P[k][j])
           P[i][j]=P[i][k]+P[k][j];
         C[i][j]=C[i][j]|(C[i][k]&C[k][j]);
       }
}
void bfs()
{
     long u,v,i;
     while(!q.empty())
     {
       u=q.front();q.pop();
       if(C[u][u]&&P[u][u]>0)
        d[u]=MAX;
       for(i=0;i<adj[u].size();i++)
       {
         v=adj[u][i];
         if(d[v]!=MAX&&d[v]<d[u]+w[v])
         {
           if(d[u]==MAX)
           d[v]=MAX;
           else
           d[v]=d[u]+w[v];
           q.push(v);
         }
       }
     }
}
int main()
{
   long a, b,j,c,i;
   while(scanf("%ld",&total)==1&&total!=-1)
   {
    e=1;
    for(i=1;i<=total;i++)
     for(j=1;j<=total;j++)
      {P[i][j]=MAXINT;C[i][j]=0;}
   for(i=1;i<=total;i++) 
   {
     scanf("%ld %ld",&c,&a);
     w[i]=c;
     for(j=1;j<=a;j++)
     {
       scanf("%ld",&b);
       adj[i].push_back(b);
       C[i][b]=1;
     }
     d[i]=MAXINT;
   }
   for(i=1;i<=total;i++)
     for(j=1;j<=total;j++)
        if(C[i][j])
         P[i][j]=w[j];
   floyod();
   d[1]=0;
   q.push(1);
   bfs();
   d[total]+=100;
   if(total==1||d[total]>0)
     printf("winnable\n");
   else 
     printf("hopeless\n");
     for(i=1;i<=total;i++)
      adj[i].clear();
  }
  return 0;
}


Nuptxxp
New poster
Posts: 2
Joined: Sun Dec 04, 2011 3:59 pm

Re: 10557 - XYZZY

Post by Nuptxxp » Sun Dec 04, 2011 4:07 pm

Could anyone tell me how to use bfs or floyd ?
i've no idea for this problem
THX

Nuptxxp
New poster
Posts: 2
Joined: Sun Dec 04, 2011 3:59 pm

Re: 10557 - XYZZY

Post by Nuptxxp » Tue Dec 06, 2011 9:54 am

I got AC but i find the test date maybe is not serious
like this date:

Code: Select all

15
0 2 2 11
-10 1 3
-10 1 4
-10 1 5
-10 1 6
-10 1 7
-10 1 8
-10 1 9
-10 1 10
-10 1 13
50 1 12
50 1 11
11 2 10 14
-100 1 15
0 0
i saw a program on the web which can't pass this date but got AC
in other words,the test date don't include this states: there are two circles but the closer circle can't connect to the end room but the other do.(like my test date)
sorry for my bad english(english is not my first language)

RagingForce
New poster
Posts: 1
Joined: Fri Feb 10, 2012 5:40 pm

Re: 10557 - XYZZY

Post by RagingForce » Fri Feb 10, 2012 7:23 pm

Hi I was wondering if anyone else tried to do this problem recursively?

ze^1
New poster
Posts: 1
Joined: Mon Aug 20, 2012 12:24 pm

Re: 10557 - XYZZY

Post by ze^1 » Mon Aug 20, 2012 12:36 pm

the offical test number seems to be not completely enough?
such as this group of number. one of the AC program can't pass this correctly.

Code: Select all

6
0 2 2 3
1 1 4
3 2 2 4
-100 1 5
-100 1 6
0 0
-1

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10557 - XYZZY

Post by mahade hasan » Tue Jul 02, 2013 11:22 pm

why WA why why why????

Code: Select all

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;

int main()
{
    int I,K,L,M,N;
    while(scanf("%d",&N)&&N>-1){
        int V[110],D[110],H[110];
        vector<int>Edge[110];
        for(I=1;I<=N;I++){
            D[I]=-1000;
            H[I]=0;
        }
        D[1]=100;
        H[1]=100;
        for(I=1;I<=N;I++){
            scanf("%d %d",&V[I],&M);
            while(M--){
                scanf("%d",&L);
                Edge[I].push_back(L);
            }
        }
        bool Flag=1;
        for(I=1;I<=N;I++){
            for(K=0;K<Edge[I].size();K++){
               if(D[I]>0) Flag=0;
               //printf("D[%d]=%d D[%d]=%d V[%d]=%d\n",Edge[I][K],D[Edge[I][K]],I,D[I],Edge[I][K],V[Edge[I][K]]);
               if(D[Edge[I][K]]<D[I]+V[Edge[I][K]])
                 D[Edge[I][K]]=D[I]+V[Edge[I][K]];
                // printf("D[%d]=%d D[%d]=%d V[%d]=%d\n",Edge[I][K],D[Edge[I][K]],I,D[I],Edge[I][K],V[Edge[I][K]]);
                
               //if(H[Edge[I][K]]<H[I]+V[Edge[I][K]])
                // H[Edge[I][K]]=H[I]+V[Edge[I][K]];
            }
        }
        //printf("%d  %d\n",D[N],Flag);
        for(I=1;I<=N;I++){
            for(K=0;K<Edge[I].size();K++)
               if(D[I]>-101&&D[Edge[I][K]]>-101&&(D[Edge[I][K]]<D[I]+V[Edge[I][K]])){
                    //printf("D[%d]=%d D[%d]=%d V[%d]=%d\n",Edge[I][K],D[Edge[I][K]],I,D[I],Edge[I][K],V[Edge[I][K]]);
                    Flag=true;
                    I=N+1;
                    break;
                }
        }//printf("%d  %d\n",D[N],Flag);
        for(I=1;I<=N;I++){
            for(K=0;K<Edge[I].size();K++)
               if(D[I]>-101&&D[Edge[I][K]]>-101&&D[Edge[I][K]]>D[I]+V[Edge[I][K]]){
                    Flag=0;
                    I=N+1;
                    break;
                }
        }
        //printf("%d  %d\n",D[N],Flag);
        if(D[N]>0||Flag) printf("winnable\n");
        else printf("hopeless\n");
    }
    return 0;
}

[/color]
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10557 - XYZZY

Post by brianfry713 » Thu Jul 04, 2013 1:31 am

After running Bellman-Ford, check for infinite energy cycles. If you can reach the exit from any of those rooms, then it's winnable.
Check input and AC output for thousands of problems on uDebug!

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

10557 - XYZZY WA

Post by hpjhc » Mon Aug 05, 2013 11:39 am

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

int visit[101];
int G[101][101];
int weight[101];
int to[101];
int dfs(int , int, int);
int bfs(int , int);
int main(void)
{
int n, i, m, k;
while(scanf("%d", &n), n != -1)
{
memset(G, 0, sizeof(G));
memset(visit, 0, sizeof(visit));
for(i = 0; i < n; i++)
{
scanf("%d", &weight[i+1]);
scanf("%d", &m);
k = 0;
while(m--)
scanf("%d", &G[i+1][k++]);
}
printf("%s\n", dfs(1, n, 100) ? "winnable" : "hopeless");
}
return 0;
}

int dfs(int x, int n, int sum)
{
int i, t, j, s;
if(x == n)
{
if(sum > 0)
return 1;
}
visit[x] = -1;
for(i = 0; G[x] != 0; i++)
{
t = G[x];
if(visit[t] == 0)
{
to[t] = x;
if(dfs(t, n, sum+weight[t]))
return 1;
}
else if(visit[t] == -1)
{
for(j = x, s = 0; j != t; j = to[j])
s += weight[j];
s += weight[t];
if(s > 0)
{
if(bfs(t, n))
return 1;
}
}
}
visit[x] = 1;
return 0;
}

int bfs(int x, int n)
{
int queue[101];
int V[101];
int first, last, i, t, temp;
first = 0;
last = 1;
queue[0] = x;
V[x] = 1;
memset(V, 0, sizeof(V));
while(first < last)
{
temp = queue[first];
for(i = 0; G[temp] != 0; i++)
{
t = G[temp];
if(t == n)
return 1;
if(!V[t])
{
V[t] = 1;
queue[last++] = t;
}
}
first++;
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10557 - XYZZY WA

Post by brianfry713 » Wed Aug 07, 2013 12:19 am

Input:

Code: Select all

4
0 1 2
-100 1 3
1 1 4
0 0
-1
AC output:

Code: Select all

hopeless
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10557 - XYZZY

Post by Mukit Chowdhury » Wed Aug 06, 2014 12:04 pm

A case, for which I have got the verdict WA ... :/

Code: Select all

7
0 1 2
-90 1 3
-90 1 4
100 1 5
100 1 6
100 3 1 4 7
0 0
answer must be
hopeless

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

Re: 10557 - XYZZY

Post by LazyTym » Mon Oct 13, 2014 9:30 pm

why getting Wrong Ans.pls help..........

Code: Select all

#include<iostream>
#define INF -9999999
#define MAX 10000

using namespace std;
int num_edge;

struct Edge {
public:
    int start;
    int des;
    int weight;
};

struct Graph {
public:
    int v;
    Edge* edge;
};

Graph* create_Graph(int v) {
    Graph* graph=new Graph();
    graph->v=v;
    graph->edge=new Edge[MAX];

    return graph;
}

int BELLMAN_FROD(Graph* graph) {
    int V=graph->v;
    int E=num_edge;
    int dist[V];


    for(int i=1;i<=V;i++) dist[i]=INF;
    dist[1]=100;

    for(int i=0;i<V;i++) {
        for(int j=0;j<E;j++) {
            int u=graph->edge[j].start;
            int v=graph->edge[j].des;
            int w=graph->edge[j].weight;


            if(dist[u]!=INF && dist[v]<dist[u]+w && (dist[u]+w)>0) {
                if(v==V) {
                    cout<<"winnable"<<endl;
                    return 0;
                }

                dist[v]=dist[u]+w;
            }
        }
    }

    int flag=0;
    for(int i=0;i<E;i++) {
        int u=graph->edge[i].start;
        int v=graph->edge[i].des;
        int w=graph->edge[i].weight;

        if(dist[u]!=INF && dist[v]<dist[u]+w && (dist[u]+w)>0) {
            flag=1;
            break;
        }
    }

    if(flag==1) cout<<"winnable"<<endl;
    else {
        if(dist[V]>0) cout<<"winnable"<<endl;
        else cout<<"hopeless"<<endl;
    }
}

int main()
{
    int num_vertex,weight,num_doors,x;
    while(1) {
        cin>>num_vertex;
        if(num_vertex==-1) break;
        num_edge=0;
        Graph* graph=create_Graph(num_vertex);

        for(int i=1;i<=num_vertex;i++) {
            cin>>weight;
            cin>>num_doors;
            for(int j=1;j<=num_doors;j++) {
                cin>>x;
                graph->edge[num_edge].start=i;
                graph->edge[num_edge].des=x;
                graph->edge[num_edge].weight=weight;
                num_edge++;
            }
        }
        BELLMAN_FROD(graph);
    }
    return 0;
}

thanks in Advanced

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10557 - XYZZY

Post by Mukit Chowdhury » Tue Oct 14, 2014 7:31 am

LazyTym wrote:why getting Wrong Ans.pls help..........
thanks in Advanced

Check this case :

Code: Select all

6
0 1 2
5 1 3
5 2 1 4
-100 0
-100 2 4 6
0 0
output must be...

Code: Select all

hopeless

Post Reply

Return to “Volume 105 (10500-10599)”