Tic Tac Toe CodeChef Solution | Easy Approach | C++ Java Python

Share:

Tic Tac Toe CodeChef Solution View on Codechef

Tic Tac Toe CodeChef Solution

Tic-tac-toe is a game played between two players on a 3×33×3 grid. In a turn, a player chooses an empty cell and places their symbol on the cell. The players take alternating turns, where the player with the first turn uses the symbol XX and the other player uses the symbol OO. The game continues until there is a row, column, or diagonal containing three of the same symbol (XX or OO), and the player with that token is declared the winner. Otherwise if every cell of the grid contains a symbol and nobody won, then the game ends and it is considered a draw.

You are given a tic-tac-toe board AA after a certain number of moves, consisting of symbols OO, XX, and underscore(__). Underscore signifies an empty cell.

Print

  • 11: if the position is reachable, and the game has drawn or one of the players won.
  • 22: if the position is reachable, and the game will continue for at least one more move.
  • 33: if the position is not reachable.

Input

  • The first line contains an integer TT, the number of test cases. Then the test cases follow.
  • Each test case contains 33 lines of input where each line contains a string describing the state of the game in ithith row.

Output

For each test case, output in a single line 11, 22 or 33 as described in the problem.

Constraints

  • 1≤T≤391≤T≤39
  • Aij∈{X,O,_}Aij∈{X,O,_}

Subtasks

Subtask #1 (100 points): Original Constraints

Sample Input

3
XOX
XXO
O_O
XXX
OOO
___
XOX
OX_
XO_

Sample Output

2
3
1

Explanation

See more posts here

Test Case 11: The board is reachable, and although no player can win from this position, still the game continues.

Test Case 22: There can’t be multiple winners in the game.

Test Case 33: The first player is clearly a winner with one of the diagonals.

Tic Tac Toe CodeChef Solution

C++

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;

#define int long long
typedef unsigned long long ull;
typedef long double lld;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // *find_by_order, order_of_key

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e18
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#ifdef Subhadip
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#define deb(x,n) cerr << #x <<" "; _print(x,n); cerr << endl;
#else
#define debug(x);
#define deb(x,n);
#endif

#define debugd(a,b) debug(a) debug(b)
#define debugt(a,b,c) debug(a) debug(b) debug(c)

void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T> void _print(T* arr, int n);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(T* arr, int n) {cerr << "[ "; for (int i = 0; i < n; i++) {_print(arr[i]); cerr << " ";} cerr << "]";}

/*---------------------------------------------------------------------------------------------------------------------------*/
int gcd(int a, int b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
int binpow(int a, int b) {int res = 1; while (b > 0) {if (b & 1) res = res * a; a = a * a; b >>= 1;} return res;}
int expo(int a, int b, int mod) {int res = 1; a %= mod; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
int mminvprime(int a, int b) {return expo(a, b - 2, b);}
void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
vector<int> sieve(int n) {int*arr = new int[n + 1](); vector<int> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
void precision(int a) {cout << setprecision(a) << fixed;}
int mod_add(int a, int b, int m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
int mod_mul(int a, int b, int m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
int mod_sub(int a, int b, int m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
int mod_div(int a, int b, int m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
/*---------------------------------------------------------------------------------------------------------------------------*/

template<class T> struct PrefixSums {
    vector<vector<T>> sum;
    void init(const vector<vector<T>>& v) {
        int R = v.size(), C = v[0].size();
        sum.assign(R + 1, vector<T>(C + 1));
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                sum[i + 1][j + 1] = v[i][j] + sum[i + 1][j] + sum[i][j + 1] - sum[i][j];
            }
        }
    }
    T get(int X1, int Y1, int X2, int Y2) {
        X2 ++, Y2 ++;
        return sum[X2][Y2] - sum[X1][Y2]
               - sum[X2][Y1] + sum[X1][Y1];
    }
};

void solve() {
    int n,m,k;
    cin>>n>>m>>k;
    vector<pair<int,int>> v;
    for(int i=0;i<n*m;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        v.pb({a,b});
    }
    int l=1,h=n*m,m1,ans=-1;
    while(l<=h){
        m1=(l+h)/2;
        int cur=-1;
        vector<vector<int>> vec(n,vector<int>(m));
        for(int i=0;i<m1;i++){
            int a=v[i].ff;
            int b=v[i].ss;
            if(i%2){
                vec[a][b]=1;
            }
            else{
                vec[a][b]=-1;
            }
        }
        PrefixSums<int> pre;
        pre.init(vec);
        for(int i=0;i<=n-k;i++){
            for(int j=0;j<=m-k;j++){
                int x=pre.get(i,j,i+k-1,j+k-1);
                if(x==-(k*k)){
                    cur=0;
                }
                else if(x==k*k){
                    cur=1;
                }
            }
        }
        if(cur==-1){
            l=m1+1;
        }
        else{
            if(cur==0){
                ans=0;
            }
            else{
                ans=1;
            }
            h=m1-1;
        }
    }
    if(ans==0){
        cout<<"Alice\n";
    }
    else if(ans==1){
        cout<<"Bob\n";
    }
    else{
        cout<<"Draw\n";
    }
}

signed main() {
#ifdef Subhadip
    freopen("Error.txt", "w", stderr);
#endif
    fastio();
    int t = 1;
    cin>>t;
    auto start1 = high_resolution_clock::now();
    while (t--)
        solve();
    auto stop1 = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop1 - start1);
#ifdef Subhadip
    cerr << "Time: " << duration . count() / 1000 << endl;
#endif
}

Java

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.security.KeyStore.Entry;
import java.text.DecimalFormat;
import java.io.*;
 
class Main
{
	 
    public static void main (String[] args) throws java.lang.Exception
    {
	 FastScanner in=new FastScanner();
	 StringBuilder sb = new StringBuilder();
	 Scanner sc = new Scanner(System.in);
	 PrintWriter out=new PrintWriter(System.out);
	 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	 int M=1000000007;
	 int t = in.nextInt();
	 while(t-->0)
	 {
		 int n=in.nextInt();
		    int m=in.nextInt();
		    int k=in.nextInt();
		    int total=n*m;
		    int [][] store = new int[total][2];
		    for(int i=0;i<total;i++){
		        int x=in.nextInt();
		        int y=in.nextInt();
		        store[i][0]=x;
		        store[i][1]=y;
		    }
		    int ans=total;
		    int l=0,r=total-1;
		    while(l<=r){
		        int mid = l+(r-l)/2;
		        int [][] arr = new int[n+1][m+1];
		        int [][] sum = new int[n+1][m+1];
		        for(int i=0;i<=mid;i++){
		            if(i%2==0)
		            arr[store[i][0]][store[i][1]]=1;
		            else
		            arr[store[i][0]][store[i][1]]=-1;
		        }
		        for(int i=1;i<=n;i++){
		            for(int j=1;j<=m;j++){
		                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];
		            }
		        }
		        int flag=0;
		        for(int i=1;i<=n-k+1;i++){
		        	for(int j=1;j<=m-k+1;j++){
		                int temp=sum[i+k-1][j+k-1]-sum[i-1][j+k-1]-sum[i+k-1][j-1]+sum[i-1][j-1];
		                
		                if(Math.abs(temp)==k*k){
		                  flag=1;
		                  break;
		                }
		            }
		            if(flag==1)
		            break;
		        }
		        if(flag==1){
		            ans=mid;
		            r=mid-1;
		        }else{
		            l=mid+1;
		        }
		    }
		    if(ans==total)
		    out.println("Draw");
		    else if(ans%2!=0)
		    out.println("Bob");
		    else 
		    out.println("Alice");
		        }
 	out.close();
     } 
   
   	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}

Python

import sys, math, random, heapq
from collections import deque
from math import gcd
def bs(arr,le,ri):
    l=0;arr.sort();r=len(arr)-1;ans=10000000
    while l<=r:
        m=(l+r)//2
        if arr[m]>=le and arr[m]<=ri:ans=arr[m];r=m-1
        elif arr[m]<le:l=m+1
        else:r=m-1
    return ans
for __ in range(int(input())):
    n,m,k=map(int,input().split());l=[[-1 for j in range(m)] for i in range(n)];ans=[[0 for j in range(m)] for i in range(n)];largest=[[0 for i in range(m)] for j in range(n) ]
    for i in range(n*m):x,y=map(int,input().split());l[x-1][y-1]=(i%2,i)
    for i in range(n):
        ans[i][0]=l[i][0][0]
        for j in range(1,m):ans[i][j]=l[i][j][0]+ans[i][j-1]
    for j in range(m):
        for i in range(1,n):ans[i][j] += ans[i-1][j]
    for i in range(n):
        st=deque()
        for j in range(k):
            while len(st)>0 and st[-1][0]<l[i][j][1]:st.pop()
            st.append((l[i][j][1],j))
        largest[i][k-1]=st[0][0]
        for j in range(k,m):
            if st[0][1]==j-k:st.popleft()
            while len(st)>0 and st[-1][0]<l[i][j][1]:st.pop()
            st.append((l[i][j][1],j));largest[i][j]=st[0][0]
    for i in range(k-1,m):
        st=deque()
        for j in range(k):
            while len(st)>0 and st[-1][0]<largest[j][i]:st.pop()
            st.append((largest[j][i],j))
        largest[k-1][i]=st[0][0]
        for j in range(k,n):
            if st[0][1]==j-k:st.popleft()
            while len(st)>0 and st[-1][0]<largest[j][i]:st.pop()
            st.append((largest[j][i],j));largest[j][i]=st[0][0]
    alice=[];bob=[]
    for i in range(k-1,n):
        for j in range(k-1,m):
            x=ans[i][j]
            if i-k>=0:x-=ans[i-k][j]
            if j-k>=0:x-=ans[i][j-k]
            if i-k>=0 and j-k>=0:x+=ans[i-k][j-k]
            if x==0:alice.append(largest[i][j])
            if x==k*k:bob.append(largest[i][j])
    if len(bob)==0 and len(alice)==0:print("Draw")
    elif len(bob)==0:print("Alice")
    elif len(alice)==0:print("Bob")
    else:print("Bob") if min(alice) > min(bob) else print("Alice")

Tic Tac Toe CodeChef Solution Tutorial

See more posts here

Leave a Comment

Your email address will not be published. Required fields are marked *

x