336 WA

[nishith]

Getting WA , don't know why.
please give me some critical inputs or help me to find the bugs.

Code: Select all

ACC



[abid_iut]

Can anyone tell where is the problem please...
here is the code

Code: Select all

#include<iostream>
#include<cstdio>
#include<queue>
#define MAX 100
using namespace std;

int path[MAX][MAX];
int distinct[MAX];
int flag[MAX];
int n,index;
int ccount;
long dist[MAX];
queue<int>map;

void initiation(){
   int i,j;
   for(i=0; i<MAX; i++){
      for(j=0; j<MAX; j++){
         path[i][j] = 0;
      }
      distinct[i] = 0;
      flag[i] = 0;
   }
}

void distini(){
   int i;
   for(i=0; i<MAX; i++)
      dist[i] = 2147483647;
}

void bfs(int start){
   int temp;
   int flag = 0;
   while(!map.empty()){
      map.pop();
   }
   
   map.push(start);
   dist[start] = 0;
   while(!map.empty()){
      temp = map.front();
      map.pop();
      for(int i=0; i<index; i++){
         if(distinct[i] != temp){
            if(path[temp][distinct[i]]==1){
               if(dist[distinct[i]] > dist[temp] + 1){
                  dist[distinct[i]] = dist[temp] + 1;
                  map.push(distinct[i]);
               }
            }
         }
      }
   }
}

int main(){
   int i,j;
   int a,b;
   ccount = 0;
   int c = 0;
   int init = 1;
   int nrc;
   initiation();
   while(scanf("%d",&n)==1&&n){
      index = 0;
      for(i=0; i<n; i++){
         scanf("%d %d",&a,&b);
         if(flag[a] == 0){
            distinct[index] = a;
            flag[a] = 1;
            index++;
         }
         if(flag[b] == 0){
            distinct[index] = b;
            flag[b] = 1;
            index++;
         }
         path[a][b] = path[b][a] = 1;
      }
      int dest,ttl;
      while(scanf("%d %d",&dest,&ttl)==2){
         if(dest==0 && ttl==0)break;
         distini();
         bfs(dest);
         nrc = 0;
         for(j=0; j<index; j++){
            if(dist[distinct[j]]>ttl){
               nrc++;
            }
         }
         printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",init,nrc,dest,ttl);
         init++;
      }
      for(j=0; j<MAX; j++){distinct[j] = 0;flag[j] = 0;}
   }
   return 0;
}


[remerson]

I've finally solved this after one wrong answer and a few hours. It is more fiddly than it first looks. I managed rank 62/2333

Some gotchas/hints:

1) Algorithm is graph BFS and with a non-recursive depth track twist. I personally did this with an adjacency list but a matrix should work equally well.

2) Like several other people, if I increased my MAX_EDGES constant from 32 to 64, this was the only difference between AC and WA. I think there's an inaccuracy in the specification here.

3) Part of the reason why I spent so much time is that I also got my algorithm generate graphviz output (coloured nodes - visited blue, unvisited red). I found this useful for diagnosing edge cases and was quite quick to add. I'll leave this as exercise to the reader to implement in their own code

Here is example graphviz output (matching 1.png below):

Code: Select all

graph "start = 1 TTL = 5" {  100 [fillcolor=blue,style=filled]; 2 [fillcolor=blue,style=filled]; 3 [fillcolor=blue,style=filled]; 4 [fillcolor=blue,style=filled]; 5 [fillcolor=blue,style=filled]; 6 [fillcolor=blue,style=filled]; 7 [fillcolor=blue,style=filled]; 8 [fillcolor=blue,style=filled]; 9 [fillcolor=blue,style=filled]; 1000 [fillcolor=blue,style=filled]; 100100 [fillcolor=blue,style=filled]; 1002 [fillcolor=red,style=filled]; 1003 [fillcolor=red,style=filled]; 1004 [fillcolor=blue,style=filled]; 1005 [fillcolor=blue,style=filled]; 1006 [fillcolor=blue,style=filled]; 1007 [fillcolor=blue,style=filled]; 1008 [fillcolor=blue,style=filled]; 1009 [fillcolor=blue,style=filled]; 20 [fillcolor=blue,style=filled]; 2100 [fillcolor=blue,style=filled]; 22 [fillcolor=blue,style=filled]; 23 [fillcolor=blue,style=filled]; 100 -- 2; 100 -- 4; 100 -- 7; 2 -- 3; 3 -- 4; 3 -- 9; 5 -- 6; 5 -- 22; 6 -- 7; 7 -- 8; 7 -- 2100; 8 -- 9; 8 -- 1006; 8 -- 100100; 9 -- 1000; 1000 -- 100100; 1000 -- 20; 1002 -- 1003; 1003 -- 1004; 1004 -- 1005; 1005 -- 1006; 1006 -- 1007; 1007 -- 1008; 1008 -- 1009; 1009 -- 20; 20 -- 2100; 2100 -- 22; 22 -- 23;
}


4) As was also pointed out above, the large sample input given on this forum is helpful a bit misleading in one specific edge case. From analysing the mismatches between this and my AC code, I think most of the differences are cases where a query is made from a non-existent node. E.g. if only nodes 10,11 defined then asking for query from node 12. I think behaviour of this type of query is undefined and the judge input (rightly) does not care about these cases.

5) In the judge sample input, I've inferred that there are no nodes with self-referential edges i.e. no edge linking node a to node a. I figured this out from comparing with Mark Greve's (excellent) UVA Toolkit site/reference solutions, which show differences in this case with my AC solution (yet both his and my solution are AC by the judge). Hence, again I think the judge input does not include such cases.

Here is another test case - this does not include any queries from undefined nodes. This has long/short cycles and is non-trivial and avoids cases (4) and (5) noted above.

INPUT

Code: Select all

28
100 2 2 3 3 4 4 100
5 6 6 7 7 8 8 9 9 1000 1000 100100 9 3 100 7
1002 1003 1003 1004 1004 1005 1005 1006 1006 1007 1007 1008 1008 1009 1009 20 20 2100 2100 22 22 23
1006 8 1000 20 22 5 7 2100 8 100100
100 5 7 3 1005 3 1004 5 2100 6 1000 99 0 0

0


OUTPUT

Code: Select all

Case 1: 2 nodes not reachable from node 100 with TTL = 5.
Case 2: 4 nodes not reachable from node 7 with TTL = 3.
Case 3: 12 nodes not reachable from node 1005 with TTL = 3.
Case 4: 6 nodes not reachable from node 1004 with TTL = 5.
Case 5: 1 nodes not reachable from node 2100 with TTL = 6.
Case 6: 0 nodes not reachable from node 1000 with TTL = 99.


Attached also are graphviz (dot) graphs for the first 3 cases in the above input (this is the maximum number of file attachments, unfortunately!).

Hope this is useful to someone.

[Scarecrow]

why am I getting RE in this problem? can't figure it out. can any1 help plz?

Code: Select all

AC


[brianfry713]

TTL can be greater than 50.

[Scarecrow]

fixing the RE, now i get WA

Code: Select all

AC


[brianfry713]

There is a case where a node is connected to itself. This causes your graph to be constructed incorrectly.

[shatil_cse]

WA !!!!!!
please help me..........

Code: Select all

#include<stdio.h>
int a,t,front,rear,level,nc,q[100000],i,j,k,l,m,n,x[10000][10000],y[10000],z[100000],state[10000];
int main()
{
   scanf("%d",&nc);
   for(l=1;nc!=0;l+=j-1)
   {
      for(i=0;i<10000;i++) x[i][0]=1;
      t=0;
      for(i=1;i<=nc;i++)
      {
         scanf("%d%d",&m,&n);                     //I have store all node I can go directly from a node(index) in two dimentional array
                                        //x[m][0] indicates how many node I can go from node m.
         if(x[m][0]==1) t++;
         x[m][x[m][0]++]=n;
         if(x[n][0]==1) t++;
         x[n][x[n][0]++]=m;
      }
      scanf("%d%d",&y[1],&z[1]);
      for(k=1;y[k]!=0||z[k]!=0;) scanf("%d%d",&y[k],&z[++k]);       
      for(j=1;j<k;j++)
      {
         for(i=0;i<10000;i++) state[i]=0;             //initializing the state
         rear=1;
         front=1;
         level=1;
         a=0;
         q[rear]=y[j];
         n=y[j];
         for(i=1;rear>=front&&a!=z[j];i++)           //traversing the node.
         {
            state[n]++;
            for(m=1;m<x[n][0];m++)
            {
               if(state[x[n][m]]==0)
               {
                  q[++rear]=x[n][m],state[x[n][m]]++;
               }
            }
            if(front==level) level=rear,a++;
            n=q[++front];
         }
         printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",l+j-1,t-rear,y[j],z[j]);
      }
      scanf("%d",&nc);
   }
   return 0;
}

[brianfry713]

Edit: removed wrong I/O.

[mahade hasan]

cut

[binitam]

Code: Select all

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main()
{
   int nc,nEdge,a,b,i,root,ttl,cases=1;
   while(1)
   {
      
      
         vector<int>edges[10000];
         cin>>nc;
         
         if(nc==0)break;
      
         for(i=0;i<nc;i++)
         {
            cin>>a>>b;
            if(a==0&&b==0)break;
            edges[a].push_back(b);
            edges[b].push_back(a);
            

         }
         while(1)
         {
            int v,visited[10000]={0},dist[10000]={0},u,count=0,flag=0;
            
            cin>>root>>ttl;
            if(root==0&&ttl==0)
            {
               flag=1;

               break;
            }
            queue<int>q;
            q.push(root);
            while(!q.empty())
            {
               v=q.front();
               visited[v]=1;
               for(i=0;i<edges[v].size();i++)
               {
                  u=edges[v][i];

                  if(!visited[u])
                  {
                     visited[u]=1;
                     dist[u]=dist[v]+1;
                     
                     if(dist[u]>ttl)count++;

                     q.push(u);
                  }


               }
               q.pop();
               
            }
            if(!flag)
            cout<<"Case "<<cases<<": "<<count<<" nodes not reachable from node "<<root<<" with TTL = "<<ttl<<"."<<'\n';
            cases++;

         }

   }
   return 0;
}

IT IS GIVING WA,,,cant understand,,plz help


[quote][/quote]

[brianfry713]

mahade hasan, running memset on your large MainArry every test case is slow. no network will contain more than 30 nodes. My AC code assumes each node can be any 32-bit signed integer.

[brianfry713]

binitam, no network will contain more than 30 nodes. My AC code assumes each node can be any 32-bit signed integer.

[@ce]

Getting WA...plz help

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>
#include<utility>

#define L long long int
#define U unsigned long long int
using namespace std;

int arr[111][111];
map <int,int>m;
vector < pair<int,int> >v;

main()
{
      int t = 1;
      while(1)
      {
            int n,p=0;
            cin>>n;
            m.clear();
            v.clear();
            if(!n)
                  break;
            for(int i = 0;i<n;i++)
            {
                  int a,b;
                  cin>>a>>b;
                  if(!(a|b))
                        break;
                  //cout<<a<<b<<endl;
                  if(m.find(a) == m.end())
                        m.insert(make_pair(a,p++));
                  if(m.find(b) == m.end())
                        m.insert(make_pair(b,p++));
                  v.push_back(make_pair(a,b));

            }

            for(int i = 0;i<m.size();i++)
            {
                  for(int j = 0;j<m.size();j++)
                        arr[i][j] = -1;
            }
            for(int i = 0;i<n;i++)
            {
                  int a = m.find(v[i].first)->second ;
                  int b = m.find(v[i].second)->second;
                  arr[a][b] = 1;
                  arr[b][a] = 1;
            }

            for(int k = 0;k<m.size();k++)
            {
                  for(int i= 0;i<m.size();i++)
                  {
                        for(int j = 0;j<n;j++)
                        {
                              if(i == j)
                                    arr[i][j] = 0;
                              else if(arr[i][j] == -1)
                              {
                                    if(arr[i][k] != -1 && arr[k][j] != -1)
                                          arr[i][j] = arr[i][k] + arr[k][j];
                              }
                              else
                              {
                                    if(arr[i][k] != -1 && arr[k][j] != -1)
                                          arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
                              }
                        }
                  }
            }

            int src,ttl;
            while(1)
            {
                  cin>>src>>ttl;
                  if(!(src|ttl))
                        break;
                  int c = 0;
                  for(int i = 0;i<m.size();i++)
                  {
                        if(src == i)
                              continue;
                        int x = m.find(src)->second;
                        if(arr[x][i] > ttl || arr[x][i] == -1)
                              c++;
                  }
                  printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",t++,c,src,ttl);
            }
      }
}


[brianfry713]

@ce, I was able to make your code AC with two small changes.
In Floyd-Warshall, all the limits should be m.size().
On line 93 you have

Code: Select all

                        if(src == i)
                              continue;


Delete that and check if(x==i) instead.