1998A - Find K Distinct Points with Fixed Center
Problem Credits: sum
Analysis: cry
We can construct a solution by fixing all $$$x_i$$$ as $$$x_c$$$ or all $$$y_i$$$ as $$$y_c$$$. For example, if we fix all $$$y_i$$$ as $$$y_c$$$, then we can output pairs $$$(x_c-1, y_c), (x_c+1, y_c), (x_c-2, y_c), (x_c+2, y_c), ... , (x_c- \lfloor \frac{k}{2} \rfloor, y_c), (x_c + \lfloor \frac{k}{2} \rfloor, y_c)$$$. If the $$$k$$$ is odd, we need one more pair, so just output $$$(x_c, y_c)$$$.
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--){
int x, y, k; cin >> x >> y >> k;
for(int i = 0; i < k - k % 2; i++){
cout << x - (i & 1 ? 1 : -1) * (i / 2 + 1) << " " << y << "\n";
}
if(k & 1){
cout << x << " " << y << "\n";
}
}
}
1998B - Minimize Equal Sum Subarrays
Problem Credits: satyam343
Analysis: cry
We can always construct a solution such that the number of pairs $$$(i, j)$$$ is $$$1$$$ where the only pair is $$$(1, n)$$$. There exists several constructions, such as rotating $$$p$$$ once or increment all $$$p_i$$$ (and $$$p_i = n$$$ turns into $$$p_i = 1$$$).
Consider the former construction, where $$$q = [p_2, p_3, ..., p_n, p_1]$$$. For an arbitrarily interval $$$[i, j]$$$, $$$p[i..j]$$$ and $$$q[i..j]$$$ will have exactly $$$1$$$ element that's different, disregarding ordering. Since we have a permutation and all elements are distinct, the sum in the range will never be the same. The only exception is the entire array, of course.
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while(t--){
int n; cin >> n;
vector<int> p(n);
for(int& i: p) cin >> i;
rotate(p.begin(), p.begin() + 1, p.end());
for(int i: p) cout << i << " ";
cout << "\n";
}
}
1998C - Perform Operations to Maximize Score
Problem Credits: cry, satyam343
Analysis: sum, satyam343, Dominater069
First, solve for $$$k = 0$$$. Find some nice characterization about $$$med(c_i)$$$ and thus the maximum score.
Divide into $$$2$$$ cases where we either increment the max element or the median.
Apply binary search
Let's forget about the operations of adding $$$1$$$ to $$$a_i$$$ and figure out how to find an array's score. Assume the array $$$a$$$ is sorted in increasing order as the order doesnt change the problem.
First observe how $$$med(c_i)$$$ changes with respect to $$$i$$$. $$$med(c_i)$$$ is always either $$$a_{\lfloor \frac{n}{2} \rfloor}$$$ or $$$a_{\lfloor \frac{n + 2}{2} \rfloor}$$$. You can prove this formally by considering different positions of $$$i$$$ with respect to the initial median position. Specifically, for all $$$i \le \lfloor \frac{n}{2} \rfloor$$$, $$$med(c_i) = a_{\lfloor \frac{n + 2}{2} \rfloor}$$$, and for other $$$i$$$, $$$med(c_i) = a_{\lfloor \frac{n}{2} \rfloor}$$$.
Claim 1 : The score of the final array (after sorting in increasing order) is $$$a_n + med(c_n)$$$
There are $$$2$$$ cases we need to consider.
1) $$$med(c_i) = a_{\lfloor \frac{n}{2} \rfloor}$$$, in which case optimum value of $$$i$$$ is $$$n$$$ as we want to maximise $$$a_i$$$. Thus score in this case is $$$a_n + a_{\lfloor \frac{n}{2} \rfloor}$$$.
2) $$$med(c_i)= a_{\lfloor \frac{n + 2}{2} \rfloor}$$$, in which case optimum value of $$$i$$$ is $$$\lfloor \frac{n}{2} \rfloor$$$ as this is the largest value of $$$i$$$ which will change median. This obtains a score of $$$a_{\lfloor \frac{n}{2} \rfloor} + a_{\lfloor \frac{n + 2}{2} \rfloor}$$$
The score in Case $$$1$$$ is clearly larger than Case $$$2$$$, hence it is optimal.
Hence, our score can be nicely characterized by "max + median of the others".
Claim 2 : Either we will use all $$$k$$$ operations on the element which eventually becomes max element in our array, or we will use all operations trying to improve $$$med(c_n)$$$ and keep max element constant.
Suppose we did $$$x$$$ ($$$0 < x < k$$$) operations on the element which eventually became maximum.
Then, we could have done the remaining $$$(k - x)$$$ operations on this element too, as this is already the max element and doing operations on it guaranteedly improves our score each time by $$$1$$$. Doing operations on any other element can only improve our score by atmost $$$1$$$
Thus, we are in $$$2$$$ cases now, either increase max, or increase median of the rest. We will solve the problem considering both cases separately.
Case $$$1$$$ : We do operations on the element which becomes max eventually.
Lets fix $$$i$$$ to be the index that will become max. Then $$$b_i = 1$$$ must hold. We want to find $$$med(c_i)$$$, i.e. the median of the other $$$(n - 1)$$$ elements. This can be done with the observation mentioned above that $$$med(c_i)$$$ is always either $$$a_{\lfloor \frac{n}{2} \rfloor}$$$ or $$$a_{\lfloor \frac{n + 2}{2} \rfloor}$$$.
Another possible way to solve this case is observe that we should only do operations on the largest index $$$i$$$ such that $$$b_i = 1$$$. While intuitive, the proof is left as an exercise to the reader.
Case 2 : We do operations to increase the median of the others.
$$$a_n$$$ is fixed as the max element in this case, and we want to find the largest possible median by using the $$$k$$$ operations on the other $$$(n - 1)$$$ elements.
Let's binary search! Suppose we want to check if we can get $$$med(c_n) \ge x$$$ or not.
Some elements are already $$$\ge x$$$, and we will not modify them.
Some of the other elements can be incremented to become $$$\ge x$$$ too. Obviously, we should choose the largest indices $$$i$$$ such that $$$a_i < x$$$ and $$$b_i = 1$$$, and greedily increment as many as possible.
Let $$$z$$$ be the maximum number of elements which become $$$\ge x$$$ at the end. The check is true iff $$$z \ge \lfloor \frac{n + 1}{2} \rfloor$$$.
Thus, the problem is solved in $$$O(N \cdot log (MAX))$$$. The code is nicely written and commented, you may want to check it out.
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while (t--){
int n, k; cin >> n >> k;
vector <pair<int, int>> a(n);
for (auto &x : a) cin >> x.first;
for (auto &x : a) cin >> x.second;
sort(a.begin(), a.end());
long long ans = 0;
// case 1 : increment max
for (int i = 0; i < n; i++) if (a[i].second == 1){
// find med(c_i)
int mc;
if (i < n / 2) mc = a[n / 2].first;
else mc = a[(n - 2) / 2].first;
ans = max(ans, 0LL + a[i].first + k + mc);
}
// case 2 : increment median
int lo = 0, hi = 2e9;
while (lo != hi){
int mid = (1LL + lo + hi) / 2;
int z = 0;
vector <int> smaller_list;
for (int i = 0; i < n - 1; i++){
if (a[i].first >= mid){
z++;
} else if (a[i].second == 1){
smaller_list.push_back(mid - a[i].first); // list of numbers smaller than x but b[i] = 1
}
}
reverse(smaller_list.begin(), smaller_list.end()); // list will be sorted in ascending, but we want sorted in descending, as greedily changing largest elements
int kk = k;
for (auto x : smaller_list) if (kk >= x){
kk -= x;
z++;
}
if (z >= (n + 1) / 2) lo = mid;
else hi = mid - 1;
}
ans = max(ans, 0LL + a[n - 1].first + lo);
cout << ans << "\n";
}
return 0;
}
1998D - Determine Winning Islands in Race
Problem Credits: cry
Analysis: cry
First, let's consider if there was no alternative bridges. Then obviously, if Bessie starts at island $$$i$$$ and keeps moving forwards, it is impossible for Elsie to move past island $$$i$$$ since the bridge would have already collapsed. From this, we can deduce that Bessie cannot let Elsie use these alternative bridges to overtake the island Bessie is on, or else Elsie will always reach the end first.
Therefore, Bessie will keep moving right in hopes of breaking enough bridges so that it is impossible to for Elsie to overtake Bessie. This can be simplified to: consider we are at island $$$i$$$ and $$$t$$$ units of time has passed, for all alternative bridges that Elsie can take with an endpoint $$$v > i + t$$$, we have to reach $$$v$$$ before her.
Let $$$d_i$$$ denote the minimum amount of time Elsie takes to reach island $$$i$$$. For the first case, consider all bridges with endpoints $$$v > S$$$, then $$$d_v \geq v - S - 1$$$ must hold true since we want to reach $$$v$$$ before Elsie does when we keep going right. We can rearrange the equation as $$$S \geq v - d_v - 1$$$. To make sure this holds true for all bridges, we just have to make sure this is true for the maximum value of $$$v - d_v$$$.
All $$$d_i$$$ can be calculated using a linear sweep to the right, and we can track all $$$v - d_v$$$ with a sweep to the left. Note that we cannot take a bridge if it starts past $$$S$$$, so we need to track the maximum with a multiset and erasing as we sweep.
Time Complexity is $$$\mathcal{O}(n \log n)$$$. There exists other solutions using prefix sums in $$$\mathcal{O}(n)$$$ and segment tree in $$$\mathcal{O}(n \log n)$$$
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define trav(a,x) for(auto& a: x)
void solve() {
int n, m; cin >> n >> m;
vector<vector<int>> g(n), rg(n);
FOR(i,0,m){
int u, v; cin >> u >> v;
--u; --v;
g[u].pb(v);
rg[v].pb(u);
}
FOR(i,0,n-1) g[i].pb(i+1);
vector<int> dist(n, -1);
queue<int> q;
dist[0] = 0;
q.push(0);
while(!q.empty()){
int f = q.front();
q.pop();
trav(i, g[f]){
if(dist[i] == -1){
dist[i] = dist[f] + 1;
q.push(i);
}
}
}
multiset<int> max_good_rights;
vector<vector<int>> to_erase(n);
string ans = string(n - 1, '0');
ROF(i,n-1,0){
trav(j, rg[i]){
int max_right = i - dist[j];
max_good_rights.insert(max_right);
to_erase[j].pb(max_right);
}
trav(j, to_erase[i]){
max_good_rights.erase(max_good_rights.find(j));
}
if(i < n - 1){
int max_good_right = max_good_rights.empty() ? -1 : *prev(max_good_rights.end());
if(i >= max_good_right - 1){
ans[i] = '1';
}
}
}
cout << ans << endl;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int t = 1;
cin >> t;
for(int test = 1; test <= t; test++){
solve();
}
}
1998E1 - Eliminating Balls With Merging (Easy Version)
Problem Credits: cry, sum, satyam343
Analysis: sum
Consider the ball with the maximum number. Let this ball be $$$m$$$. That ball can clearly be the last ball remaining. And if we are able to merge some ball $$$i$$$ with ball $$$m$$$ (whilst removing $$$m$$$), then ball $$$i$$$ can also be the last ball remaining.
We can do a divide and conquer solution. For some range $$$[l,r]$$$, let $$$m$$$ be the ball with the maximum value. Clearly, $$$m$$$ can be the last ball remaining if we only consider the range $$$[l, r]$$$.
Let's first recurse on $$$[l,m)$$$ and $$$(m,r]$$$. Let $$$s_l=a_l+a_{l+1}+\cdots+a_{m-1}$$$ (i.e. the sum of the left half). If $$$s_l < a_m$$$ then no ball in the left half can be the last one remaining. Otherwise, the results (i.e. whether each ball can be the last one standing) for range $$$[l,r]$$$ for balls in $$$[l,m)$$$ is the results we computer when recursing onto $$$[l,m)$$$. The same reasoning holds for the right half.
We can use a sparse table to find the maximum ball in any range. This leads to a $$$\mathcal{O}(n\log n)$$$ solution.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
const int MAX = 2e5 + 5;
int n, x, ans; ll A[MAX], bad[MAX], P[MAX]; pll rmq[MAX][18];
void dnq(int l, int r){
if (l >= r)
return;
int lg = 31 - __builtin_clz(r - l + 1);
int mid = max(rmq[l][lg], rmq[r - (1 << lg) + 1][lg]).second;
dnq(l, mid - 1);
dnq(mid + 1, r);
ll sum1 = P[mid - 1] - P[l - 1];
ll sum2 = P[r] - P[mid];
// Left half bad
if (A[mid] > sum1){
bad[l] += 1;
bad[mid] += -1;
}
// Right half bad
if (A[mid] > sum2){
bad[mid + 1] += 1;
bad[r + 1] += -1;
}
}
void solve(){
cin >> n >> x;
for (int i = 1; i <= n; i++){
cin >> A[i];
P[i] = P[i - 1] + A[i];
bad[i] = 0;
rmq[i][0] = {A[i], i};
}
for (int j = 1; j <= 17; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
dnq(1, n);
ans = 0;
for (int i = 1; i <= n; i++){
bad[i] += bad[i - 1];
ans += !bad[i];
}
cout << ans << "\n";
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--)
solve();
}
For some ball $$$i$$$, let $$$l_i$$$ and $$$r_i$$$ be the first balls on the left and right that have a value greater than $$$a_i$$$.
Proccess the balls from largest $$$a_i$$$ to smallest $$$a_i$$$. For each ball $$$i$$$, let $$$\text{ans}_i$$$ denote whether it can be the last ball remaining. We know that if we merge ball $$$i$$$ with some ball $$$j$$$ (while discarding $$$j$$$) and $$$\text{ans}_j=1$$$, then $$$\text{ans}_i=1$$$. Furthermore, we know that balls $$$l_i$$$ and $$$r_i$$$ can freely merge with balls $$$j$$$ where $$$j$$$ is in interval $$$[l_i+1 \ldots r_i-1]$$$ while discarding $$$j$$$ (i.e. $$$\text{ans}_{l_i}$$$ and $$$\text{ans}_{r_i}$$$ would have taken this into account).
This motivates the following idea. Let $$$s$$$ be the sum of values in $$$[l_i+1 \ldots r_i-1]$$$. If $$$s \geq a_{l_i}$$$ then we do $$$\text{ans}_i := \text{ans}_i |\text{ans}_{l_i}$$$. Similarly, if $$$s \geq a_{r_i}$$$, then we do $$$\text{ans}_i := \text{ans}_i |\text{ans}_{r_i}$$$. This solution runs in $$$\mathcal{O}(n \log n)$$$ due to sorting.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
int n, x;
cin >> n >> x;
vector<int> A(n + 5);
vector<ll> P(n + 5);
vector<int> ans(n + 5, 0);
vector<int> ord(n);
set<int> S{0, n + 1};
for (int i = 1; i <= n; i++){
cin >> A[i];
P[i] = P[i - 1] + A[i];
ord.push_back(i);
}
sort(ord.begin(), ord.end(), [&](int a, int b){
return A[a] > A[b];
});
for (int i : ord){
int l = *(--S.lower_bound(i));
int r = *S.lower_bound(i);
ll sum = P[r - 1] - P[l];
if (i == ord[0])
ans[i] = true;
if (sum >= A[l])
ans[i] |= ans[l];
if (sum >= A[r])
ans[i] |= ans[r];
S.insert(i);
}
cout << accumulate(ans.begin(), ans.end(), 0) << "\n";
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--)
solve();
}
1998E2 - Eliminating Balls With Merging (Hard Version)
Problem Credits: cry, sum, satyam343
Analysis: sum
Consider the naive greedy solution. We continuously merge with the balls on the left and right without removing our ball until we can't anymore or our ball is the final remaining one.
Suppose at some point in this greedy approach, we can not merge with the balls on our left and right anymore without discarding our ball. Let our ball be $$$i$$$. Then we have the following cases.
- There is a ball $$$l$$$ on the left of $$$i$$$ and ball $$$r$$$ on the right of $$$i$$$. Then: $$$\min(a_l,a_r) > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$.
- There is a ball $$$l$$$ on the left of $$$i$$$ but no ball on the right of $$$i$$$. Then: $$$a_l > a_{l+1}+a_{l+2}+\cdots+a_{\text{last}}$$$.
- There exists no ball on the left of $$$i$$$ but a ball $$$r$$$ on the right of $$$i$$$. Then: $$$a_r > a_1+a_2+\cdots+a_{r-1}$$$.
For some ball $$$i$$$, if there exists some $$$l$$$ and/or some $$$r$$$ such that one of the above is true, then there exists no way for our ball to be the last one remaining. Otherwise, the ball can be the last one remaining.
Let $$$p$$$ be the prefix sum array of $$$a$$$ (i.e. $$$p_i=a_1+a_2+\cdots+a_i$$$).
For some ball $$$i$$$, we want to do the following.
- Find the smallest $$$r_1$$$ such that there exists some $$$l$$$ such that ($$$l, r_1$$$) is a pair (i.e. $$$\min(a_l,a_{r_1}) > a_{l+1}+a_{l+2}+\cdots+a_{r_1-1}$$$). Finding this is more difficult than the other cases and will be focused on later.
- Find the smallest $$$r_2$$$ such that $$$a_{r_2} > a_1+a_2+\cdots+a_{{r_r}-1}$$$. We can rewrite it as as $$$a_{r_2} > p_{r_2-1}$$$ and it can easily be found.
- Find the smallest $$$r_l$$$ such that there exists no $$$l$$$ on the left of $$$i$$$ such that $$$a_l > a_{l+1}+a_{l+2}+\cdots+a_{r_l}$$$. We can rewrite the inequality as finding the first $$$r_l$$$ such that $$$p_{r_l} \geq a_l + p_l$$$ which can be done with binary search.
Suppose at some $$$i$$$, we know its $$$r_l$$$, $$$r_1$$$, and $$$r_{2}$$$. Then we know ball $$$i$$$ can be the last one remaining for prefixes spanning from $$$r_l$$$ to $$$\min(r_1-1, r_{2}-1)$$$ so we can do a range add with prefix sums.
The only thing we have not resolved yet is how to find the smallest $$$r_1$$$ for some $$$i$$$ such that $$$\min(a_l,a_{r_1}) > a_{l+1}+a_{l+2}+\cdots+a_{r_1-1}$$$.
Let's iterate over $$$r$$$. For each $$$r$$$ we want to find the leftmost $$$l$$$ such that $$$\min(a_l,a_{r}) > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$
A key observation is that we can write the following inequality as $$$a_l > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$ and $$$a_r > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$ (both have to be true).
Using prefix sums, the equations can be rewritten as $$$a_l + p_l > p_{r-1}$$$ and $$$p_l > p_{r-1} - a_r$$$.
So some $$$(l,r)$$$ works if the equation above is satisfied. Consider the second part $$$p_l > p_{r-1} - a_r$$$. We can binary search to find the range of available $$$l$$$ that satisfy this. Specifically, let $$$l_b$$$ be the lower bound of the range. Then, any $$$l$$$ in $$$[l_b...i)$$$ satisfies this.
Now, let's try to satisfy $$$a_l + p_l > p_{r-1}$$$. Unfortunately, $$$a_l + p_l$$$ is not monotonic so the method above will not work. Instead, we can create a sparse table over all $$$a_i + p_i$$$. Then we can binary search to find the first $$$l_{opt}$$$ such that the maximum in range $$$[l_b,l_{opt}]$$$ (which can be found with the sparse table) is greater than $$$p_{r-1}$$$.
Circling back, $$$r_1$$$ is the minimum $$$r$$$ of an interval covering $$$i$$$ which can be found with things such as sweepline. In all, this solution runs in $$$\mathcal{O}(n \log n)$$$ time.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
int n, x;
cin >> n >> x;
vector<ll> A(n + 5, 0);
vector<ll> P(n + 5, 0);
vector<vector<ll>> rmq(n + 5, vector<ll>(18, 0));
for (int i = 1; i <= n; i++){
cin >> A[i];
P[i] = P[i - 1] + A[i];
rmq[i][0] = A[i] + P[i];
}
for (int j = 1; j <= 17; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
vector<vector<int>> add(n + 5), rem(n + 5);
auto ins = [&](int l, int r, int v){
l = max(l, 1);
if (l > r)
return;
add[l].push_back(v);
rem[r + 1].push_back(v);
};
for (int r = 1; r <= n; r++){
// r is a roadblock
if (A[r] > P[r - 1])
ins(1, r - 1, r);
// Find leftmost l possible
int lowerB = upper_bound(P.begin() + 1, P.begin() + n + 1, P[r - 1] - A[r]) - P.begin();
int lo = lowerB, hi = r - 1;
while (lo < hi){
int mid = (lo + hi) / 2;
// Query lowerB...mid
int lg = 31 - __builtin_clz(mid - lowerB + 1);
ll val = max(rmq[lowerB][lg], rmq[mid - (1 << lg) + 1][lg]);
val > P[r - 1] ? hi = mid : lo = mid + 1;
}
ins(lo + 1, r - 1, r);
}
multiset<int> badR{n + 1};
vector<int> ans(n + 5, 0);
ll worst = 0;
for (int i = 1; i <= n; i++){
for (int v : add[i])
badR.insert(v);
for (int v : rem[i])
badR.erase(badR.find(v));
int l = lower_bound(P.begin() + i, P.begin() + n + 1, worst) - P.begin();
int r = *badR.begin();
// Active for interval [l...r)
if (l <= r){
ans[l]++;
ans[r]--;
}
worst = max(worst, A[i] + P[i]);
}
for (int i = x; i <= n; i++){
ans[i] += ans[i - 1];
cout << ans[i] << " \n"[i == n];
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int tc;
cin >> tc;
while (tc--)
solve();
}
first, I feel like B is a problem you can really get stuck on if you don't guess it
True that,I tried proving multiple approaches while guessing and wasted time.
My logic was that if you shifted each element right 1, each pair of i and j (except when i=1 and j=n), will have all but one element be the same from the original permutation, thus making the sums different(keep in mind that all elements are distinct due to the array being a permutation so the shift will not shift in an identical element).
Yeah, I wasted 20mins on it.
Yeah,I wasted around 30 mins on that question with any conclusion then in frustation moved to C . I don't understand how so many people were able to solve it .
I guessed it. Tried the simples solution which felt logically right and the rest was luck
i did. I cant believe its so easy
Bonus: E2 can be solved in $$$O(n)$$$ time. 275655689
Nice, I have a bit of a different $$$\mathcal{O}(n)$$$ via Cartesian tree: 275679381
Just compare a point's value with the sum of its subtree right?
why is there a ycombinator template in your code lol
Can someone estimate an upper bound on no of states in these solutions for E1 and E2? Or hack otherwise? 275608667 275619707
For E1, Did you do expand in directions till you hit larger than initial?
Its very naturally log(max) states per index.
Because your base value atleast doubles once you beat someone who was larger than your base
(Confirmed that the E1 submission passes after removing the dp map: 275657487.)
Specifically, I think the subarray sum at least doubles after every three calls to
chk.Also E2, because his logic surrounding the questionable complexity part is not changing in any significant way
275664378 E2 without map.
Thanks for making me break the record of my worst rank ever:)
You not alone bro :P, let's get back our rating points together in next contest ;)
Me too. I got stuck on C. Now I'm nearly specialist.
The two codes of problem E1 are same,cry please fix it,thx.
B can be solved using one cyclic shift
how did you thought about it?
If you do a cyclic shift and then pick any contiguous subarray, it will always differ in exactly one element. Hence the sums will never be the same (unless you take the whole array).
I tried to minimize segments of length one
For D I have a better solution which works in O(n + m).
275623093
what does the vector mpjt contain?
I have seen the race as the cow Bessie having a head start of s units, so to beat Bessie we must be able to get ahead of Bessie using the edges which originate upto point s — 1. mjpt vector is used to store the maximum "Jump" we can get when we land at any x. "Jump" for each move Elsie takes is equal to (lenght of jump — 1) (as we take 1 unit time to jump which Bessie also gets so in short we gained a distance of Lenght — 1), mj variable stores the maximum possible "Jump" (or distance gain we can get using edges originating upto s — 1). If we can get a net jump of more than s, we Elsie wins else Bessie wins.
So basically you solved it by calculating wins of Elsie and editorial tends to solve it by making bassie win. Difference in perspective I guess?
This seems a little bit easier to come up with than the standard answer but I think one thing is that this mj variable should normally use dynamic programming, so it's probably a little bit slower, right?
C you can do O(nlogn) time instead of O(nlogMAX) binary search time by using two pointers, faster than binary search. First, only two strategies can be optimal; increase the maximum of the array a as much as possible, or increase the median of the array a as much as possible. The editorial goes into the reasoning behind this in more detail.
First strategy is easy to compute by just finding the biggest array element where the corresponding b_i = 1, then increasing it by k.
Second strategy, first sort the array, then use two pointers where right pointer is pointing to the right of the median, and the left pointer is pointing to the first i to the left of (or equal to) the median where b_i = 1.
Clearly the right pointer forms a "wall" that we cannot overcome until we increment the median to its value, and if this "wall" is not incrementable (b_i = 0), you can only get past it by incrementing values to the left of the median, so you can recruit extra help from the left pointer to shift the wall over to the left. At each iteration we keep track of the "width"/frequency of the median (because we will have to increment a lot of elements at once to increase the median sometimes), and we increment the median to the value of the "wall" (right pointer), then move the wall to the right one element, and keep on iterating until we either reach the end of the array (just increment the current median as much as possible) or we run out of operations.
I too went down this route during the contest, but wasn't able to come up with a correct implementation. Sometimes I just wish I was born smarter. xD
b..but you are Ayanokoji
that is why he is intentionally holding back
I see that a lot of you have got FST on A by fixing the first $$$k-1$$$ points in some way and balancing with the last one, my sincere condolences. However I also have to tell you that you could immediately upgrade that to an (almost) unhackable solution.
Instead of choosing the first $$$k-1$$$ deterministically, choose them randomly in the range of $$$[-R,R]\times [-R,R]$$$. $$$R$$$ should not matter as long as there is no overflow, though the collision probability should be $$$O(k/R)$$$ if my proofs are correct. Now choose the last point as the trivial one that makes the center same as the given one.
Really all this for div2 A??
This blog was created 7weeks ago?????
Attached code for C doesn't pass samples?
Editorial code for Problem C doesn't work for this valid test case
$$$1$$$
$$$5$$$ $$$3$$$
$$$3$$$ $$$4$$$ $$$7$$$ $$$5$$$ $$$3$$$
$$$0$$$ $$$1$$$ $$$0$$$ $$$1$$$ $$$0$$$
The code outputs $$$10$$$ but $$$11$$$ can be achieved by applying given operation thrice on index $$$4$$$ ($$$1$$$-based indexing).
Yeah... No. Editorial code kinda also outputs $$$11$$$.
they changed the code.
You can also do E2 using the same DnC approach in the solution 1 to E1
my sub
it boils down to finding dpl and dpr, where dpl is the point starting which a ball can consume all other blobs and it only works till dpr. To calculate dpl, you need to find the leftmost index upto which the ball must consume other ones such that you can consume the left blockade(so dpl must be atleast this index). Also, if you can consume the right blockade, you can set dpl to dpl of the right blockade
In C: " Observe that it is optimal to only consider removing the largest element with bi=0", did you mean guess?
Please give proofs...
I also was not able to observe that and solved a harder problem, used prefix sum and ordered multiset. 275621322
Denote $$$a_m$$$ as the max element, $$$a_o$$$ to be the median of array after removing $$$a_m$$$ and $$$a_i$$$ to be the alternative element we want to consider to remove instead of $$$a_m$$$ for a better solution. If one of them is changeable then the case becomes choose the max changeable element and put all increments there. So we only consider all of them to be unchangeable below:
if $$$a_i>a_o$$$, then swapping the choice won't impact the median but we pay $$$a_m-a_i$$$ for the change
if $$$a_i=a_o$$$, then swapping the choice would increase the median by at most $$$a_m-a_i$$$, we pay $$$a_m-a_i$$$ for the swap as well, so the result won't be better
if $$$a_i<a_o$$$, the only hope for getting a better result is after swapping, $$$a_m$$$ replaced $$$a_o$$$ to be the median, and it must increase more than $$$a_m-a_i$$$ we pay. The increase would be $$$a_m-a_o$$$ and we know $$$a_i<a_o$$$, so $$$a_m-a_o<a_m-a_i$$$, so the result cannot be better as well
can u explain this more ?
Thus, we are in 2 cases now, either increase max, or increase median of the rest. We will solve the problem considering both cases separately. As mentioned in this editorial We need to handle the cases separately . Whyyy Separately I mean Why there is no optimality if we are trying to maximize and last element together
totally changed the editorial, i hope its fine now :)
Thus, we are in 2 cases now, either increase max, or increase median of the rest. We will solve the problem considering both cases separately.
As mentioned in this editorial We need to handle the cases separately .
Whyyy Separately I mean Why there is no optimality if we are trying to maximize and last element together
this means that either max remains constant or median of the others remains constant.....which are 2 separate cases
when max remains constant, we want to maximise median of others and vice versa
but why , why we did not need to do these operation together let say for some x , x < k. I will focus to maximise the median and for remaining k-x I will try to maximise the maximum
Ahhh!! Got it got it. I am a moron
Thanks @Dominator069
C is much harder than D to me, spent twice as much time solving it
any proof for this ?
Hello, for E1, I have another solution,
we know the brute force solution is for every index i, check if it can remain till the end, we can do this by simple greedy, this becomes O(n^2)
Now, there are 2 observations :-
1) suppose, for an index i, we can use it to remove i-1, and i-1 can potentially stay till the end, then i can also stay till the end, the same is true for i+1
2) suppose, we scan the array in both directions for a certain index i, and we found out that it cannot potentially stay till the end, then, all the indexes that i can remove, will also not stay till the end
ik that the explanation is not that good, but idk how to explain this more precisely, so forgive me for that
my code : https://codeforces.me/contest/1998/submission/275623982
nice contest. it'd be great if authors add hints before solutions in their editorials
For A , why can't we have coordinates are (-1, -1), ... (-k/2, -k/2), (1,1), .... (k/2, k/2) and (0, 0)(if k is even) and (xc*k, yc*k) ? It was failing on pretest2.
For k=2 and xc=yc=0
You will output (0, 0) and (0, 0)
"(In fact we can observe that we only have to consider the rightmost one, though this observation is not necessary.)"
It isn't clear that you mean the rightmost in the sorted array.
In original array the position doesn't matter, so I think it's quite obvious. Anyway editorials should be as clear as possible
Guys, what's wrong with my code? Can someone pls help:
Getting this on test 2: wrong answer 208th numbers differ — expected: '17', found: '16'
In C, how is the answer for this testcase 29
1
6 2
3 11 12 14 14 15
1 0 0 1 0 0
UPD: Sorry, saw the wrong testcase
Why this solution of mine for A is giving WA on test 4? 275601626
Thanks for making me break the record of my worst rank ever:)
C is too difficult! Why you put such a difficult problem in that position!
example of problem B why can't the second(i,j)take (4,5)?Doesn't that go against the meaning of the solution?
I have a confusing way to solve E1. I could even not calculate its time complexity.
275618236
Could anyone help me to prove its correctness or hack it?
for problem C in proof2 , how one can prove that doing remaining k-x ops on any other element or more of those element improvement in score will be atmost 1? what about if that ops is done on the median part then the score will increase by 1 each time if the case was that bi=1 in the median part ? satyam343
How to even analyze in B ?I mean I kept thinking about half an hour without reaching any conclusion.
use next_permutation to observe a pattern the good thing is that next_permutation works in an order and not in a random way so it will always give you the same pattern for all the cases you will try
For C there is also more naive
O(N * log(MAX_ELEM + K) * log(N))solution.https://codeforces.me/contest/1998/submission/275689471
We can brute force selected element. Firstly, we sort pairs like (a[i], b[i]) in array c.
Suppose c[i] is rejected element, then we can binary search for maximum median we can get in remaining array. In this binary search we need to find position where we insert this value:
For example, if we test 7 for median in remaining array
1 2 (4) 5 8
we will need to put it between 5 and 8 — test_pos also is found with binary search
if this element to the left of median (4) we won, if not, we need to have at least test_pos — median_pos elements to change, in this example we need to change at least two numbers behind 7 to make it median. So, we need to fastly calculate how much elements behind number are changeable
So, let's calculate prefsum for array c, where we only prefsumming numbers where b is 1 and saving positions of that 1s, Then we can binary search in that array of positions to find where our test_pos lies. Our index is our count of changeable numbers, if it less then we can't make it median. If we can, we need to understand how many increments we need to make them all like median.
So, basically, deficite is
sum(value - a[i])for changeable i. Which equiualent tovalue * i_count - sum(a[i]).sum a[i]could be found with prefix sums.if deficite is less than k we won, else not
has anyone done problem C without the use of binary search ?
satyam343, Dominater069, sum In problem C editorial it is mentioned that when applying all k operations on a_n after sorting and taking median of the remaining n — 1 elements the ans will be maximum as compared to other cases when taking a_i where 1 <= i <= n — 1.
Then do we need this code for checking all scenarios? Instead why can't we just find value for a_n + med(remaining n — 1 elements)?
Let me know if I am misunderstanding something.
the sorted order of A may change after the K operations
Notice the curious wording :
-20 -32 -21 -33 100000000 100000000 -100000000 -100000000 99999999 99999999 -999999999 -99999999 99999998 99999998 -99999998 -99999998
for problem A why the center is not -5,-8, 8 for this test case i think this should work
I was having confusion that why I am choosing max element when bi = 0, since we have two option for max_element like a_lmax or a_rmax for array { a_lmax, a_med1, a_med2, a_rmax} --> choosing a_lmax will give greater median than a_rmax
If anybody can complete the proof that would be nice of you. Thanks.
My construction for A
We want $$$x_1 + x_2 + \cdots + x_k = k \cdot x_c$$$ and $$$y_1 + y_2 + \cdots + y_k = k \cdot y_c$$$ also all $$$(x_i, y_i)$$$ to be distinct respecting the limit $$$(-10^9 \le (x_i, y_i) \le 10^9)$$$
One way to construct $$$\sum x = k \cdot x_c$$$ is to set the $$$x$$$ coordinates of the first $$$(k-1)$$$ points to be $$$0$$$ and the last $$$x$$$ coordinate to be exactly $$$k \cdot x_c$$$
Let's check if $$$k \cdot x_c$$$ is in given limit or not. Given $$$-100 \le (x_c, y_c) \le 100$$$ and $$$1 \le k \le 10^3$$$ therefore $$$-10^5 \le (k \cdot x_c, k \cdot y_c) \le 10^5$$$. Now we want $$$\sum y = k \cdot y_c$$$.
Let's use $$$y$$$-coordinates as $$$1, 2, \cdots, k-1$$$ and somehow construct the $$$y$$$-coordinate of the last point. We now have the sum $$$S = \frac{k(k - 1)}{2}$$$ and we need $$$\sum y - S$$$ much more. After proving this extra term is within the limits and all are distinct we're done.
Let's prove $$$\sum y - S$$$ is within the limits. Consider the case $$$\sum y \gt 0$$$ and $$$S \lt 0$$$, maximum value would be $$$\approx$$$ $$$10^5 + 10^6$$$ and least value would be also around that magnitude, which is in the limit
Now are all points distinct? After this construction we have the points
$$$(0, 1), (0, 2), \cdots, (0, k-1), (k \cdot x_c, Y)$$$ where $$$Y = \sum y - S$$$. The first $$$(k-1)$$$ points will be on $$$y$$$-axis at different locations because each has different $$$y$$$-coordinates and will be above $$$x$$$-axis since $$$k \gt 0$$$ if the last point doesn't collide with other other points we're fine. We only have to consider the case when $$$k \cdot x_c = 0$$$ which means when $$$x_c = 0$$$, $$$Y = \sum y - S$$$ should not be in {$$${1, 2, \cdots, k-1}$$$}.
Let's say We fix the $$$y$$$-coordinate of last point at $$$\sum y$$$ which can be atmost $$$100 \cdot k$$$, and if we drag the point down by $$$S$$$ units if it's still above $$$(k-1)$$$ or below point $$$1$$$ we're fine. We can ignore the case when $$$y_c \lt 0$$$ since it will drag the point more down to $$$x$$$-axis and we don't have any points there.
$$$\textit{proof}$$$
If any there is any mistakes please let me correct. Thanks!
Check my solution down
Here're my insights for Problems A,B
Let the points you want to output is
the center is
which means that
.
So we have : -
k \mod 2=1 \rightarrow (x-\frac{k}{2},y-\frac{k}{2}),....,(x+\frac{k}{2},y+\frac{k}{2}) \\ \end{cases}$$$
.
Let's think of $$$j-i=1$$$ first that means that all every $$$p_i \neq q_i$$$ , $$$j-i=2$$$ that means that $$$p_i+p_{i+1} \neq q_i+q_{i+1}$$$ you can keep doing the same until $$$j-i=n-2$$$ , but when $$$j-i=n-1$$$ i.e. you selected the whole permutation you cannot do it anymore thus you can achieve the goal for any $$$(i,j)$$$ except $$$i=1,j=n$$$ , we can ensure the following in order to make it optimal
This is possible for all $$$(i,j)$$$ except $$$i=1,j=n$$$ , if we rotated/shifted the array one unit to right.
Total Complexity is $$$\mathcal{O}(n)$$$.
I enjoyed the contest , and I've to say cry and sum , I'm a big fan , keep writing contests !
ok
I misread the problem C, instead of calculating $$$max(a_i + median(c_i))$$$, I thought that you need to calculate $$$sum(a_i + median(c_i))$$$ (so you need to only calculate $$$sum(c_i)$$$), any ideas how to solve it?
"For the first case, consider all bridges with endpoints v > S, then dv ≥ v − S − 1 must hold true since we want to reach v before Elsie does when we keep going right."
Can someone please explain what v and S are here? Correct me if I am wrong, but according to the explanation, v and S are both indices of the islands, but dv is the time to reach the v-th island.
I had the goofiest, most overcomplicated solution to C.
275828049
Problem D can also be solved in $$$O(n+m)$$$ using a simple approach. We create a DP vector that stores the minimum distance traveled by Elsie. Then, we iterate over the islands, keeping track of the maximum difference between an island Elsie can reach and the minimum distance to reach it. At the end of each iteration, we compare this value with Bessie's starting point to compute the answer.
Edit: as pointed out by L0giCAL's reply, we must compute the DP vector incrementally, not before the main loop; otherwise, the path used by Elsie might include paths that come after Bessie's starting point.
275863908
I have a similar approach but I am getting WA on TC 26 .. any idea where I am making mistake.
Submission link:277874595
Upd: The issue was I was calculating the moves array before(which might use paths after s) but i could only use the paths before s. I fixed it and got AC.
I see, that's good to know. You're absolutely right, we must compute the distance array incrementally, while Elsie is behind Bessie. I should edit my comment to point that out. Thanks!
As you've found out, the first TC where a solution using a precomputed array fails is number 26 of test 4, for which the answer should be 1000011111 and the input is:
for the second solution of E1
what if a[l] = a[r] = false
and with the new sum : x = P[r — 1] — P[l] && x >= next greater && prev greater
cant this be the maximum ?" ( after adding x + a[l] we will have a new maxi we didnt check before ) that can leads to possible answer ?
Problem B was so easy, can't believe I didn't get it T_T
Just solved A, got -71 delta
预防B题诈骗，人人有责
Preventing fraud in question B is everyone's responsibility
---------------------------------------------------------- //CODE ~~~~~ // this is code
include <bits/stdc++.h>
using namespace std;
define int long long
define sp ' '
void solve() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; reverse(a,a+n); if(n%2==1) { int pt=n/2; int temp=a[pt]; a[pt]=a[pt-1]; a[pt-1]=temp; } for(int i=0;i<n;i++) cout<<a[i]<<sp; cout<<endl; } signed main(void) { int t; cin >> t; while (t--) solve(); return 0; }
~~~~~
FOR B I DONT UNDERSTAND WHAT WRONG WITH MY CODE.CAN SOMEONE HELP?
https://codeforces.me/contest/1998/submission/275895287
Task C is so stupid and many posts down can approve my words. Unclear explanation and code not working. Please give us really good explanation. And when you post your code, you need to give him really clear isn't it? (It's about: kk? z? what does it mean??). I also can't do this task lower than O(10^14).
Tutorial for C rephrased for newbies like me:
think iterativelyand try to check if a number can be medianRelax!rather than thinking if a number can be median think if median can be greater than or equal to that number:)Hmm, it seems that problem E1 has a randomized solution as well. Let's find $$$l_i$$$, $$$r_i$$$ for each $$$i$$$ where $$$[l_i, r_i]$$$ is the maximal segment we can merge without discarding ball $$$i$$$. Then it is clear that if ball $$$i$$$ can subsume ball $$$j$$$ then $$$l_i \le l_j \le r_j \le r_i$$$ holds.
Now simply run the trivial algorithm for all $$$i$$$ in random order: try to add the elements from both sides to the current segment. When adding a new element in such a way, immediately apply the optimization from above ($$$l_i = \min(l_i, l_j)$$$, $$$r_i = \max(r_i, r_j)$$$).
Now, how many times would we add an element $$$j$$$ for different $$$i$$$ (e.g. to the right side of the segment). Suppose it happened for $$$i_1, \dots, i_k$$$ (in order). Then it's clear that $$$i_1 < \dots < i_k$$$ (otherwise we would jump over $$$j$$$ thanks to the optimization). But the length of the longest increasing sequence is expected to be $$$O(n^{1/2})$$$ (actually it shouldn't be much harder to derandomize such a solution).
276336073
Is that proved after shuffling a container of different values the Expected LIS is √n?
I think in problem D we can add edge instead of erase it.Below is my submission,time complexity is O(n) 276931199
预防B题诈骗，人人有责
Preventing fraud in question B is everyone's responsibility
E2 is a nice problem,double experience https://www.luogu.com.cn/problem/P9530
In Cthis my idea was that basically, all the elements from median of the original array to the max element of the original array would have a chance for affecting the maximum value, and further I thought of two cases where if A’s B[i]==1. then we would simply add k to A[i] and use the original median of the n-1 elements, else if A’s B[i]==0 then we would have to find the rightmost idx to the left of the median where B[i]==1 then we can check if adding k to it affects the median, if it does then the new median would be this A[i]+k, and then we can add it to the A[i] from right and if no such index is found then we can just add A[i]+old median , but what am I missing here.Link to solution: https://pastebin.com/ux1dK3fw