As per history of codeforces, whenever a tester says the round will be very good, the contest turns out to be bad.

fucking clickbait

I'm sorry that these two tasks had to be replaced, I hope that we'll see them in the future.

Maybe one task is best of 2011.

This comment didn't age well.

Happy Birthday In Advance..

Don't judge without seeing the problems. Coordinators,testers,setters know the problems and according to that they would have set the duration. So probably 2 hours would be appropriate.

It's funny that such a things are proposed by a participants who anyway will not solve all of them :)

Thanks for being considerate of the very small fraction of the LGMs who has the ability to AK the round, but may get into time trouble.

don't worry for tourist.

Agreed

А я вам желаю решить все восемь задач :)

I am also thinking about it ;)

Prizes

Previously you got double happiness of Grandmaster and 69 at once so it got balanced.

I think because it has prize and div 2 users also have chance to win the prize

If anyone interested, it didn't even offer me to proceed to the contest page

But still more than a t-shirt, see current price

Near year party is over

Hahahahaha.

TimDee

find any wrong positions of any two elements and replace their columns then check your solution is correct or not. wrong positions means that an array element such that it doesn't exist in allowed position in a sorted array .

for example : in this array [1,2,3,3,4], the allowed positions for 3 is 3 or 4 only and for 2 is 2 only .

Find the first index i such that a[i] > a[i+1]. Now, all elements at index less than equal to i will be sorted, so you can't swap a[i+1] with some a[j], j < i. Also a[i] can't be swapped with a[j], j < i. So you can only swap a[i] with some a[j], j > i. So find j such that a[j] <= a[i+1] and (j+1 == n || a[j+1] >= a[i]). Swap columns i and j

Consider this test

1
3 1
2 1 1

your solution says that the answer is 4, but you can achieve a score of 3 by jumping over the third trap.

Failing testcase: Ticket 7275

I take my words back. Very weak pretests, especially for task C

I think you should read the problem statement carefully.

how was C casework?

It took me forever to figure out WA pretest 6 lol.

On the topic of samples, the samples of D are so weak that if you mistakenly sort by $$$a_i - i$$$ (or even just $$$a_i$$$) instead of $$$a_i + i$$$ you will still pass the samples.

For F I have the same opinion with you, But does the person who didn't put case n = 1 and m = 1 in this problem have the permission to say this thing?

My solution to C require no casework (though I don't know if I will FST)

Sort each row and check if there are at most 2 columns that differ. And if there are such 2 columns we try swapping them.

dirty case-work, AND the pretests were among the weakest in recent history. In a problem with multiple test cases per input, so there is no excuse for this. Disgusting.

what dirty case work? just sort the columns lexicographically and find the number of non-equal columns what kind of case work is that?

I did a greedy

It's greedy

I didn't use DP. Refer it if it passes system test :|

For me both D and E were instant, F required some thinking. Should have thought a bit more though, almost TLEd in system tests, with 1949ms / 2000ms >_>

Based on the previous comments of yours, I feel like ranting about math problems in a contest is a recurring theme of yours lol.

That's how I felt, too :)

After wasting 20+ minutes on paper trying to do math and coming up empty handed, I started trying to guess the formula. Guess I should do less math and more guessing from now on...

You can do it with two segment trees, one for sum and one for count of distinct numbers.

I binary search the largest possible MEX, then remove group of numbers more than MEX greedily.

First drop the first k traps and then start from k + 1 and check if there is a better drop than the worst drop from the previous k drops.

I used a Heap for this.

find any wrong positions of any two elements and replace their columns then check your solution is correct or not. wrong positions means that an array element such that it doesn't exist in allowed position in a sorted array .

for example : in this array [1,2,3,3,4], the allowed positions for 3 is 3 or 4 only and for 2 is 2 only .

You can refer to mine. 157703045 I just checked if there exists any such row where the (j+1)th element is smaller than the jth element, if it exists then I simply marked that row and and searched for two indices in that particular row where the numbers should be swapped. Then simply for that two indices i swapped the values for every row. After that simply traversed the matrix and checked whether the conditions are violated or not. If any such case found then print -1. else print those two indices.

First of all if $$$m = 1$$$, then the answer is $$$1$$$ $$$1$$$ otherwise :

We consider a number in an array $$$bad$$$ if it is not in it's correct place in sorted form of the main array, So if the number of $$$bad$$$ numbers in any row was more than $$$2$$$ then the answer is $$$-1$$$, In other cases, Store the index of one of the rows that has exactly $$$2$$$ $$$bad$$$ numbers, then find the indices of two $$$bad$$$ numbers in that row, For example they're at indices $$$i$$$ and $$$j$$$, then swap all the pairs at indices $$$i$$$ and $$$j$$$ for each row or better to say is swap column's $$$i$$$ and $$$j$$$, Then after all if you found any row unsorted, the answer will be $$$-1$$$ otherwise the answer will be $$$i$$$ and $$$j$$$.
157737517

26 were enough :P

Same here :(
Found out WA test only after the contest end :(

How do you know it as of now? AFAIK, system testing has not yet begun.

You guys are not already depressed?

But in this round there was a constrain , i.e a<b<c. Which makes the problem in this contest easier

Consider the amount of damage you prevent by picking each trap. Say the first trap you pick is index $$$i$$$. You save $$$a_i - (n - i)$$$ damage because you no longer take $$$a_i$$$ damage from the $$$i$$$th trap, but all $$$n - i$$$ traps after index $$$i$$$ take bonus damage. After picking the first trap, ALL remaining values increase by $$$1$$$. Traps before index $$$i$$$ increase by $$$1$$$ because there is one less trap after it that takes bonus damage. Traps after index $$$i$$$ also increase by $$$1$$$ because you save the $$$+1$$$ bonus damage dealt by index $$$i$$$ by choosing that trap. So all values change by the same amount, and it is correct to still sort by $$$a_i - (n - i)$$$ for future decisions.

There is an easy proof by changing the problem to an equivalent one.

Note that we always jump exactly k times. Change the problem, such that we DO take the bonus damage when jumping over a trap (we still don't take the trap's base damage). Note that the answer to the changed problem is always $$$k (k - 1) / 2$$$ larger than the answer to the original, so subtract this from your answer to get an equivalent problem.

But now, the damage we avoid by jumping over trap $$$i$$$ (zero-indexed) with damage $$$a[i]$$$ is exactly $$$a[i] - (n - 1 - i)$$$, as desired.

It works in O(c). It's obvious that it TLEs if a = 1 b = 2 c = 1e8 and 10000 testcases.

Test case #77 for D:

1
10 5
1 1 1 1 1 1 1 1 1 1

I also got WA 77. The mistake I made in my code is that k * (k-1) / 2 in line 64 should be i * (i-1) / 2. How did it passed the pretest??

and the pretests of D also

problem B

*systest

I feel the need to identify myself as one of the big + 2*small jokers because I just find it so incredibly funny that you can pass systests with such a mistake