first, I feel like B is a problem you can really get stuck on if you don't guess it

Bonus: E2 can be solved in $$$O(n)$$$ time. 275655689

Can someone estimate an upper bound on no of states in these solutions for E1 and E2? Or hack otherwise? 275608667 275619707

Thanks for making me break the record of my worst rank ever:)

The two codes of problem E1 are same,cry please fix it,thx.

B can be solved using one cyclic shift

For D I have a better solution which works in O(n + m).

vector<int> adj[N], radj[N];
 
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) adj[i].clear(), radj[i].clear();
    for (int i = 1; i < n; i++) adj[i].push_back(i + 1), radj[i + 1].push_back(i);
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        if (u > v) swap(u, v);
        adj[u].push_back(v);
        radj[v].push_back(u);
    }
    vector<int> mpjt(n + 1);
    int mj = 0;
 
    for (int s = 0; s < n - 1; s++) {
        for (int z : radj[s]) mpjt[s] = max(mpjt[s], mpjt[z] + s - z - 1);
        for (int z : adj[s]) mj = max(mj, mpjt[s] + z - s - 1);
        if (mj > s) cout << 0;
        else cout << 1;
    }
    // cout << mpjt;
}

275623093

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 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.

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

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...

C is much harder than D to me, spent twice as much time solving it

Observe that it is optimal to only consider removing the largest element with bi=0
 (in fact if the last element has bn=1
 then we don't even need to consider it given that increasing an
 is the same or better than increasing the median). This leads to an O(nlogmaxai)
 solution.

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://mirror.codeforces.com/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.

"(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.

Guys, what's wrong with my code? Can someone pls help:

def read_num(): return int(input())
def read_nums(): return map(int, input().split())
def read_list(): return list(map(int, input().split()))
def get_yn(o): return 'YES' if o else 'NO'

t = read_num()
outs = []

for _ in range(t):
    
    n, k = read_nums()
    a = read_list()
    b = read_list()
    
    v = [[a[i], b[i]] for i in range(n)]
    v.sort(key=lambda x: x[0])
    
    ans = v[n//2-1][0] + v[-1][0]
    
    if v[-1][1]:
        ans += k
    else:
        for i in range(n-1, n//2, -1):
            if v[i-1][1]:
                ans = max(ans, v[n//2-1][0] + max(v[i-1][0]+k, v[-1][0]))
            
        for i in range(n//2, 0, -1):
            if v[i-1][1]:
                if v[i-1][0]+k>v[n//2][0]:
                    ans = max(ans, v[n//2][0] + max(v[i-1][0]+k, v[-1][0]))
                else:
                    ans = max(ans, max(v[n//2-1][0], v[i-1][0]+k) + v[-1][0])
            
        back, med, mul = 1, v[n//2-1][0], 1
        
        if v[n//2-1][1]:
            for i in range(n//2+1, n+1):
                if (v[i-1][0] - med)*mul <= k:
                    k -= (v[i-1][0] - med)*mul
                    med = v[i-1][0]
                    ans = max(ans, med + v[-1][0])
                    
                    if v[i-1][1]==1:
                        mul+=1
                    else:
                        idx = n//2-back
                        if idx>=1 and v[idx-1][1] and med-v[idx-1][0]<=k:
                            k-=med-v[idx-1][0]
                            mul+=1
                            back+=1
                        else:
                            break
                else:
                    break
                
                med += k//mul
                k%=mul
                
                if i==n+1:
                    ans = max(ans, 2*med)
                else:
                    ans = max(ans, med+v[-1][0])
                
            
                
    outs.append(ans)

for out in outs:
    print(out)

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.

For C there is also more naive O(N * log(MAX_ELEM + K) * log(N)) solution.

https://mirror.codeforces.com/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 to value * 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.

// 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 &mdash; 2) / 2].first;
 ans = max(ans, 0LL + a[i].first + k + mc);
}

-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!

Here're my insights for Problems A,B

def solve():
    x,y,k=map(int,input().split())
    if(k==1):
        print(x,y)
        return
    else:
        if(k%2==0):
            for i in range(k//2,k):
                print(x+i,y+i)
                print(x-i,y-i)
        else:
            for i in range(-(k//2),k//2+1):
                print(x+i,y+i)
    
for _ in range(int(input())):
    solve()

def solve():
    n=int(input())
    p=list(map(int,input().split()))
    q=[p[-1]]
    for i in range(n-1): q.append(p[i])
    print(*q)

for _ in range(int(input())):
    solve()

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

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

---------------------------------------------------------- //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?

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:

• if k=0 then max score is max_elt + median of rest
• if k>0 then max score can be got by max of
• what we get when we increment only max element that can be incremented (incrementing it partially will not lead us to a better score if it turns out to be the max element. If it isn't the max element eventually then the other case takes care)
• keep the max element fixed and increment such that median is increased(if max gets changed during this incrementing then the first case will take care)
• to deal with the second case
• instead of finding a formula, think iteratively and try to check if a number can be median
• very nice trick: Relax! rather than thinking if a number can be median think if median can be greater than or equal to that number
• now see binary search is applicable:)

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

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 C this 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

Delet

Cleaner solution to C

#include <bits/stdc++.h>
#define MAXN ((int)2e5+10)
#define MOD ((int)1e9+7)
#define int long long
#define endl "\n"
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> nums(n);

    for (auto &x : nums)
        cin >> x.first;
    for (auto &x : nums)
        cin >> x.second;

    sort(nums.begin(), nums.end());

    // Refer to the sorted array [1, 3, 5, 7], n = 4.
    // If we take i = n / 2 = 2, this would be the array:
    // [1, 3, 7], whose median is i = 1 = n / 2 - 1.
    // In fact, for every index >= n / 2, this shift occurs,
    // where we take the element to the left of the median,
    // which, in this problem, is defined as the floor of n / 2.
    // Now if we take some element like i = 0, this becomes
    // the array: [3, 5, 7], where the median is i = 1 (2 in
    // the original array, which is n / 2). Therefore, the
    // median of the remaining array is a[(n / 2) - 1] if
    // the removed element has i >= n / 2; otherwise, it is
    // a[(n / 2)].

    int ans = 0;

    // Apply the k operations on the biggest changeable number.
    for (int i = n - 1; i >= 0; i--)
        if (nums[i].second == 1){
            ans = nums[i].first + k + nums[n / 2 - (i >= n / 2)].first;
            break;
        }

    // Now that we've covered the possibility os spending all operations on a single number,
    // let's also see what happens when we try to instead increase the median. In order to
    // increase the median, we need to make ceil(n / 2) elements at least equal to it. That
    // is, for an odd-sized array like 3, at least 2 elements need to be greater than or
    // equala to the median. For an even-sized array, exactly half of more need to be
    // at least the median.

    // Binary search for the biggest median achievable.
    int left = 0, right = 2e9;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;

        int good_elements = 0;
        priority_queue<int, vector<int>, greater<>>bad_elements;

        for (int i = 0; i < n - 1; i++) {
            // Tag the elements greater than or equal to the median (no change required)
            if (nums[i].first >= mid)
                good_elements++;
            
            // If nums[i] < median, but it's changeable, let's see how much it would cost 
            // to bring this element up to the desired median and add such cost to a
            // min-heap (priority queue). Later, we'll greedily only spend the operations
            // on the elements that are closer to reaching the median
            else if (nums[i].second == 1)
                bad_elements.emplace(mid - nums[i].first);
        }

        int remaining = k; // Remaining operations (initially all k operations are available)
        while (!bad_elements.empty()) {
            // Cost to bring an element to the median
            int cost = bad_elements.top();
            bad_elements.pop();

            // If we can afford the change, go ahead and do it 
            if (remaining >= cost) {
                remaining -= cost;
                good_elements++;
            }
            // If we can't afford it, we won't be able to change any of the following
            // elements, since it's a min-heap (all the other elements are at least x).
            // There's no point in continuing, so break out early.
            else
                break;
        }

        // If there are at least ceil(n / 2) elements greater than or equal to the median,
        // this median is achievable and we can move on to a larger one
        if (good_elements >= (n + 1) / 2)
            left = mid;
        // else this median is too big and we'll try a smaller one
        else
            right = mid - 1;
    }

    // The optimal answer is the maximum between what we got just incrementing a single
    // element k times and what we got increasing the median. It's always optimal to add
    // the new median to the largests element, so we don't even have to check the other ones.
    ans = max(ans, nums[n - 1].first + left);
    cout << ans << endl;
}

signed main() {
    #ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}