Worst Contest I have Ever Seen!..

Ak2006: am i a joke to you?

They also forgot to thank X for excellent coordination and help with preparation

diamond 1, finally!

no pro Rocket League roster yet, only the fan one :)

I've read all of your submissions on Codeforces, really really impressive.

Give all the contests except Div1. This contest has Div2 questions in the beginning so you can participate.

Do participate in all contests. Even if ratings go down, it can be recovered in 2-3 good rounds.

*cries in hard-stuck Iron [Valorant]

That's some skill right there

what happened in the last round ? you posted the same comment last round right?

It should be obvious by now mate, Codeforces >>>>>>>>>> classes :)
Best wishes for the round ! <3

D1: You can do it using a simple O(nk) DP (define state dp[i][j] as the minimum time to do the ith task such that the other machine (the one which doesnt do the ith task) last did the jth task). Transitions will also be quite easy, you need to handle the case wherein (i-1)th task = ith task separately though.

implementation: https://mirror.codeforces.com/contest/1799/submission/195167349

D2: If you observe the transitions carefully you will notice that at each i, what happens is that we do a range sum update on some dp values from the dp[i — 1] table and set them to their corresponding values in dp[i] table, and a point update on one dp[i — 1] value and set it to its corresponding dp[i] value, so this can be done easily using a segment/fenwick tree.

implementation (segtree): https://mirror.codeforces.com/contest/1799/submission/195178402

I solved both D1 & D2 without segment tree or Fenwick. You can watch my video editorial if you are interested: https://youtu.be/oOyPQL16x1M

Also there is a similar approach here

I tried my best and got WA on 4th pretest :'(

I have a quite long solution for problem C although I don't know how to prove it yet: Firstly, create two pointers p1 ( set to 0 ) and p2 (set to n), then save all the strings to a map and then iterate through the map, then for each key in the map, if the frequency of that key is divisible by 2, then simply put the first appearance of the character in p1, the next one to p2, the next one to p1, etc until it ends. If the frequency of that key is odd, do the same process for the n-1 number and then break out of the map. At this time, there are 4 cases : 1. If the map is now completely empty, we can check for the constructed string and reverse version of it to output the larger one out. 2. if the map size is equal to 1, then put the last element in the map in the position string size/2 and printout the larger of the constructed string and its reverse version 3. If the map size is >= 3, then we can put the current element in position of p1 and the other element in the map inside the string in reversed order and output 4. If the map size is equal to 2, then we can put the remaining 1 element in the middle of the string and then put all the other inside it and output it .

Code : https://mirror.codeforces.com/contest/1799/submission/195192191 ( sorry for the bad implementation )

I agree, for me too C is harder than D. For me it just came down to considering three cases:

1. Every frequency is even. Then the answer is just 'abccba'.

2. Suppose that the smallest symbol whose frequency is odd is symbol 'f'. Then if all symbols greater than 'f 'are the same, then the answer is 'abcfffggfgggfffcba'.

3. Otherwise, the answer is 'abcfffghijkffffcba'.

Why? It’s straight forward to get a 2 which is true if you have more than 3 different elements. Otherwise just check if you can make a 2. Whats so good about it

When I started testing, C and D1 were not in the problemset and the order of other problems was A — B — F — E — D2 — G — H. Of course the standing page was funny, and current problemset is even much improvement. This is why I felt lol after testing.

I agree that C was very troublesome to deal with (and I personally had multiple incorrect implementations of a correct idea). I think that kind of messy problem might appear in any kind of round and that it might just be smarter to skip it directly (tbh, after reading the statement, I could guess that I would most likely spend inf time on it).

Yes, this is one of the correct solutions.

Skip the problem.

I also wasted 2 hr solving this, and after that when I saw D1 it was direct dp but there was no time to complete the code.......

I agree with every word you said.

If there's exists some $$$i,j$$$ ($$$i \ne j) \quad a_i = 1 , a_j \ne 1$$$ then we cannot make all the elements equal. because for $$$a_i = 1$$$ you cannot change it. and if you attempt to make the other elements 1 then you are failed also because after making $$$n-1$$$ elements to 1 then you cannot make the last one same because it is now max of the array.

But if you have an array of greater than 1 integers, then you can make all of elements 2 in at most $$$30n$$$ operation. the idea is whenever you found two distinct elements you can divide greater integer by smaller integer. so in this way you make array elements smaller and smaller till you make all elements equal to 2.

Worst case scenario you have to divide 10^9 by 2. then it wouldn't take more than 30 operations (because $$$log(10^9) \lt 30$$$)

1. If you've got 1, array must contain 1s only: otherwise you can't make array maximum equal to 1.
2. If there is no 1, let's divide non-minimal elements by minimal element. This will eventually make all numbers equal, as this algorithm does not create 1 and the array decreases on each step.

No, it's just your solution have big hidden constant as you're using too much memory. Try to do it in $$$O(NK)$$$ time with linear memory.

Sol:

Let's construct the optimal string in two parts (a left side and a right side which are respectively a prefix and suffix of the final string)

In the first step we will keep the following invariant: left is the same string as right

We consider the chars in lexicographical order

While the current char occurs an even number of times it is clearly optimal to split it evenly on both sides (it is easy to get a contradiction as if you place more a to the left, then you would put some, say, b at the symmetrical position in the right side and you could get better by putting an a instead).

Now we are either done, either facing a char C having odd count.

As earlier, it is optimal to split the even part of the char equally on both sides (so if you have 5 a you will put aa on each side).

(You can do a proof by contradiction exactly like earlier)

There is now only one occurence of C

Consider two cases

1: you have one or less remaining chars greater than c

2: you have more than one remaining chars greater than c

Case 1:

if C is the last char, you just put C as it's the only thing you can do

else, it is basically analog to solving the case abbbb...bb and in this case the best answer is (by casework) to put a in the middle of the group of b

Case 2:

There are more chars so its similar to solving abbccdd... (you can compress adjacent equals chars to make them blocks)

Here we can wlog assume that reading the string starting from the left side will give the lexicographical smallest string.

Assume you don't place a right now, it will be suboptimal as you would add some b on the left and right side (if you add anything greater the string becomes >) and now if you add a on the left side, you can just swap a with the b to get something <= (same on the right side by symmetry).

So you will add some c on both sides but what can make a better answer.

So you should add a to the left. Now it is clearly optimal to sort the remaining chars.

Indeed: we know that reading from the left side gives something strictly smaller than reading from the right side so we are now only interested in making the right as small as possible

Code: 195196709

So do we need to tabulate the solution ?

There's no need for 2D array in D1.

I agree. Lost more than 450 points because of memory.........

You can use the "hidden parameter" technique to only store the current layer of DP, reducing the memory consumption to O(n).

But it's completely trivial ._.