PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kryptonix171
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
(Optional) Binary search
PROBLEM:
You’re given an N\times M grid, with A_{i, j} denoting who between two players shot at each cell.
If cell (x, y) is the bullseye, the score of shooting at cell (x_1, y_1) is \max(|x-x_1|, |y-y_1|).
The score of a player is the sum of all their scores.
For each of the N\cdot M cells, find the difference between the scores of both players, if that cell was the bullseye.
In this version, N = 1.
EXPLANATION:
Since N = 1, the grid is really just a line of length M.
This also means every cell has the same y-coordinate (namely 1), so if the bullseye is at (x, 1), shooting at (x_1, 1) gives a score of just |x-x_1|; after all |y-y_1| = |1-1| = 0 so it can’t be larger than |x-x_1|.
Since the y-coordinate can be ignored, cells will be referred to with just their x-coordinates henceforth.
Let’s compute the score of each player for each cell individually - the differences can be computed at the end.
Suppose the cells player 1 shoots at are x_1, x_2, \ldots, x_k (in ascending order).
Then, if the bullseye is at cell x, player 1's score will be exactly
To compute this quickly, we split it into two parts: x_i \leq x and x_i \gt x.
This allows us to remove the absolute value from the summation.
Suppose there are m_1 values among these k that are \leq x, and m_2 that are \gt x.
The above summation then becomes
which reduces to
So, once m_1 is known, the required value can be computed in constant time: after all, both remaining summations are just prefix and suffix sums of the x_i values.
Finding m_1 can be done using binary search.
We now have all the scores of player 1 in \mathcal{O}(N\log N) time.
Do the same for player 2, and output the differences.
The above algorithm can be optimized to \mathcal{O}(N) time as well - either use two pointers instead of binary search, or observe how quantities change when moving from x to x+1 (for the latter, m_1 changes by at most 1, and the prefix and suffix sums change by at most one element too, so changes are easy to make).
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void cal(int a[], int m, int res[]){
res[0] = 0;
int cnt = 0;
for(int i = 0; i < m; i++){
if(a[i]){
res[0] += i;
cnt++;
}
}
if(a[0]){
cnt--;
}
int temp = a[0];
for(int i = 1; i < m; i++){
res[i] = res[i - 1] - cnt + temp;
if(a[i]){
cnt--;
temp++;
}
}
}
int32_t main() {
int t;
cin>>t;
while(t--){
int n, m;
cin>>n>>m;
int a[m] = {};
int b[m] = {};
for(int i = 0; i < m; i++){
int temp;
cin>>temp;
if(temp == 1 || temp == 3){
a[i] = 1;
}
if(temp == 2 || temp == 3){
b[i] = 1;
}
}
int ar[m], br[m];
cal(a, m, ar);
cal(b, m, br);
for(int i = 0; i < m; i++){
cout<<abs(ar[i] - br[i])<<" ";
}
cout<<"\n";
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
score = [0]*m
asum = bsum = act = bct = 0
for i in range(m):
score[i] += i*act - asum + bsum - i*bct
if a[i] & 1:
asum += i
act += 1
if a[i] & 2:
bsum += i
bct += 1
asum = bsum = act = bct = 0
for i in reversed(range(m)):
score[i] += asum - i*act - bsum + i*bct
if a[i] & 1:
asum += i
act += 1
if a[i] & 2:
bsum += i
bct += 1
for i in range(m): score[i] = abs(score[i])
print(*score)