As a participant, I also solved strictly fewer than 15 problems during testing.

deleted, cause got downvoted for no reason ;(

off topic, but the contest you made was fire!

As a random guy, i dont know what to say

Nice problems! I recommend the Codeforces community members who haven't participated yet to give it a try.

That's for sure, considering you solved 15 problems for 2 sets of 6 problems (which ig will overlap, giving total of ~10 unique problems in a set). So even in the best case it's only $$$\frac{2}{3}$$$ similarity to your experience :)

Interactive problem, oh yes, free rating

There is no score distribution and thank God there isn't any because the score distribution ones are the hardest ones

Why Downvotes?

are u participant of ioi?

Congratulations bro! I also got a rank increase after this contest :D

no

Yes

Oh no I know nothing about generating function please no

Also I hope interactive is not 1A/2C

Ok,carry on

you're joking right? D is so stupid

I had same idea. But notice: you can better. Just use format '((' + index_to_check So, you can check 8 indexes by query. Length of query is 3 * (1 + 2 + 4 + ... + 128) < 1000

go from right to left and pick choose greedily. (try to prove it).

you solve from value 1~N

O(N^2) is acceptable

don't get discouraged, sometimes I also only solve 2 probs in div2.

Basically, you store the indices for every number 1..n. Then, for those indices, you can count the number of inversions(regardless of future choices), if you chose either i or 2*n — i. For every index, I used i or 2n — i, depending on the number of inversions. To count inversions, I used order statistics tree, but I later realized, it could also be done using whole array pass(as the constraints allow it). Sorry, if my explanation is not that clear. You can see the code: 331840665

I also struggled a lot with it. Idea is that if you don't flip number in position, you will add as many inversions as there are bigger numbers before current number. If you flip, you will add only those bigger numbers which are after, because all inversions with numbers that are flipped before and were smaller before flip are considered calculated already, and all numbers which are after and greater will cause +1 inversion (regardless they will be flipped in future or not). So for each position greedily decide to add count of bigger nums before or after this position

My solution was to find an index that I am sure is a '(' and ')' (call the former bra_index, the latter ket_index), this can be done with binary search.

After finding these indices, query the other indices two at a time (call them i and j):

? 8 i ket_index bra_index bra_index ket_index bra_index j

Essentially, it is asking what f("s_i ) ( ( ) ( s_j") is:

• When s_i = '(', s_j = '(', the result would be 2
• When s_i = '(', s_j = ')', the result would be 4
• When s_i = ')', s_j = ')', the result would be 3
• When s_i = ')', s_j = '(', the result would be 1

so you can identify what those two characters are with one query, and in total it would take less than 1000 / 2 + 2 * log(1000) < 550 queries.

And actually by making the template 's_i ) ( ( ) ( s_j' longer you can identify 6 characters at a time! I think this is the solution to E2 (probably).

I'm pretty sure dp[l][r][center][increments] should work?

It represents the number of ways you can fill [l, r] where [center] is the first element that gets painted black in the range, and it has been incremented [increments] times by stuff outside of the range. To transition, you just iterate on the next element to pick from [l, r] (resulting in the range getting split into 2) and [increments] is at most like 12 or something, so I think it might run in time (?)

I couldn't properly implement this in ~30mins though :((

(edit: I don't think this works 🤣)

I failed with one of the samples but that sounded good to me:

• first of all, any written number is something small like 12, because from each side you can't place more than 6 guys (first placed on the left blocks all to the left of him and half of the segment between him and target).
• then you notice that when you put first element, it separates problem into two unused blocks to the left and right of him.
• each block can't push values outside of it except it's two sides.
• So you do $$$dp[l][r][push_A][push_B]$$$, where you solve on subsegment and see how much it can push for bigger problems.
• Now you take some intermediate $$$l \le i \le r$$$ and see how to get $$$a_i$$$ out of left and right blocks sub-pushes:

• Based on the block you know that one of push-values will increment by one

If u look at inversions as value (1, > 1) + (2, > 2) ..

u can see relation between (i, > i) pairs is either i is below them or above them.

I thought of it differently. Consider the number 1 in the permutation -- if I keep it as it is it will always form an inversion with all digits to the left of it but no inversion with any digit to the right of it, and if I flip it then it will be vice versa.

So, I can greedily choose what to do with 1. Now that all inversions including 1 are taken care of, we can effectively remove it from the array..and now 2 becomes the new 1 and so on..

I thought like this

Say u move from right to left and at some index i, u see that the no of numbers bigger than a[i] on the left is more than the no of numbers bigger than 2*n-a[i] on the left, now changing a[i] to 2*n-a[i] is definitely better

But what about the numbers in the right -> if those were smaller then those are still smaller so no change else let's say they were smaller but then they were also changed by 2*n-itself so those are now bigger but now even after doing 2*n-a[i] to index i, those number will still remain bigger hence no change again.

Edit: ok i missed the case where the right number is bigger but then it was made 2*n-itself

See my comment above. You can prove this by showing that as the number increases, whether you choose i or 2n-i has NO effect on your previous selections. (1,6),(2,5),(3,4) if you choose 1, it will be the smallest value in the array. If you choose 6 it will be the largest value in the array. This means you only need to consider the indices of the elements with a larger N, because your choice has no effect on previous selections.

Actually, you can iterate through the array in arbitrary order and it can be easily proven.

fr D was just guessforces. so hard to prove why it works

F STD