If you create a blog post and save it as a draft, when you publish it, it is labeled with the creation time instead of the publish time for some reason. But it still takes a huge amount of foresight to create a blog post for a contest 2 years in the future...

Does it mean, I have to wait approximately half year more for my contest?)

It might have been a clone of this announcement before it got edited and published, since it is also a contest prepared by the same author two years ago.

"This post was published a long time ago. Please refrain from commenting unless you have a really reasonable cause to leave a comment. Necroposting is discouraged by the community." The reasonable cause is that the contest is starting in 4h :)

This would be great.

I agree

LOL

More of them were probably Div2 when they tested but their rankings have gone up in 2 years..

I feel the same way, maybe I should invite some testers with lower ratings.

but the difficulty balance/overall was amazing for div2 round nonetheless, thanks!

I didn't notice that until I see this comment

What made you come to this conclusion?

hahaha

We will update soon.

and you did :)

tru

Yes, i also wanna know. I think it is some dp that i'm just too stupid for. My greedy doesn't worked out

I think it's easier. but obviously, the problems were interesting with perfect difficulty.

let the first element of array has parity p . now check for the last element whose parity is p (let its position be j) .now for all 'i' from 1 to j-1 elements whose parity of element is p, apply one operation on i and j since both has same parity arr[i]+arr[j] will definitely be even i.e a[i]=a[j]

now for all i from 2 to n whose parity is not equal to p apply one operation on 1 and i since arr[1] and arr[i] are of different parity their sum will be odd i.e arr[i]=arr[1]

after this every element in array becomes equal.

I can describe my algo:

1. Check weather first element even or not

(if it is even)

1. Find last occurrence of even element

2. Now go through the whole array from left to right and if we meet even number do (i, lastEvenInd) to make them equal. If we meet odd number do (1, i) to make it equal to the first element

Pretty the same if first one is odd, but all "odd" replaced with "even" and vice versa

Make a[1] and a[n] equal. For i = 2 to n — 1, if a[i] + a[1] is odd, then the operation is (1,i), otherwise (i,n). After this we can achieve an array with the same number using n — 1 operations.

How to do that C?

test case:

1
4
4 3 1 2

your answer :

5
1 2
1 3
3 4
2 3
1 2

5 > 4

Here is an answer:

3
1 4
1 2
1 3

in D1,5 <= n <= 3000

n will be greater than 4

min array length is 5

Not valid, since $$$n \geq 5$$$. I was worried about this case too, but they always made sure it's possible to deal with a consecutive mismatch through two $$$y$$$-swaps.

It's an invalid test case.

N>=5, Mentioned in the constraints.

Thanks for pointing that out! I totally missed this case. (So if not for the restriction on $$$N$$$ I would have failed probably pretest but for sure system test. Note: Always think about small cases! The only special case I thought about was with $$$N=2$$$, which would have needed a seperate consideration too.)

B: One of $$$x$$$ or $$$y$$$ must be 0, because the loser of the first round wins 0. WLOG let $$$x$$$ be the non-zero value. Then everyone who won at least once would win exactly $$$x$$$ times, so $$$n - 1$$$ must be divisible by $$$x$$$. Now it's easy to make somebody win $$$x$$$ times and then let the next challenger be the winner for $$$x$$$ rounds and so on (it's simpler if 2 wins at first, so the winners are all gonna have IDs of the form $$$2 + ix$$$).

C: If the first value is even, then apply the operation on each even with the last even, to make all evens equal to the last even. Then apply the operation on each odd with the very first value (even) to make all odds equal to the first even (which is now equal to all other evens). Similarly, if the first value is odd, then apply the operation on each odd with the last odd, to make all odds equal to last odd. Then apply the operation on each even with the very first value (odd) to make all evens equal to the first odd (which is now equal to all other odds).

Sorry for that. The constraint changed just before the contest start, and it seems to have taken some time to reflect on the problem page.

Can you explain your O(N) approach?

My misreading was more severe. I thought the operation was a[i] = a[i] % k, a[j] = a[j] % k and then swap a[i], a[j]. I have no idea how I could read like that.

misread C and didnt note m had to be less than n and wasted 30 mins coming up with a soln then realized after seeing pretest 1 fail and got correct soln 10 mins after contest ;)

i should really get better at reading in contest nerves

I don't think they were easier, you just did a great job

then why did my approach — 172725963 — get a WA2? what cases did I miss?

I think that this does not work in this case:

This is not correct. It is not necessary that you always match consecutive ones. Consider all non-matching indices to be $$$[1,3,4,7]$$$. You might match 4 with 7 and 1 with 3(cost = $$$min(y,3x) + min(y,2x)$$$). But matching 1 with 7 and 3 with 4 could be better($$$min(y,6x) + x$$$). This may happen when $$$y = 2x$$$ for example.

This is incorrect. Imagine that the indices where a and b are different are 1, 3, 4, 7, x = 1 and y = 2. Your solution would match 4, 7 and 1, 3 for a total cost of 4. But the optimal cost is 3, from matching 3, 4 and 1, 7.

That should not work. Do you have a submission to try and hack? X_XX_X with $$$y=3$$$ and $$$x=2$$$ should hack it.

Consider case:

12 1 6

100001100001

000000000000

According to you greey algo,the strategy is:

-change the 7-th and 12-th bit costing 5;

-change the 1-th and 6-th bit costing 5.

The total cost is 5+5=10.

But the optimal strategy is:

-change the 1-th and 12-th bit costing 6;

-change the 7-th and 6-th bit costing 1;

The total cost is 6+1=7.

Maybe I misunderstand you method,can you explain it?

Greedy doesn't work. Consider the following test-case:

6 2 5
101101
000000

A greedy approach would pair the first two 1s with a cost of 4, and the last two 1s with a cost of 4 as well, for a total cost of 8. However, the optimal choice would be to pair the middle two 1s for a cost of 2, and then the first 1 with the last 1 with a cost of 5, for a total cost of 7.

If your submission was truly accepted, then it could not have followed the greedy approach that you just described (unless the pretests were really bad, but I doubt that's the case, considering how many penalties I observed in D2).

Ok this doesn't work then. I guess it'd have to be DP.

I used GNU C++17 (64) and got Accepted.

cause plyer1 won 0 times then

can you explain your dp?

Count how many indices have mismatches. Each operation flips exactly two bits. If the number of mismatches is odd, then it's impossible to fix all the mismatches, so the answer is -1. Otherwise, there are two cases:

1. The exceptional case to watch out for is when there are exactly two mismatches AND they are on adjacent bit positions. In this case, you can pair them directly for a cost of $$$x$$$, or you can pair each of them with some other distant bit position for a cost of $$$2y$$$ (note that this distant bit position flips twice, so it reverts to its original value). In this case, we output whichever of $$$x$$$ or $$$2y$$$ is smaller.

2. In all other cases, it's always possible to resolve the mismatches using $$$y$$$ operations. If we have only two mismatches, then they're not next to each other (since that's covered by Case 1), so you can just use a $$$y$$$ operation. If there are more than two mismatches, you can divide the number of mismatches by 2, and pair indices from the first half with indices from the second half, so the paired indices are never adjacent and the cost is always $$$y$$$. Here, the answer is just (number of mismatches)/2 * y. This is always optimal because $$$x \geq y$$$.

It's more like a second B problem

yes,same feeling .I checked if its a Div 2 or Div 4 contest lol

Thanks for enjoying! Actually, some testers gave O(n) solution of D2 already, but we decided to accept O(n^2) solution for difficulty balance.

It's rated, but it takes some time for rating changes to apply, since there is system testing after the contest (which is already done for this one) and a procedure to find and remove cheaters (which can take quite a while). After that, the rating changes are applied and the contest should be moved to the rated contest list.

There are exceptional scenarios in which a contest that is supposed to be rated becomes unrated (such as when a problemsetter unethically copies a problem directly from another source), but I don't think there were any issues for this particular contest, so it should hopefully be rated. Just be patient...

Until the rating changings will be done it is unrated (it usually takes about 12h-16h)

yes

True. But n is guaranteed to be at least 5. So you can ignore this special case.

I solved this by change the initial DP, like this https://codeforces.net/contest/1733/submission/172778355

and the test date is: 1 6 100 1 111111 000000

Here is a counterexample:

5 3 1
00011
00000

Your algorithm returns 3, but the correct answer is 2. You can simply apply the operation on indices $$$(1, 4)$$$ and then on $$$(1, 5)$$$. Index 1 flips twice, so it reverts to 0, while indices 4 and 5 each flip once and become 0. The cost is $$$2y = 2$$$, which is better than spending $$$x = 3$$$ cost on flipping $$$(4, 5)$$$ directly.