This is the smallest test input I could find:
1
7 5 3
2 5
1 4
3 3
3 5
4 1
3 4
5 3
5 5
5 1
2 3
3 1
7 1
7 2
2 1
3 2
6 3
5 4
1 3
4 5
2 2
7 5
1 1
6 5
7 3
6 1
1 2
2 4
6 2
5 2
6 4
4 2
4 4
4 3
7 4
1 5
Dunno 
Yes, you are right, but even if it is given that nm doesn’t exceed 10^6, then I can take T= 10^4 and N=10, M=10, which would make sum of NM over all test cases = 10^6 . Now in this case the total number of operations would be 10^10, still it is large enough to give TLE.
1 Like
There is no mention of such thing in the question, maximum number of test cases in worst case still remains 10^5. If this was the case then the test cases would have been at most 100 for subtask 1.
Same happened with me and because of that I couldn’t focus on the 3 rd subtask.
But then that should be the case with subtask 1 also right?
@anon26258039 @harsh_h
I have always thought that with subtask the sum of N.M also changes.
But this time when I suddenly saw the comment during contest, this doubt came in my mind. Also, my O((n*m)^2) solution was not passing. Can sum of N.M greater than 2500 for subtask 2? But this problem was only with subtask 2. I think this has happened first time.
Here is another approach, it is technically O(n*m) at lower constraints, but at larger integers (2 to power 1e+6) even common operations like addition and subtractions becomes costly so it gives TLE at larger constraints, so it is giving TLE at current constraints too because they are large.
So what I did was like we calculate prefix sum and absolute sum for each cell in current editorial’s method, I added another prefix “sum” (not exactly sum) based on time(when was a turn played instead of by whom it was played) attribute and some smart bit manipulation.
The main idea is to detect maximum time from a subgrid, which gives us when was a subgrid completed, and now we just have to store minimum time at which any subgrid was completed and who’s subgrid was it (Bob or Alice), which will give us the winner.
Approach:
Time(when is a turn played) is assigned in power of two, it is assigned like so:
1st turn: 1 (1)
2nd turn: 2 (10)
3rd turn: 4 (100)
Now we will use the same prefix technique to calculate prefix array and absolute value but instead of addition and subtraction operation we will use bitwise OR and bit mask set zero operation. So:
grid[i][j] += grid[i-1][j] becomes time[i][j] |= time[i-1][j]
temp -= grid[i-k][j] becomes tempTime = temp ^ (temp & time[i-k][j])
for our prefix calculations, and now tempTime will give us the time at which the subgrid was completed.
Should work at O(n*m) for lower constraints but for larger numbers, operations on integers becomes costly which leads to TLE.
Submission Link: CodeChef: Practical coding for everyone
Why this solution is giving WA and this solution giving AC? Can anyone provide me testcase for this WA solution, I think it should pass?
In WA solution : I just checked if there how many times k*k matrix sum has k*k and -k*k in alice and bob variable respectively. And in binary searched itself I had checked
- if alice+bob>1 then search left part
- else if alice==1 then answer is Alice
- else if bob==1 then answer is Bob
- else search right part.
Draw will happen when it got out of binary search without anyone wins
In AC solution: I had checked ans is odd or even or n*m after binary search like Editorial
Edit: Got it. Updated WA solution to AC solution
Consider the test input:
1
4 4 2
3 2
4 2
1 2
3 4
1 3
1 1
2 3
1 4
4 3
4 1
3 3
2 4
2 2
3 1
2 1
4 4
1 Like
Thanks Got it. 
1 Like
Can you explain this solution? It will be helpful.
Please help me to correct my solution. It’s having segmentation fault. Unable catch it
#include<bits/stdc++.h>
using namespace std;
void play(int n, int m, int k, vector<pair<int,int>> steps)
{
int low = 0, high = n*m -1, ans = n*m, mid;
bool flag;
vector<vector<int>> grid(n+1, vector<int>(m+1,0));
//populating the array
for(int i=0; i<=n*m; i++)
if(i%2 == 0)
grid[steps[i].first][steps[i].second] = 1;
else
grid[steps[i].first][steps[i].second] = -1;
//binary search
while(low<=high)
{
mid = (low+high)/2;
vector<vector<int>> sum(n+1, vector<int>(m+1,0));
//calculating prefix sums
for(int i=1; i<n; i++)
for(int j=1; j<m; j++)
sum[i][j] = grid[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
flag =0;
for(int i=k; i<n; i++)
for(int j=k; j<m; j++)
{
int cnt = sum[i][j] - sum[i-k][j] - sum[i][j-k] + sum[i-k][j-k];
if(abs(cnt) == k*k)
flag =1;
}
if(flag)
{
ans = mid;
high = mid-1;
}
else
low = mid+1;
}
if(ans == n*m)
cout<<"Draw";
else if(ans%2 )
cout<<"Alice";
else
cout<<"Bob";
}
int main()
{
int t,n,m,k,x,y;
cin>>t;
while(t--)
{
cin>>n>>m>>k;
vector<pair<int,int>> steps;
for(int i=0; i<n*m; i++)
{
cin>>x>>y;
steps.push_back({x,y});
}
cout<<"winner is ";
play(n,m,k,steps);
cout<<endl;
}
}
can anyone explain how this is working ?
pref[x][y] = number of 1s in the matrix between rows x and 0 and cols y and 0.
The equation is basically trying to find number of ones in size k*k matrix whose bottom right corner is x, y [ Assuming rows increase from 0 towards right and cols increase from 0 towards bottom ].
If you draw a picture and demarcate the rectangles each of this term correspond to, visually, you will get the intuition behind the equation. Just speaking, it removes the left part of the kk matrix, removes the top part of the kk matrix and adds top-left corner of the matrix ( since its removed twice )
Although my code may fail on large test cases, but can anyone tell me why my code is causing runtime error
Submission
Thank You 
This is the same pattern of this binary search problem.
It’s because this block:
if (zz == 1)
{
continue;
}
prevents you reading the rest of the testcase input when you think you know the answer, so it gets left in the stdin buffer, so the next testcase is read in incorrectly.
Just move it down to just after the cin>>t1>>t2; line.
1 Like