PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: lazywitt
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Sorting, binary search
PROBLEM:
There are N players, each with initially distinct skill levels represented by array S. Each of them belongs to either team A or team B.
Each pair of players will play, and whoever has higher skill wins (in case of a tie, you decide who wins).
The score of player i is \min(i, W_i), where W_i is the number of wins of player i.
You can reduce the skill levels of members of team A.
Is there a way to do that so that at least one player with maximum score is from team A?
EXPLANATION:
Let’s fix a player i from team A, and see what happens if they are to have the maximum score.
It is in fact somewhat annoying to explicitly try and make them the overall maximum, but we can restate our goal slightly to make it easier to deal with.
Note that, rather than the maximum, we only need player i to have a score that’s not less than anyone from team B - this will ensure that at least one person with the maximum score is from team A.
This will be our goal from now on.
First, observe that before any reductions are performed, the score of player i is \min(i, S_i - 1).
Let their current score be C_i.
The only possible way to increase C_i is to choose some player with a score of \gt S_i, and reduce it to \leq S_i.
If C_i \lt i this will increase it by 1, and if C_i = i the score won’t change (recall that C_i = \min(i, W_i) so it can’t go higher than i).
So, say we maybe reduce the skills of a few players and end up with some score C_i (the exact details on who and how much will be figured out as we go).
Our aim is to ensure that no player from team B has a score that’s \gt C_i.
Observe that any player at an index \leq C_i certainly cannot have a score \gt C_i.
So, we only need to look at team B players at indices \gt C_i.
Let x be the index of the team B player with maximum skill at an index \gt C_i.
Note that if C_x \leq C_i, then any team B player will have a score that’s \leq C_i (since player x will have the maximum number of wins among any member of team B among indices \gt C_i).
So, it’s enough for us to ensure that C_x \leq C_i.
Now, let’s look at S_x and S_i, and what happens when we reduce the skill of some member.
Let j be an index such that S_j \gt S_i, which we then reduce to something \leq S_i.
Then,
- If S_x \lt S_i, it’s optimal to reduce S_j exactly to S_i: this will increase C_i by 1 but not increase C_x.
- If S_i \lt S_j \lt S_x, it’s again optimal to reduce S_j to S_i: again, C_i increases by 1, while C_x doesn’t change since it already beat index j anyway.
- If S_i \lt S_x \lt S_j, reducing S_j to S_i will increase both C_i and C_x by 1.
Note that if W_x = x already then this in fact increases C_i by 1 while not increasing C_x.
From the above, we can see that as long as it’s possible to increase C_i, it’s always not worse to do so, even at the cost of perhaps increasing C_x.
Further, it’s better to bring smaller values of S_j down to S_i first before larger ones.
With this in mind, we have the following algorithm:
- Increase C_i as much as possible by repeatedly choosing the smallest available S_j \gt S_i and reducing it.
Stop when C_i = i or no more reductions are possible. - With this new C_i, find x - the maximum skill level of a team B player at an index \gt C_i.
- Compute the score C_x after the reductions done in step 1.
- If C_x \leq C_i, we’ve won.
- Otherwise, try again with a different i.
All that remains is implementation.
Subtask 1 allows for a quadratic solution, so we can do the following:
- Fix i.
- Loop over all skills levels of team A players that are \gt S_i.
If reducing their skill level to S_i will increase C_i, do so.- To make this part simple, keep a sorted list of skill levels and simply iterate through it once.
- Once the previous step is done, find the index x of the maximum skill team B player, by iterating through all indices \gt C_i.
- Finally, compute the score C_x, which is easy in linear time, and compare it against C_i.
We do \mathcal{O}(N) work for each index i, leading to an \mathcal{O}(N^2) solution overall.
To further optimize this for subtask 2, we make each part individually faster.
- The skill levels that will be reduced to S_i will form some range of the sorted list of skill levels, starting from just after where S_i itself is.
The position of S_i can be found using binary search, and the range itself can be found in constant time since its length is either all the remaining elements, or just enough of them to make C_i reach i.
This step now takes \mathcal{O}(\log N) time. - Once C_i is known, finding the index x is easily done by maintaining suffix maximums on the array S.
This step takes \mathcal{O}(1) time. - Once x is known, we need to compute C_x.
For that, we start off at x-1, and then increase by 1 for each element that was initially \gt S_x and then reduced to below it.
This count can be found in \mathcal{O}(\log N) time using binary search, since we already know the range of reduced elements from step 1.
The total work done at an index is now \mathcal{O}(\log N), so the entire problem is solved in \mathcal{O}(N\log N) time.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
string s; cin >> s;
vector <int> a(n);
for (auto &x : a) cin >> x;
// for each player of your team, compute wins
vector <pair<int, int>> ord;
vector <int> opp;
for (int i = 0; i < n; i++){
if (s[i] == 'A'){
ord.push_back({a[i], i});
} else {
opp.push_back(a[i]);
}
}
sort(ord.begin(), ord.end(), greater<pair<int, int>>());
sort(opp.begin(), opp.end());
vector<vector<int>> wins(n);
vector<pair<int, int>> use(n);
for (int j = 0; j < (int)ord.size(); j++){
int x = ord[j].first;
int i = ord[j].second;
int tot = lower_bound(opp.begin(), opp.end(), x) - opp.begin();
tot += (int)ord.size() - j - 1;
if (tot > i + 1){
tot = i + 1;
}
int need = i + 1 - tot;
need = min(need, j);
if (need == 0){
use[i] = make_pair(-1, -1);
} else {
use[i] = make_pair(ord[j - 1].first, ord[j - need].first);
}
tot += need;
wins[tot].push_back(i);
}
int mxa = 0;
vector <int> psum(n + 1, 0);
for (int i = 0; i < n; i++){
if (s[i] == 'A'){
psum[a[i]]++;
}
}
for (int i = 1; i <= n; i++){
psum[i] += psum[i - 1];
}
auto report = [&](int x){
// cout << 1 << "\n";
// return;
vector<pair<int, int>> ans;
for (int i = 0; i < n; i++){
if (a[i] > a[x] && s[i] == 'A'){
ans.push_back({i + 1, a[x]});
}
}
cout << ans.size() << "\n";
for (auto x : ans){
cout << x.first << " " << x.second << "\n";
}
};
for (int i = n - 1; i >= 0; i--){
if (s[i] == 'B'){
mxa = max(mxa, a[i]);
}
for (auto j : wins[i]){
int w = 0;
w = lower_bound(opp.begin(), opp.end(), mxa) - opp.begin();
w += psum[min(a[j], mxa)];
if (use[j].first != -1 && a[j] <= mxa){
w += psum[use[j].second] - psum[use[j].first - 1];
}
if (w <= i){
report(j);
return;
}
}
}
cout << -1 << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
// subtask 2
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
void solve(int n, string &s, vector<int> &a) {
vector<int> c(n);
for (int i = 0; i < n; i++) {
c[i] = min(i + 1, a[i] - 1);
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
if (c[i] != c[j]) {
return c[i] > c[j];
}
if (s[i] != s[j]) {
return s[i] < s[j];
}
return i < j;
});
if (s[order[0]] == 'A') {
cout << 0 << '\n';
return;
}
vector<int> d;
for (int i = 0; i < n; i++) {
if (s[i] == 'A') {
d.emplace_back(i);
}
}
sort(d.begin(), d.end(), [&](int i, int j) {
return a[i] > a[j];
});
vector<int> at(n);
for (int i = 0; i < (int) d.size(); i++) {
at[d[i]] = i;
}
set<int> st;
for (int i : order) {
if (s[i] == 'B') {
st.emplace(i);
continue;
}
if (i < *st.rbegin()) {
continue;
}
int need = *st.rbegin() + 1 - c[i];
if (need > at[i]) {
continue;
}
cout << need << '\n';
for (int j = 0; j < need; j++) {
cout << d[j] + 1 << " " << a[i] - 1 << '\n';
}
return;
}
cout << -1 << '\n';
return;
}
#define IGNORE_CR
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
#ifdef IGNORE_CR
if (c == '\r') {
continue;
}
#endif
buffer.push_back((char) c);
}
}
string readOne() {
assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
assert(!isspace(buffer[pos]));
res += buffer[pos];
pos++;
}
return res;
}
string readString(int min_len, int max_len, const string &pattern = "") {
assert(min_len <= max_len);
string res = readOne();
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
int res = stoi(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
long long res = stoll(readOne());
assert(min_val <= res);
assert(res <= max_val);
return res;
}
vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
input_checker in;
int tt = in.readInt(1, 1e5);
in.readEoln();
int sn = 0;
while (tt--) {
int n = in.readInt(2, 3e5);
in.readEoln();
sn += n;
string s = in.readString(n, n, "AB");
in.readEoln();
auto a = in.readInts(n, 1, n);
in.readEoln();
assert((int) set<int>(a.begin(), a.end()).size() == n);
solve(n, s, a);
}
cerr << sn << endl;
assert(sn <= 3e5);
in.readEof();
return 0;
}
Editorialist's code (Python)
import bisect
for _ in range(int(input())):
n = int(input())
s = 'A' + input()
a = [0] + list(map(int, input().split()))
have = []
for i in range(1, n+1):
if s[i] == 'A': have.append(a[i])
have = sorted(have)
sufmax = [0]*(n+2)
for i in reversed(range(n+1)):
sufmax[i] = sufmax[i+1]
if s[i] == 'B': sufmax[i] = max(sufmax[i], a[i])
where = [0]*(n+1)
for i in range(1, n+1):
where[a[i]] = i
ans = [[-1]]
for i in range(1, n+1):
if s[i] == 'B': continue
score = min(i, a[i] - 1)
pos = bisect.bisect_right(have, a[i])
take = min(i - score, len(have) - pos)
score += take
bmax = sufmax[score+1]
bscore = bmax - 1
if bmax > a[i]:
R = pos + take
L = bisect.bisect_right(have, bmax)
if L <= R: bscore += R - L
if bscore > score: continue
ans = [[take]]
for j in range(take):
ans.append((where[have[pos+j]], a[i]))
break
for x in ans: print(*x)