speedyy voventa

What did you just do?

bro solved using probabilities, absolute legend.

look at the guy right below you. youre prob his next target LOL

hey, how is that even possible?? xD In case: l = 100000, r = 200000 chance of success is 1%

Would 4500 iterations of selecting random x work well? I'm curious :3

u guys are genius

HAHA, i tried your approach in problem F to get some random intervals and then check their max

element and sum and appending them in a set, see this submission

But it didn't work XD

Hi,

My sub: https://mirror.codeforces.com/contest/2121/submission/335065195

Can you help me understand what wrong with this? I am getting WA.

I am finding the differing len in diff between those nums. Apart from Most significant decimal we will have ans =0 for below indexes. For differing length(detLen) and above index, i am computing.

Thanks.

what's wrong with my solution submission link :- https://mirror.codeforces.com/contest/2121/submission/337553309

What a madlad

Posting suspicious solutions in chat before the hacking round is over invites attention. :)

Dk what u mean exactly but it sounds super cool!

Let $$$a$$$ and $$$b$$$ be the arrays after sorting, but before swapping.

Then for any $$$i$$$, we have that $$$\min(a_i, b_i) \leq a_i, b_i$$$. But at least one of $$$a_i$$$ or $$$b_i$$$ must be smaller than $$$\min(a_{i+1}, b_{i+1})$$$, because one of them was placed before $$$\min(a_{i+1}, b_{i+1})$$$ whilst sorting. So we have that the mins are increasing.

By similar reasoning, for any $$$i$$$, we have that $$$\max(a_i, b_i)$$$ is less than at least one of $$$a_{i+1}$$$ or $$$b_{i+1}$$$ because $$$\max(a_i, b_i)$$$ was placed before one of them whilst sorting. Since we have that $$$a_{i+1}, b_{i+1} \leq \max(a_{i+1}, b_{i+1})$$$, we have that the maxes are increasing.

So we have that $$$\min(a_1, b_1) \lt \min(a_2, b_2) \lt \dots \lt \min(a_n, b_n)$$$ and $$$\max(a_1, b_1) \lt \max(a_2, b_2) \lt \dots \lt \max(a_n, b_n)$$$, so if we place all of the mins in $$$a$$$ and all of the maxes in $$$b$$$, both arrays remain sorted.

After sorting, we have:
- a[i] < a[i+1] for all i
- b[i] < b[i+1] for all i

Now, when we decide to swap because a[i] > b[i], we need to verify that the swap won't violate the sorted order of either array.

Swapping b[i] into a:

We're putting b[i] in place of a[i]. Since we originally had b[i] < a[i] < a[i+1], it follows that b[i] < a[i+1], so inserting b[i] into a won't break the increasing order in a.

Swapping a[i] into b:

This is more subtle. It's possible that a[i] > b[i+1], which would break the sorted order in b. However, since b[i+1] < a[i] < a[i+1], on the next iteration (i+1), we will again encounter a[i+1] > b[i+1], and thus perform another swap. This chain reaction will make sure that the arrays remain valid.

simple proof for min(a[i], b[i]) < min(a[i + 1], b[i + 1])

d1 = a[i + 1] - a[i], d1 > 0

d2 = b[i + 1] - b[i], d2 > 0

min(a[i], b[i]) < min(a[i] + d1, b[i] + d2) because both arguments of min have increased

how did you easily get D?

can u explain it.. can't figure out ,been thinking 'bout it for like 2 hours straight. a strong hint is also welcome ,like don't explain everything but only what u feel is the critical optimization part.

can you explain the ans[i-1] + part? i dont get it.

sumit sir :)

That's a clever approach. Thanks for sharing it.

I wanted to point out that the tutorial's solution can also be made $$$O(n)$$$ trivially by using a counting sort instead of a comparison-based sort, since all the elements are between $$$-n$$$ and $$$n$$$.

In fact, you can think of Kilo_5723's solution as doing an online counting sort: at the end of the loop, the array val contains a count of the elements of pref in the tutorial. The “online” part is that he updates the total for each character processed, which is why there are only additions/subtractions and no multiplications.

https://mirror.codeforces.com/contest/2121/submission/325347841

Here's mine also with O(n) time

Seems a little simpler

UPDATE.

Solution Explanation: Comment

After the Hacking period is over, everyone's submissions will be finalized. I would expect them to be back by early morning EST.

I simply used a Lazy Segment Tree; after compressing all values, let $$$\mathrm{dp}[k][v]$$$ be the maximum length of a non-decreasing subsequence using the first $$$k$$$ intervals and ending in $$$v$$$.

Initially (for $$$k = 0$$$), the maximum length is always $$$0$$$. For a fixed $$$k$$$, all non-decreasing subsequences ending in $$$[0; l]$$$ can be "extended" by one by simply appending $$$l$$$ to it. At the same time, all subsequences ending in $$$v \in [l; r]$$$ can be "extended" by $$$v$$$; two operations that can be easily implemented for a Segment Tree!

So in the end, you simply maintain a Lazy Segment Tree containing all possible ending values and update that for each step in $$$\mathcal O(\log n)$$$ time.

Submission: 324887791

The 4 can only become a 3, and will then remain the max. You can use the decrement op at most once. How will you get a 2 max for this?

Yeah.

Suppose the max element in matrix is 9 and rest of the elements are 5.

5 5 5

9 5 5

Now we can choose r=2 and c=1 and ans will be 7 but according to algorithm we get 8. if maxx=largest element in matrix and secondMaxx= 2nd largest then, I tried writing two diff cases for when maxx-secondMaxx>1 and maxx-secondMaxx==1.

Even in the first test case

1 1

1

The answer should be -1 right? After choosing r=1 and c=1. Can anyone please explain where I have gone wrong?

The problem asks you to output the manimum possible maximum value. Meaning, you have to find out after doing one operation, what is the maximum value in the matrix? You have two cases, then

1) Lets say the maximum number has a count of 1 in the entire matrix, thus, you can simply reduce it by 1 and that's your answer.

2) If there are more than 1 count of the maximum in the matrix, then you will have to check if its possible to reduce all of them with one operation or not. If its possible, then the answer is mx — 1. If its not possible, then the answer is mx

1 3 3 1 2 3 4 1 2 4 1 2

In this test case, its possible to choose row = 2, and column 2 to reduce all the 4s to 3s. Thus, the final maximum value will be 3

I dont see anything to worry about. I guess its from the vectors. I beilive they dont deallocate themselves. I dont know to help you with this one. Try long long a[] insead of vectors

You're using inbuilt swap function which stores the elements it is swapping and since you're swapping around 1600 pairs worst case for every test case. for 100 test cases it will add and you'll have to store 160000 pairs which is causing the memory limit exceed. you can instead of using inbuilt swap function swap them manually and it should pass

C can be solved with minimal efforts if you have 2D Sparse Table template in hand

Maybe not :) hah

I think that you are linearly iterating on the vector mpp[key] and that will give a tle if suppose there are lost of zeroes so mpp[key].size() will assume linear size and not logarthmic size

ItsNotMeItsYou I have also did the same thing in contest but got FST on system test-13 can you please tell me why it is failing My submission : My Submission