TCTCTOE - Editorial

Your code is failing in this test case. Answer should be 3 your code will give 2.

1
OXX
XOX
__O

Thanks Man, I got my Mistake.

Hey I wonder why online compiler is giving wrong answer even though I have checked most of the edge cases

#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?++i:--i)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define test cout<<"This is TEST********\n";
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define sz(c) (int)c.size()
#define ans(x) cout<<x<<'\n';
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;


void solve() {
	int i, j,k, row[3] = {0}, col[3] = {0}, diag[2] = {0},  win = -1, nx=0, ny=0;
	string n;
	fo(i, 3) {
		cin >> n;
		fo(j, 3)
		{	k=int(n[j]);
			row[i] += k; 
			col[j] += k; 
			if (i == j) diag[0] += k; 
			if (i == 2 - j) diag[1] += k;
			if(k==88)nx++;
			else if(k==79)ny++;
}
	}
	if ((nx - ny) > 1 || ny>nx ) {
		ans(3); return;
	}
	
	fo(i, 3) {

		if (row[i] == 264 || col[i]==264 || diag[i%2]==264) {

			if(win==-1) {if(nx<=ny){ans(3);return;}
			win=0;}
			else if(win!=0){ans(3);return;}
		}

		if (row[i] == 237 || col[i]==237 || diag[i%2]==237) {

			if(win==-1) { if(ny<nx){ans(3);return;}win=0;}
			else if(win!=1){ans(3);return;}
		}

		}
	if (nx+ny==9 || win!=-1) {
		ans(1);return;
	}
	
	ans(2);


}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int t;
	cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

Solution: 46298975 | CodeChef @darshancool25. I code the same logic (as per ur video editorial) but still there is an issue and I am unable to find that.

Because you checked “most” instead of “all” :stuck_out_tongue:

1
___
OOO
XXX
1 Like
1
__X
_XO
XOO
if(res>1) cout<<"3\n";

Is the mistake.

1
XXX
OXO
XOO

Should be 1, not 3

Damn in my checking function I copied the win checker for X to O but forgot to change the win variable value to 1.
Thanks man

1 Like

@dharshancool25
can you please explain me that why should we take the condition
!((x==o)||(x==o+1)) in that why should we use ! this .
if two person wins the game ,we need to check that the count of x and o should be equal or greater than one if any one of its is true can’t we print 3 .why should we go for ! this sir.
thank you in advance

tried 30 + cases .pls tell me that one damn case where its going wrong

#include
using namespace std;

int main()
{
long long int T;
cin>>T;
for( long long int k=0;k<T;k++)
{ int X=0,O=0;
char r1[3],r2[3],r3[3];
cin>>r1[0]>>r1[1]>>r1[2];
cin>>r2[0]>>r2[1]>>r2[2];
cin>>r3[0]>>r3[1]>>r3[2];

    for(int i=0;i<3;i++)//counting X and O
    {
        if(r1[i]=='X')
        X++;
        else if(r1[i]=='O')
        O++;

        if(r2[i]=='X')
        X++;
        else if(r2[i]=='O')
        O++;

        if(r3[i]=='X')
        X++;
        else if(r3[i]=='O')
        O++;

    }
    bool o2=false;
    bool d=false;
    bool h=false;
    bool v=false;
    bool won=false;
    bool win2=false;  /**more than one winner case is
                        not reachable except for 
                        the cases where x wins through
                        two ways simultaneously for eg.XXX
                                        OXO
                                        OOX
                        i make win2 true whenever this happens**/
                        
    
    int winner=0;
    //deciding if anyone won
    for(int i=0;i<3;i++)
    {
        if(r1[i]==r2[i] && r2[i]==r3[i] && (r3[i]=='X' || r3[i]=='O') )
        {   if(r3[i]=='O')
            {o2=true;} 
            won=true;
            winner++;
            if(r1[i]=='X')
            {v=true;}
        }
    }
    
    
    if(r1[0]==r1[1] && r1[1]==r1[2] && (r1[2]=='X' || r1[2]=='O') )
    {   if(r1[2]=='O')
        {o2=true;} 
        won=true;
        winner++;
        if(r1[0]=='X')
        {h=true;}
    }
         
    if(r2[0]==r2[1] && r2[1]==r2[2] && (r2[2]=='X' || r2[2]=='O') )
    {   if(r2[2]=='O')
        {o2=true;} 
        won=true;
        winner++;
        if(r2[0]=='X')
        {h=true;}
    }
    if(r3[0]==r3[1] && r3[1]==r3[2] && (r3[2]=='X' || r3[2]=='O') )
    {   if(r3[2]=='O')
        {o2=true;} 
        won=true;
        winner++;
        if(r3[0]=='X')
        {h=true;}
    }
    
    if( ( ( r1[0]==r2[1] && r2[1]==r3[2] ) || ( r1[2]==r2[1] && r2[1]==r3[0] ) ) && ( r2[1]=='X' || r2[1]=='O') )
    {   if(r2[1]=='O')
        {o2=true;} 
        won=true;
        winner++;
        if(r2[1]=='X')
        {
            d=true;
        }
        if(( r1[0]==r2[1] && r2[1]==r3[2] ) && ( r1[2]==r2[1] && r2[1]==r3[0] ) && r2[1]=='X')
        {win2=true;}
    }
    
    if(h==true && v==true || d==true && h==true || v==true && d==true)/**this checks if two wins
                                                                        have happened simultaneously**/ 
     
    { win2=true;}
    
    
    if(X-O==1 || X-O==0)//as we start with X ,O can never be more than X
    {
        if(X+O!=9 && won==false)
        {cout<<2<<endl;}
        else if ((winner>1 && win2==false ) || ( o2==true && X-O==1) )
        {cout<<3<<endl;}
        else
        {cout<<1<<endl;}
    }
    else
    {
        cout<<3<<endl;
    }
    
    
}
return 0;

}

1
___
___
__O

@ojas_17

https://www.codechef.com/viewsolution/46624166
Can someone please provide test case(s) where this wont work. Have been trying for a long time

#include <bits/stdc++.h>
#define int long long int
using namespace std;

bool hasWonX = false, hasWonO = false, rowWinX = false, rowWinO = false, colWinX = false, colWinO = false, diagWinX = false, diagWinO = false;

bool oneKindOfWinX()
{
    if ((rowWinX && !colWinX && !diagWinX) || (!rowWinX && colWinX && !diagWinX) || (!rowWinX && !colWinX && diagWinX))
        return true;
    else
        return false;
}

bool oneKindOfWinO()
{
    if ((rowWinO && !colWinO && !diagWinO) || (!rowWinO && colWinO && !diagWinO) || (!rowWinO && !colWinO && diagWinO))
    {
        // cout << (rowWinO && !colWinO && !diagWinO) << " " << (!rowWinO && colWinO && !diagWinO) << " " << (!rowWinO && !colWinO && diagWinO) << "\n";
        return true;
    }
    else
    {
        return false;
    }
}

int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;
    while (t--)
    {
        hasWonX = false, hasWonO = false, rowWinX = false, rowWinO = false, colWinX = false, colWinO = false, diagWinX = false, diagWinO = false;
        string r1, r2, r3;
        cin >> r1 >> r2 >> r3;

        int spaceCount = 0, oCount = 0, xCount = 0;

        for (int i = 0; i < 3; i++)
        {
            if (r1[i] == '_')
                spaceCount++;
            if (r2[i] == '_')
                spaceCount++;
            if (r3[i] == '_')
                spaceCount++;
            if (r1[i] == 'X')
                xCount++;
            if (r2[i] == 'X')
                xCount++;
            if (r3[i] == 'X')
                xCount++;
            if (r1[i] == 'O')
                oCount++;
            if (r2[i] == 'O')
                oCount++;
            if (r3[i] == 'O')
                oCount++;
        }

        // Case 1 - game is reachable and decided
        // Case 2 - game is reachable and not decided
        // Case 3 - game is unreachable

        //Row wins
        if ((r1[0] == r1[1] && r1[1] == r1[2] && r1[1] == 'X') || (r2[0] == r2[1] && r2[1] == r2[2] && r2[1] == 'X') || (r3[0] == r3[1] && r3[1] == r3[2] && r3[1] == 'X'))
        {
            hasWonX = true;
            rowWinX = true;
        }
        if ((r1[0] == r1[1] && r1[1] == r1[2] && r1[1] == 'O') || (r2[0] == r2[1] && r2[1] == r2[2] && r2[1] == 'O') || (r3[0] == r3[1] && r3[1] == r3[2] && r3[1] == 'O'))
        {
            hasWonO = true;
            rowWinO = true;
        }

        //Col wins
        if ((r1[0] == r2[0] && r2[0] == r3[0] && r2[0] == 'X') || (r1[1] == r2[1] && r2[1] == r3[1] && r2[1] == 'X') || ((r1[2] == r2[2] && r2[2] == r3[2] && r2[2] == 'X')))
        {
            hasWonX = true;
            colWinX = true;
        }
        if ((r1[0] == r2[0] && r2[0] == r3[0] && r2[0] == 'O') || (r1[1] == r2[1] && r2[1] == r3[1] && r2[1] == 'O') || ((r1[2] == r2[2] && r2[2] == r3[2] && r2[2] == 'O')))
        {
            hasWonO = true;
            colWinO = true;
        }

        //Diag wins
        if ((r1[0] == r2[1] && r2[1] == r3[2] && r2[1] == 'X') || (r3[0] == r2[1] && r2[1] == r1[2] && r2[1] == 'X'))
        {
            hasWonX = true;
            diagWinX = true;
        }
        if ((r1[0] == r2[1] && r2[1] == r3[2] && r2[1] == 'O') || (r3[0] == r2[1] && r2[1] == r1[2] && r2[1] == 'O'))
        {
            hasWonO = true;
            diagWinO = true;
        }

        //Case break - if x greater or o greater
        if(xCount - oCount > 1 || oCount - xCount > 1 || (oCount > xCount && hasWonX) || (xCount > oCount && hasWonO) )
        {
            cout << "3\n";
            continue;
        }

        //Case 1a) - X wins
        if (hasWonX && oneKindOfWinX() && !hasWonO)
        {
            cout << "1\n";
            continue;
        }
        // Case 1b) - O wins
        else if (hasWonO && oneKindOfWinO() && !hasWonX)
        {
            cout << "1\n";
            continue;
        }
        // Case 1c) - Draw
        else if (spaceCount == 0 && !hasWonO && !hasWonO)
        {
            cout << "1\n";
            continue;
        }

        //Case 2) - Continue
        else if (!hasWonO && !hasWonX && spaceCount > 0)
        {
            cout << "2\n";
            continue;
        }

        // Case 3) - Unreachable
        else if ((hasWonO && hasWonX) || !oneKindOfWinO() || oneKindOfWinX())
        {
            cout << "3\n";
            continue;
        }
        else
            cout << "why? \n";
        // If it reaches here I am stupid

        // cout << "hasWonX " << hasWonX << " "
        //      << "hasWonO " << hasWonO << " "
        //      << "rowWinX " << rowWinX << " "
        //      << "rowWinO " << rowWinO << " "
        //      << "colWinX " << colWinX << " "
        //      << "colWinO " << colWinO << " "
        //      << "diagWinX " << diagWinX << " "
        //      << "diagWinO " << diagWinO << "\n";
    }
    return 0;
}```

This gave a 2, which I understand to be correct? Am I missing something?
Thanks anyway! :smiley:

Yes :slight_smile: Who makes the first move?

Oh, I’m stupid, thanks a lot!

1 Like

how that position is not reachable if u don’t mind explaining pls?
1
OXX
XOX
__O

X can’t have made a greater number of moves if O wins

2 Likes

ahhhh gotcha!! thanks man… that was such a silly mistake from my side :grimacing:

1 Like

The answers you have posted to these test cases are wrong. You are generating the wrong output for test cases where both “X” and “O” have won the game, which is and unreachable position and should give 3.

The correct outputs (from my solution) are:

1
2
1
3
3
2
2
3
3
1
3
3
1
2
2
2
3
3
3
1
1
3
1
3
3