PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY : HARD
PREREQUISITES:
Matrix, Divide and Conquer, Recursion
PROBLEM:
Kibu is having a tough time coaching his football team. He wants his players to spread out maximum, such that the vacant space is reduced.
The ground is in the shape of an n × m matrix. Some players have entered the field and settled down, while others are getting ready to enter.
He watches the players entering one by one. After the entry of each player, Kibu will calculate the size of the largest vacant square possible (largest square without a player inside).
You should help Kibu to find the size(length of a side) of the largest vacant square after each entry
#QUICK EXPLANATION:
The model solution uses the idea of Divide and Conquer. Let’s make a recursive routine that takes a rectangular sub-table, bounded with r1, r2, c1, c2 (r1 ≤ r2, c1 ≤ c2), and a list of events that happen inside this sub-table. The purpose of the routine is to consider how maximal empty squares in this sub-table change in time, and to update the answers for some of the events.
#EXPLANATION:
Let’s denote the player arrivals as events.
Consider the following solution (it will help to understand the author’s idea): let’s consider all empty squares in the table. There a too many of them, but imagine that we can afford to loop through all of them. If we fix a square, we can find out when it is no longer empty: find the first event that belongs to this square. Let this event has the number x, and the size of the square is k. Now we can update the answers for all events with numbers less than x with a value of k.
The model solution uses the idea of Divide and Conquer. Let’s make a recursive routine that takes a rectangular sub-table, bounded with r1, r2, c1, c2 (r1 ≤ r2, c1 ≤ c2), and a list of events that happen inside this sub-table. The purpose of the routine is to consider how maximal empty squares in this sub-table change in time, and to update the answers for some of the events.
Let’s assume that c2 - c1 ≤ r2 - r1 (the opposite case is symmetric). Take the middle row r = (r1 + r2) / 2. Virtually split all the squares inside the sub-table into those which lie above r, those which lie below r, and those which intersect r. For the first two parts, make two recursive calls, splitting the list of events as well. Now focus on the squares that intersect the row r.
Using the initial table, for each cell (r, c) we can precompute the distance to the nearest taken cell in all four directions (or the distance to the border, if there is no such cell): up(r, c), down(r, c), left(r, c) , right(r, c). Using these values, build two histograms for the row r: the first is an array of values up(r, c), where c1 ≤ c ≤ c2; the second is an array of values down(r, c), where c1 ≤ c ≤ c2. I say histograms here because these arrays actually can be viewed as heights of empty columns, pointing from the row r upwards and downwards. Let’s call the first histogram “upper”, the second one — “lower”. Now consider all events inside the sub-table in the order they happen. Each event changes a single value in a histogram. If after some event x the maximum empty square found in the histograms has size k, and the next event has number y, we can update answers for all events with numbers x, x + 1, …, y - 1 with the value of k.
It remains to learn to find a maximum square in two histograms. It can be done by a two-pointer approach. Set both pointers to the beginning. Move the second pointer until there is such a square in histograms: there is a square with side length k if (minimum on the interval in the upper histogram) + (minimum on the interval in the upper histogram) — 1 >= k. When the second pointer can not be moved anymore, update the answer and move the first pointer. To find the minimum in O(1), the author’s solution creates a queue with the minimum in O(1) support. That is, the maximum square can be found in linear time.
Let’s try to estimate the running time. Each call of the routine (omitting inner calls) costs O(len·q), where len is the shortest side of the sub-table, and q is the number of events in it. If we draw a recursion tree, we will see that each second call len decreases twice. The total cost of all operations in a single level of a recursion tree is O(NK), where K is the total number of events. As long as we have O(logN), the overall complexity is O(NKlogN).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
const ll maxn = 2017;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);
#define pb push_back
#define endl ‘\n’
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(ares)%md;}a=(aa)%md;b>>=1;}return(res);}
int n , m , k,l ;
int x[maxn] , y[maxn];
string s[maxn];
int ans = 0;
int up[maxn][maxn] , down[maxn][maxn];
deque < int > u , d;
bool chk(int x , int k){
u.clear();
d.clear();
if(k > m)return(0);
for(int i = 1 ; i < k ; i ++){
while(u.size() and up[x][i] <= up[x][u.back()])
u.pop_back();
u.pb(i);
while(d.size() and down[x][i] <= down[x][d.back()])
d.pop_back();
d.pb(i);
}
for(int i = k ; i <= m ; i ++){
while(u.size() and up[x][i] <= up[x][u.back()])
u.pop_back();
u.pb(i);
while(d.size() and down[x][i] <= down[x][d.back()])
d.pop_back();
d.pb(i);
if(up[x][u.front()] + down[x][d.front()] > k)return(1);
if(d.front() == i - k + 1)d.pop_front();
if(u.front() == i - k + 1)u.pop_front();
}
return(0);
}
int solve(int i){
int l = 0 , r = n+1;
while(r - l > 1){
int mid = (l + r)/2;
if(chk(i , mid))
l = mid;
else
r = mid;
}
return(l);
}
void solve(){
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
if(s[i][j]!=‘X’)
up[i][j] = up[i - 1][j] + 1;
for(int i = n ; i ; i --)
for(int j = 1 ; j <= m ; j ++)
if(s[i][j] != ‘X’)
down[i][j] = down[i+1][j] + 1;
for(int i = 1 ; i <= n ; i ++)
ans = max(ans , solve(i));
}
vector < int > Ans;
int main(){
cin >> n >> m >>l>> k;
for(int i = 1 ; i <= n ; i ++){
s[i]=‘1’;
for(int j=1;j<=m;j++)
s[i]+=‘.’;
}
for(int i = 1 ; i <= l ; i ++)
{cin >> x[i] >> y[i] ; s[x[i]][y[i]] = ‘X’;}
for(int i = 1 ; i <= k ; i ++)
cin >> x[i] >> y[i] , s[x[i]][y[i]] = 'X';
solve();
for(int i = k ; i ; i --){
s[x[i]][y[i]] = '.';
for(int j = 1 ; j <= n ; j ++)
if(s[j][y[i]]!='X')
up[j][y[i]] = up[j - 1][y[i]] + 1;
for(int j = n ; j ; j --)
if(s[j][y[i]] != 'X')
down[j][y[i]] = down[j+1][y[i]] + 1;
Ans.pb(ans);
ans = max(ans , solve(x[i]));
}
reverse(Ans.begin() , Ans.end());
for(int x : Ans)cout << x <<"\n";
return(0);
}
Tester's Solution
Same Person
Editorialist's Solution
Same Person