Can you briefly explain, what testers do?

satyam343 orz

Huge fan sir.

As a tester, I confirm!

dramaforces

MikeMirzayanov Can you please tell why no action was taken against him despite him cheating in many contests using alt accounts, and he never apologized or showed remorse for his actions?

CM Pandey

as another participant I don't think this is a wise decision. If you don't attempt harder interactive problems you will not improve at them.

did u said it to me?

Happy birthday! I hope you will enjoy the round :D

Same, the original time just barely didn't collide with my uni, the new one does >:(

A for me was in reading the constrain after 2 hours of trying to casework it

I skipped the sequence having a[i]=1

As long as $$$1$$$ is not one of the chosen elements to be local maximums, then such construction will lead to values $$$\geq n+2$$$ for local maximums and $$$\leq n+1$$$ for other values.

Just choose the case that ignore 1 cuz for example if n=8

a-> ..8 1 7.. p-> ..1 8 2.. res -> ..9 9 9 ..

which not valid solution..

If one of them have better score, then the smaller-score one will have the element '1' inside it. The fact is that every elements will be at least n + 1 after the transformation. So if the we try to maximize the position having the element 1, it couldn't be the local maximum.

Take the one with n or if n is on the edge, take the one that is further away from n.

If you take the one with n, worst case, you have to maximize 1, 2, 3, ... n in order. To 1 let's match up n in ans permutation and to 2 let's match up n — 1 and so on and so on. The minimum sum we can get is n + 1, n + 1, n + 1 ...

To be sure they are the local maximums, the worst case scenario of the neighbors are that they are n — 1, n — 2, n — 3 ... to n — 1 let's match up 1 in our ans permutation, to n — 2 let's match up 2 to n — 3, 3 ... and we see that our neighbors are n, n, n in the worst case. Since n + 1 > n, this works.

There is similar logic when n is on the edge.

Since it is even you can always achieve the optimal number of local maximums in an array. The only thing you need to watch out for is to make element N, a local maximum, and if you do that it can be proven that every element that is supposed to be a local maximum will be >= N+1 and every other element < N+1. Just add 1, 2, 3, 4.... to local mins in increasing order so at worse that would be (N-1)+1, (N-2)+2 ... you can see that each is at most N, and do the reverse for local maxs 1+N, 2+(N-1) ... each is >= N+1.

It was very easy to implement, the observation was the difficult part imo.

Lol I thought I was the only one thinking B was odd. Counting prefixes bit-by-bit should be C at least.

Out of curiosity, what makes D so strange in your opinion?

It feels fairly normal for a CF interactive problem to me.

1.Divide the array into halves based on even and odd index.

1. Find which half has 1 (this is the half without maxes), you could do half that has n is maxes, alse.

2. Sort both halves.

3. Sort sides with peaks. Put n/2 + 1 to n in this half. Smallest number in OG array gets largest number in new array.

4. Same as above with array without peaks but with 1 to n/2.

5. Print

1.Divide the array into halves based on even and odd index.

1. Find which half has 1 (this is the half without maxes), you could do half that has n is maxes, alse.

2. Sort both halves.

3. Sort sides with peaks. Put n/2 + 1 to n in this half. Smallest number in OG array gets largest number in new array.

4. Same as above with array without peaks but with 1 to n/2.

5. Print

You're going in the correct direction.

If you want a (somewhat spoiler-ish) hint:

First I thought D is binary search, but it's actually not. Ad-hoc seems fit to D.

D: Guess that finding the max is important and then think how to use it :P

If you try solving B in O(n log n) the solution is very pretty, no guesses needed.

You can take a look at my solution https://codeforces.me/contest/1973/submission/261355440

You just look for the maximum distance between numbers with the i-th bit on, for every bit.

Every time it's giving 0 as maximum, but surely it will give some positive

I think that you may need to read something after you give an answer, because the interactor in this problem will return 1 or -1 after you give an answer. I also WA in pretest 1 and got confuse but after I figure it out and read one more thing after giving my answer, I passed the pretest.

1. Use n guesses to find largest element in array. Can be done by guessing ? n s*n for s in range n to 1. s is the largest number in array

2. If m exists m must be a multiple of s. m must also be a maximum of s/k, because anything greater cannot exist as m=s/k, divide array into k equal parts if all elements in array are s.

3. Can brute force with those 2 observations. n/k solutions to check. Each solution takes at most k queries.

Find the maximum element $$$mx$$$ in $$$a$$$ by making queries $$$(1,n*n), (1,n*(n-1)),\dots$$$. If you get $$$r=n$$$ on query $$$(1,n*b)$$$ then $$$mx=b$$$.

Now since this maximum element is present in at least one of the $$$k$$$ subarrays, $$$mx$$$ must divide $$$m$$$. Also, if $$$m=b*mx$$$, every subarray must have length at least $$$b$$$. So we only need to check multiples of $$$mx$$$ upto $$$\frac{n}{k}mx$$$. In each candidate for $$$m$$$, just query $$$k$$$ segments starting from position $$$1$$$ and check if these segments cover the array.

This takes $$$n$$$ queries to find $$$mx$$$ and another $$$n$$$ queries to check all values of $$$m$$$.

Happy you liked!