TICTACTO - Editorial

DISCLAIMER:

Don't Open This

Drinking is Injurious to Health. The characters used in this problem statement do not support the use of any type of product such as Alcohol etc. or their promotion in any manner.

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Ritika Gupta
Tester: Felipe Mota
Editorialist: Aman Dwivedi

DIFFICULTY

Easy-Medium

PREREQUISITES

Binary Search, 2D-Prefix Sum

PROBLEM:

Two drunken players Alice and Bob are playing a drunken version of Tic-Tac-Toe.

You are given N \times M empty grid.

Alice and Bob take alternate turns starting with Alice. In her turn, Alice chooses an empty cell on the board and puts a "A" on the chosen cell. In Bob’s turn, he chooses an empty cell and puts a "B" on the chosen cell.

The player who first gets any K \times K subgrid filled with his/her initial wins the game. By a K \times K subgrid, we mean the intersection of K consecutive rows and K consecutive columns. The players do not stop making turns after one of them wins and they play all N⋅M turns until the grid is filled.

You are given the sequence of moves played by each player (The cell selected by the player in his/her turn). You have to output the winner of the game or report that there is no winner.

EXPLANATION:

Subtask 1:

In this case, the value of N, M and K are small which means the number of turns i.e. N.M will be less. Hence after every turn, we can check whether there is a subgrid of size K \times K such that each cell of this grid is completely filled with exactly one character.

For checking whether there is a subgrid of size K \times K, we can iterate over all the subgrids of size K \times K and check whether there exists such subgrid.

If such subgrid exists after Alice turn, then the winner is Alice and if it exists after Bob turn then the winner is Bob. If there never exists such a subgrid the game ends in a Draw.

Time Complexity

O((N.M) * (N.M.K^2)) per test case

Solution
#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
  int n,m,k;
  cin>>n>>m>>k;

  vector <pair<int,int>> a;

  for(int i=0;i<n*m;i++)
  {
    int x,y;
    cin>>x>>y;

    x--;
    y--;

    a.push_back({x,y});
  }

  int l=0,r=n*m-1,ans=n*m;

  for(int mid=0;mid<n*m;mid++)
  {
    int arr[n][m];
    memset(arr,0,sizeof(arr));

    for(int i=0;i<=mid;i++)
    {
      if(i%2==0)
        arr[a[i].first][a[i].second]=1;
      else
        arr[a[i].first][a[i].second]=-1;
    }

    int flag=0;

    for(int i=0;i<n;i++)
    {
      for(int j=0;j<m;j++)
      {
        if(i+k-1<n && j+k-1<m)
        {
          int temp=0;
          for(int itr=0;itr<k;itr++)
          {
            for(int ptr=0;ptr<k;ptr++)
              temp+=arr[i+itr][j+ptr];
          }

          if(abs(temp)==k*k)
          {
            flag=1;
            break;
          }
        }
      }

      if(flag)
        break;
    }


    if(flag)
    {
      ans=mid;
      break;
    }
  }

  if(ans==n*m)
    cout<<"Draw"<<"\n";
  else if(ans%2)
    cout<<"Bob"<<"\n";
  else
    cout<<"Alice"<<"\n";
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

Subtask 2:

Since the value of N,M and K are large enough to give us TLE, hence we need to optimize it further.

Instead of doing linear search , we can perform binary search on turns and find out the minimum turn say x, after which there exists a subgrid of size K \times K such that each cell of this grid is completely filled with exactly one character.

For checking whether there is a subgrid of size K \times K, we can iterate over all the subgrids of size K \times K and check whether there exists such subgrid.

Since Alice moves first, it means that Alice moves in odd turns while Bob moves in even turns. Therefore if x comes out to be odd then the game is won by Alice, else Bob wins the game.

Time Complexity

O((log2(N.M)) * (N.M.K^2)) per test case

Solution
#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
  int n,m,k;
  cin>>n>>m>>k;

  vector <pair<int,int>> a;

  for(int i=0;i<n*m;i++)
  {
    int x,y;
    cin>>x>>y;

    x--;
    y--;

    a.push_back({x,y});
  }

  int l=0,r=n*m-1,ans=n*m;

  while(l<=r)
  {
    int mid=l+(r-l)/2;

    int arr[n][m];
    memset(arr,0,sizeof(arr));

    for(int i=0;i<=mid;i++)
    {
      if(i%2==0)
        arr[a[i].first][a[i].second]=1;
      else
        arr[a[i].first][a[i].second]=-1;
    }

    int flag=0;

    for(int i=0;i<n;i++)
    {
      for(int j=0;j<m;j++)
      {
        if(i+k-1<n && j+k-1<m)
        {
          int temp=0;
          for(int itr=0;itr<k;itr++)
          {
            for(int ptr=0;ptr<k;ptr++)
              temp+=arr[i+itr][j+ptr];
          }

          if(abs(temp)==k*k)
          {
            flag=1;
            break;
          }
        }
      }

      if(flag)
        break;
    }


    if(flag)
    {
      ans=mid;
      r=mid-1;
    }
    else
      l=mid+1;
  }

  if(ans==n*m)
    cout<<"Draw"<<"\n";
  else if(ans%2)
    cout<<"Bob"<<"\n";
  else
    cout<<"Alice"<<"\n";
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  // freopen("input1.txt","r",stdin);
  // freopen("output1.txt","w",stdout);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

Subtask 3:

Now the value of N,M and K are so large that the above solution will also result in TLE. We had already optimized the number of turns by using binary search on turns.

For checking whether there exists a subgrid of size K \times K which is completely filled with exactly one character, we are wasting enough time on this as we are checking each and every subgrid of size K \times K. Can we do better ?

Let’s fill the cell by 1 if the Alice performs a move and -1 if Bob performs a move. All the empty cells are filled with 0. Now instead of checking whether there exists a subgrid of size K \times K which is completely filled with exactly one character, we can check that if there exists a subgrid whose absolute sum is K^2.

We can use 2D-prefix sum array to optimally find the sum for every subgrid of size K \times K:

Let’s say pref[i][j] denotes the sum of array from (0,0) to (i,j).

Now if we are at cell (x,y) and we need to find the sum of the subgrid of size K \times K such that subgrid ends at point (x,y). It can be found as follows:

sum = pref[x][y] - pref[x-k][y] - pref[x][y-k] + pref[x-k][y-k]

We can perform binaray search on turns and use 2D-prefix sum for checking if there exists a subgrid of size K \times K whose absolute sum is K^2.

TIME COMPLEXITY:

O((log2(N.M)) * (N.M)) per test case

SOLUTIONS:

Setter
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
void solve()
{
    ll n,m,k;
    cin>>n>>m>>k;
    vector <pair<ll,ll>> v;
    v.pb(mp(0,0));
    for(int i=1;i<=n*m;i++)
    {
        ll a,b;
        cin>>a>>b;
        v.pb(mp(a,b));
    }
    ll l=1,r=n*m;
    int arr[n+1][m+1];
    int sum[n+1][m+1];
    memset(sum,0,sizeof(sum));
    ll player=0;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        int sign=1;
        memset(arr,0,sizeof(arr));
        for(int i=1;i<=mid;i++)
        {
            arr[v[i].first][v[i].second]=sign;
            sign*=-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;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(i+k-1>n || j+k-1>m)
                    continue;
                ll 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(abs(temp)==k*k)
                {
                    flag=1;
                    if(temp>0)
                        player=1;
                    else
                        player=2;
                    break;
                }
            }
        }
        if(flag)
            r=mid-1;
        else
            l=mid+1;
    }
    if(player==1)
        cout<<"Alice\n";
    else if(player==2)
        cout<<"Bob\n";
    else
        cout<<"Draw\n";
}
int main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T=1;
    cin>>T;
    int t=0;
    while(t++<T)
    {
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);

			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
long long gcd(long long a, long long b){
	while(b) a %= b, swap(a, b);
	return a;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = readIntLn(1, TEN(6));
	while(t--){
		int n = readIntSp(1, TEN(3));
		int m = readIntSp(1, TEN(3));
		int k = readIntLn(1, min(n, m));
		vector<int> x(n * m), y(n * m);
		auto cnt = create<int>(2, n + 1, m + 1);
		for(int i = 0; i < n * m; i++){
			x[i] = readIntSp(1, n);
			y[i] = readIntLn(1, m);
			assert(cnt[0][x[i]][y[i]] == 0);
			cnt[0][x[i]][y[i]] = 1;
		}
		int ans = n * m;
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= m; j++)
        cnt[0][i][j] = cnt[1][i][j] = 0;
    for(int i = 0; i < n * m; i++)
      cnt[i % 2][x[i]][y[i]] = 1;
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= m; j++){
        cnt[0][i][j] += cnt[0][i - 1][j] + cnt[0][i][j - 1] - cnt[0][i - 1][j - 1];
        cnt[1][i][j] += cnt[1][i - 1][j] + cnt[1][i][j - 1] - cnt[1][i - 1][j - 1];
      }
    }
    auto mat = create<int>(n + 1, m + 1);
    for(int i = 0; i < n * m; i++)
      mat[x[i]][y[i]] = i;
    auto mat1 = create<int>(n + 1, m + 1 - k + 1);
    for(int i = 1; i <= n; i++){
      deque<int> dq;
      for(int j = 1; j <= k; j++){
        while(!dq.empty() && dq.back() < mat[i][j]) dq.pop_back();
        dq.push_back(mat[i][j]);
      }
      mat1[i][1] = dq.front();
      for(int j = k + 1; j <= m; j++){
        if(dq.front() == mat[i][j - k]) dq.pop_front();
         while(!dq.empty() && dq.back() < mat[i][j]) dq.pop_back();
        dq.push_back(mat[i][j]);
        mat1[i][j - k + 1] = dq.front();
      }
    }
    auto mat2 = create<int>(n + 1 - k + 1, m + 1 - k + 1);
    for(int j = 1; j <= m + 1 - k; j++){
      deque<int> dq;
      for(int i = 1; i <= k; i++){
        while(!dq.empty() && dq.back() < mat1[i][j]) dq.pop_back();
        dq.push_back(mat1[i][j]);
      }
      mat2[1][j] = dq.front();
      for(int i = k + 1; i <= n; i++){
        if(dq.front() == mat1[i - k][j]) dq.pop_front();
        while(!dq.empty() && dq.back() < mat1[i][j]) dq.pop_back();
        dq.push_back(mat1[i][j]);
        mat2[i - k + 1][j] = dq.front();
      }
    }
    int has = 0;
    for(int i = k; i <= n; i++){
      for(int j = k; j <= m; j++){
        for(int r = 0; r < 2; r++){
          int sum = cnt[r][i][j] - cnt[r][i - k][j] - cnt[r][i][j - k] + cnt[r][i - k][j - k];
          if(sum == k * k){
            has = 1;
            ans = min(ans, mat2[i - k + 1][j - k + 1]);
          }
        }
      }
    }

		if(ans == n * m) cout << "Draw\n";
		else if(ans % 2 == 0) cout << "Alice\n";
		else cout << "Bob\n";
	}
	assert(getchar() == -1);
	return 0;
}

Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
  int n,m,k;
  cin>>n>>m>>k;

  vector <pair<int,int>> a;

  for(int i=0;i<n*m;i++)
  {
    int x,y;
    cin>>x>>y;

    x--;
    y--;

    a.push_back({x,y});
  }

  int l=0,r=n*m-1,ans=n*m;

  while(l<=r)
  {
    int mid=l+(r-l)/2;

    int arr[n][m];
    memset(arr,0,sizeof(arr));

    for(int i=0;i<=mid;i++)
    {
      if(i%2==0)
        arr[a[i].first][a[i].second]=1;
      else
        arr[a[i].first][a[i].second]=-1;
    }

    int sum[n][m];

    for(int i=0;i<n;i++)
    {
      for(int j=0;j<m;j++)
      {
        sum[i][j]=arr[i][j];
        if(i-1>=0)
          sum[i][j]+=sum[i-1][j];
        if(j-1>=0)
          sum[i][j]+=sum[i][j-1];
        if(i-1>=0 && j-1>=0)
          sum[i][j]-=sum[i-1][j-1];
      }
    }

    int flag=0;

    for(int i=0;i<n;i++)
    {
      for(int j=0;j<m;j++)
      {
        if(i-k+1>=0 && j-k+1>=0)
        {
          int temp=sum[i][j];
          if(i-k>=0)
            temp-=sum[i-k][j];
          if(j-k>=0)
            temp-=sum[i][j-k];
          if(i-k>=0 && j-k>=0)
            temp+=sum[i-k][j-k];

          if(abs(temp)==k*k)
            {
              flag=1;
              break;
            }
        }
      }
    }

    if(flag)
    {
      ans=mid;
      r=mid-1;
    }
    else
      l=mid+1;
  }

  if(ans==n*m)
    cout<<"Draw"<<"\n";
  else if(ans%2)
    cout<<"Bob"<<"\n";
  else
    cout<<"Alice"<<"\n";
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  // freopen("input1.txt","r",stdin);
  // freopen("output1.txt","w",stdout);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}
17 Likes

Did anyone else get TLE with RMQ after 2d prefix sum like I did?

4 Likes

Was there any prob with subtask 2 ?

I had O((n*m)^2) solution but it was givng TLE Solution: 48204358 | CodeChef

After many optimisations on loop finally subtask2 passes Solution: 48217737 | CodeChef

I had doubt in subtask, if constraints on N and M decreases then does this condition “The sum of N⋅M over all test cases does not exceed 10^6.” still holds

Wow, this was a nice problem, just the tag binary search helped me realize what I was missing for full solution.
But 500 ACs in div2 :sus:

6 Likes

I also wrote O((N*M)^2)) solution but even after optimizing it a lot it gave TLE on subtask 2.

solution was again leaked

3 Likes

Yea RIP :sadge:

1 Like

I think the problem is with this line
The sum of N⋅M over all test cases does not exceed 10^6
According this there can be 400 matrices of size 50*50

My Solution using 2D sliding window

7 Likes

I used RMQ for finding the maximum time value element in the submatrix
Here is the code → https://www.codechef.com/viewsolution/48207924
(I copied the RMQ implementation from a cf blog https://codeforces.com/blog/entry/45485 the last comment, tweaking this code to fit the constraints gives an AC)
edit : oops not the last comment now (this link precisely https://ideone.com/iTSAGV)

My optimized O((n*m)^2) solution passing 2 sub tasks.
https://www.codechef.com/viewsolution/48214872

The RMQ solution passes just 2 test cases of third subtask . Any idea why ?

My O(N*M) solution using basic dp and implementation.
https://www.codechef.com/viewsolution/48227347

1 Like

Yes , I did the same , it does not pass the third subtask while it should . Only two test cases pass .

wow nice problem
i taught this was a 2d-segment-tree problem and trying to implement it did’nt worked tho (bugs).

My approach is also of order pow((n*m),2). I created 2 matrices one for Alice and one for Bob and after every step checked the largest submatrix with all 1’s in the corresponding matrix. But didn’t get AC. Here is my solution. Can you please tell me where to optimize my code? Thanks

My solution using binary search and dp: Solution: 48229410 | CodeChef
This article can help to understand the dp part.
Maximum size square sub-matrix with all 1s - GeeksforGeeks
Nice problem.

Sorry to bug you again…
But could you please say why my code is passing just 3 tcs of subtask 3 but not the rest…
I am getting WA verdict.

I have done the prefix sum of the matrix: whenever its Alice’s move i am stuffing up a +1 at that position, else -1.
Then for every submatrix with a sum of +k or -k, i am checking the max numbered query which had filled that +/- 1. To check the last numbered query, i am using a sparse table.
For all such submatrices, i am taking the min of the max numbered query which had got it filled.
Lastly, if that min is even, Bob wins, else if its odd, Alice,else its a draw.
I am unable to find which case might possibly fail :’(

1
1 1 1
1 1

correct output should be Alice, your code outputs a Draw

1 Like

Thank you
But i had submitted without that if condition as well…
Its still showing WA