JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Matches SRM 534 div2 500
 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 #include #include #include #include #include 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 > 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 ;
 Forums Algorithm Matches SRM 534 div2 500 Previous Thread  |  Next Thread