### cry's blog

By cry, 3 months ago,

#### 1998A - Find K Distinct Points with Fixed Center

Problem Credits: sum
Analysis: cry

Solution
Code (C++)

#### 1998B - Minimize Equal Sum Subarrays

Problem Credits: satyam343
Analysis: cry

Solution
Code (C++)

#### 1998C - Perform Operations to Maximize Score

Problem Credits: cry, satyam343
Analysis: sum, satyam343, Dominater069

Hint 1
Hint 2
Hint 3
Solution
Code (C++)

#### 1998D - Determine Winning Islands in Race

Problem Credits: cry
Analysis: cry

Solution
Code (C++)

#### 1998E1 - Eliminating Balls With Merging (Easy Version)

Problem Credits: cry, sum, satyam343
Analysis: sum

Solution 1
Code 1 (C++)
Solution 2
Code 2 (C++)

#### 1998E2 - Eliminating Balls With Merging (Hard Version)

Problem Credits: cry, sum, satyam343
Analysis: sum

Solution
Code (C++)
• +154

 » 4 weeks ago, # | ← Rev. 2 →   +63 first, I feel like B is a problem you can really get stuck on if you don't guess it
•  » » 4 weeks ago, # ^ |   +6 True that,I tried proving multiple approaches while guessing and wasted time.
•  » » » 4 weeks ago, # ^ |   +3 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).
•  » » 4 weeks ago, # ^ |   +4 Yeah, I wasted 20mins on it.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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 .
•  » » » 4 weeks ago, # ^ |   0 I guessed it. Tried the simples solution which felt logically right and the rest was luck
•  » » 4 weeks ago, # ^ |   0 i did. I cant believe its so easy
 » 4 weeks ago, # | ← Rev. 2 →   +24 Bonus: E2 can be solved in $O(n)$ time. 275655689
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 Nice, I have a bit of a different $\mathcal{O}(n)$ via Cartesian tree: 275679381
•  » » » 4 weeks ago, # ^ |   0 Just compare a point's value with the sum of its subtree right?
•  » » » 4 weeks ago, # ^ |   0 why is there a ycombinator template in your code lol
 » 4 weeks ago, # |   +10 Can someone estimate an upper bound on no of states in these solutions for E1 and E2? Or hack otherwise? 275608667 275619707
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +18 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
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 (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.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 Also E2, because his logic surrounding the questionable complexity part is not changing in any significant way
•  » » » » » 4 weeks ago, # ^ |   0 275664378 E2 without map.
 » 4 weeks ago, # |   +3 Thanks for making me break the record of my worst rank ever:)
•  » » 4 weeks ago, # ^ |   +1 You not alone bro :P, let's get back our rating points together in next contest ;)
•  » » 4 weeks ago, # ^ |   0 Me too. I got stuck on C. Now I'm nearly specialist.
 » 4 weeks ago, # | ← Rev. 2 →   +17 The two codes of problem E1 are same,cry please fix it,thx.
 » 4 weeks ago, # |   +2 B can be solved using one cyclic shift
•  » » 4 weeks ago, # ^ |   0 how did you thought about it?
•  » » » 4 weeks ago, # ^ |   +1 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).
•  » » » 4 weeks ago, # ^ |   0 I tried to minimize segments of length one
 » 4 weeks ago, # | ← Rev. 2 →   +6 For D I have a better solution which works in O(n + m). vector 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 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
•  » » 4 weeks ago, # ^ |   0 what does the vector mpjt contain?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +9 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.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 4 weeks ago, # ^ |   0 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?
 » 4 weeks ago, # |   +5 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.
•  » » 4 weeks ago, # ^ |   0 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
•  » » » 4 weeks ago, # ^ |   +10 b..but you are Ayanokoji
 » 4 weeks ago, # | ← Rev. 2 →   0 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.
•  » » 4 weeks ago, # ^ |   +7 Really all this for div2 A??
 » 4 weeks ago, # |   0 This blog was created 7weeks ago?????
 » 4 weeks ago, # |   0 Attached code for C doesn't pass samples?
 » 4 weeks ago, # |   0 Editorial code for Problem C doesn't work for this valid test case Testcase$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).
•  » » 4 weeks ago, # ^ |   +1 Yeah... No. Editorial code kinda also outputs $11$.
•  » » » 4 weeks ago, # ^ |   +3 they changed the code.
 » 4 weeks ago, # | ← Rev. 2 →   +5 You can also do E2 using the same DnC approach in the solution 1 to E1my subit 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
 » 4 weeks ago, # |   +20 In C: " Observe that it is optimal to only consider removing the largest element with bi=0", did you mean guess? Please give proofs...
•  » » 4 weeks ago, # ^ |   +5 I also was not able to observe that and solved a harder problem, used prefix sum and ordered multiset. 275621322
•  » » 4 weeks ago, # ^ |   0 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 changeif $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 betterif $a_i •  » » » 4 weeks ago, # ^ | 0 if ai=ao , then swapping the choice would increase the median by at most am−ai , we pay am−ai for the swap as well, so the result won't be better can u explain this more ? •  » » » 4 weeks ago, # ^ | 0 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 •  » » 4 weeks ago, # ^ | +13 totally changed the editorial, i hope its fine now :) •  » » » 4 weeks ago, # ^ | 0 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 •  » » » » 4 weeks ago, # ^ | 0 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(cn) and keep max element constant. this means that either max remains constant or median of the others remains constant.....which are 2 separate caseswhen max remains constant, we want to maximise median of others and vice versa •  » » » » » 4 weeks ago, # ^ | ← Rev. 2 → 0 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 •  » » » » » » 4 weeks ago, # ^ | 0 Ahhh!! Got it got it. I am a moron Thanks @Dominator069  » 4 weeks ago, # | +16 C is much harder than D to me, spent twice as much time solving it  » 4 weeks ago, # | 0 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 ?  » 4 weeks ago, # | ← Rev. 2 → +6 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+12) 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 endik that the explanation is not that good, but idk how to explain this more precisely, so forgive me for that  » 4 weeks ago, # | 0 nice contest. it'd be great if authors add hints before solutions in their editorials  » 4 weeks ago, # | 0 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. •  » » 4 weeks ago, # ^ | 0 For k=2 and xc=yc=0You will output (0, 0) and (0, 0)  » 4 weeks ago, # | +3 "(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. •  » » 4 weeks ago, # ^ | 0 In original array the position doesn't matter, so I think it's quite obvious. Anyway editorials should be as clear as possible  » 4 weeks ago, # | 0 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'  » 4 weeks ago, # | ← Rev. 2 → +4 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  » 4 weeks ago, # | 0 Why this solution of mine for A is giving WA on test 4? 275601626  » 4 weeks ago, # | 0 Thanks for making me break the record of my worst rank ever:)  » 4 weeks ago, # | 0 C is too difficult! Why you put such a difficult problem in that position!  » 4 weeks ago, # | 0 example of problem B why can't the second(i,j)take (4,5)?Doesn't that go against the meaning of the solution?  » 4 weeks ago, # | ← Rev. 2 → 0 I have a confusing way to solve E1. I could even not calculate its time complexity.275618236Could anyone help me to prove its correctness or hack it?  » 4 weeks ago, # | 0 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  » 4 weeks ago, # | +5 How to even analyze in B ?I mean I kept thinking about half an hour without reaching any conclusion. •  » » 4 weeks ago, # ^ | 0 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  » 4 weeks ago, # | ← Rev. 4 → 0 For C there is also more naive O(N * log(MAX_ELEM + K) * log(N)) solution.https://mirror.codeforces.com/contest/1998/submission/275689471We 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 array1 2 (4) 5 8we will need to put it between 5 and 8 — test_pos also is found with binary searchif 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 changeableSo, 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  » 4 weeks ago, # | 0 has anyone done problem C without the use of binary search ?  » 4 weeks ago, # | ← Rev. 4 → 0 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 — 2) / 2].first; ans = max(ans, 0LL + a[i].first + k + mc); }  •  » » 4 weeks ago, # ^ | 0 the sorted order of A may change after the K operations Notice the curious wording : We do operations on the element which becomes max eventually.  » 4 weeks ago, # | 0 -20 -32 -21 -33 100000000 100000000 -100000000 -100000000 99999999 99999999 -999999999 -99999999 99999998 99999998 -99999998 -99999998for problem A why the center is not -5,-8, 8 for this test case i think this should work  » 4 weeks ago, # | ← Rev. 4 → 0 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  » 4 weeks ago, # | 0 If anybody can complete the proof that would be nice of you. Thanks.My construction for AWe 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$\approx10^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! •  » » 4 weeks ago, # ^ | 0 Check my solution down  » 4 weeks ago, # | ← Rev. 2 → 0 Here're my insights for Problems A,B Problem ALet the points you want to output is$\displaystyle (x_1,y_1) , (x_2,y_2) , ... , (x_k,y_k)$the center is$\displaystyle (\frac{\sum_{i=1}^{k} x_i}{k},\frac{\sum_{i=1}^{k} y_i}{k})=(x,y)$which means that$\displaystyle \sum_{i=1}^{k} x_i=kx$.$\displaystyle \sum_{i=1}^{k} y_i=ky $So we have : -$\displaystyle \begin{cases} k=1 \rightarrow (x,y) \\ k \mod 2=0 \rightarrow \displaystyle (x-\frac{k}{2},y-\frac{k}{2}),(x+\frac{k}{2},y+\frac{k}{2}),........,(x-k,y-k),(x+k,y+k)\\ k \mod 2=1 \rightarrow (x-\frac{k}{2},y-\frac{k}{2}),....,(x+\frac{k}{2},y+\frac{k}{2}) \\ \end{cases}$. Python Codedef 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() $\text{Time Complexity : } \mathcal{O}(k)$Problem BLet'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$\displaystyle \mathtt{sorted}(p[i:j]) \neq \mathtt{sorted}(q[i:j])$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)$. Python Codedef 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 !  » 4 weeks ago, # | ← Rev. 3 → 0 ok  » 4 weeks ago, # | 0 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?  » 4 weeks ago, # | 0 "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.  » 4 weeks ago, # | 0 I had the goofiest, most overcomplicated solution to C.275828049  » 4 weeks ago, # | ← Rev. 2 → 0 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 •  » » 3 weeks ago, # ^ | ← Rev. 2 → 0 I have a similar approach but I am getting WA on TC 26 .. any idea where I am making mistake.Submission link:277874595Upd: 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. •  » » » 3 weeks ago, # ^ | 0 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: Input11 6 5 9 6 9 1 7 6 8 1 6 1 3   » 4 weeks ago, # | 0 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 ?  » 4 weeks ago, # | ← Rev. 3 → 0 Problem B was so easy, can't believe I didn't get it T_TJust solved A, got -71 delta •  » » 3 weeks ago, # ^ | 0 预防B题诈骗，人人有责Preventing fraud in question B is everyone's responsibility » 4 weeks ago, # | 0 ---------------------------------------------------------- //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? •  » » 4 weeks ago, # ^ | 0  » 4 weeks ago, # | 0 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).  » 4 weeks ago, # | 0 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:)  » 4 weeks ago, # | ← Rev. 2 → 0 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
•  » » 2 weeks ago, # ^ |   0 Is that proved after shuffling a container of different values the Expected LIS is √n?
 » 4 weeks ago, # |   0 I think in problem D we can add edge instead of erase it.Below is my submission,time complexity is O(n) 276931199
 » 3 weeks ago, # |   0 预防B题诈骗，人人有责Preventing fraud in question B is everyone's responsibility
 » 13 days ago, # |   +3 E2 is a nice problem,double experience https://www.luogu.com.cn/problem/P9530