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:
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;
}
