JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
div2 500 | Reply
why the simple bfs with pruning wont work , i am applying the simple bfs , if i reach the same state again , i will not explore it.

my state contain { int x, string } x correspond to chance and string correspond to current state .. I am getting output as truncated on test 3 and 4 , please help me to sort out .
Re: div2 500 (response to post by goyal.arpit.91) | Reply
here is the code , simple bfs soln with pruning , but happen to truncated on test case 4 and 5 , help out ...

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
 
class EllysCheckers{
  public:
       string  fun( string s , int index)
      {
        string k = s;
        if ( k[index+1] == '.'   ) {
            k[index+1] = 'o';
            k[index] = '.';
        }
        k[k.size()-1] = '.';
        return k;    
      }
      string fun3( string s,int index)
      {
          string k = s;
          if ( index < s.size() -2) {
        if ( k[index+1] == 'o' && k[index+2] == 'o' && k[index+3] =='.' ) {
            k[index+3] = 'o';
            k[index] = '.';
        }
        }
        k[k.size()-1] = '.';
        return k;
      }  
  
  
    string getWinner(  string s) 
    {
         queue < pair <string,int> > q;
         
         map < string ,int > m;
        pair < string,int > p; 
        p.first = s;
        p.second = 1;
        q.push(p);
        int chance = 1;
          
        while ( !q.empty()) {
          int put;
          p = q.front();
             chance = p.second;
           
          if ( chance == 1)
            put = 2;
          else
          put = 1;
          string s = p.first;
          cout << s <<" " << chance << endl;  
          s[s.size()-1] = '.';
          for ( int i = 0; i < s.size();i++) { 
              if ( s[i] == 'o' ) {
                 string d = fun( s, i);
                 if ( d != s) {
                   
                     p.first = d;
                     p.second = put;
                     if (m[d] ==  0) {
                     q.push(p);
                       m[ d ] = 1;
                     }  
                     
                 } 
                 string r = fun3(s,i);
                 if ( r != s ) {
                     p.first = r;
                     p.second = put;
                     if ( m[r] == 0) {   
                      q.push(p);
                      m[r] = 1;
                      }  
                  }    
             }
          }  
          q.pop();
      }
      if ( chance == 2) 
          return "YES";    
        
      else
        return "NO";  
        
        
        
}        
        
        
        
  };
Re: div2 500 (response to post by goyal.arpit.91) | Reply
Well, it is easy to tell why it is wrong as it is.

You are assuming that the last string that your loop will test is ".................." that string. But it doesn't have to be, so what you are outputting is who will win whatever happened to be the last state that was processed.

An easy way to fix this is store store who wins in your map m, rather than "1".

However, even applying this fix is not enough, because while it now returns the correct output, it just takes too long to run on the large test cases.
Re: div2 500 (response to post by Cricicle) | Reply
This "1" is just for storing that the state that has visited , dont need to put that state back in the queue .if it is "0" , it mean state is not visited ;
RSS