I hope any problemsetter asked me too for testing. I wanna try testing a round so bad xd

X: doubt. UPD: I really enjoyed the contest. Problems were great. My performance was worse than usual but still I really liked the contest. Big thanks to the problem setters!

Don't trust appearances.

Don't cover the book by its judge

cursed comment

Confused Unga Bunga... XD

agree+1

hypocrite? the problems were very nice and I wholeheartedly recommend the participation?

As...

Me too. I hope we both do it!

Makise Kurisuu <3

Is it funny in any meaning?

"As a tester, I wish to solve three problems"

As a participant, I think you are sus

C1/C2 instead of just C

by not doing it lol

too hard

they can't tell the difficulty with confidence if they can't solve it though

I would like to publicly apologize for not helping the authors well enough in this matter.

I agree.

two pointer

same here...found C1 easier than B

Same, I barely solved it in the last minutes, I think it was harder than $$$C$$$

B was literally on GFG. (Link here)

If this can generate the array $$$b$$$ and it fits the conditions, answer is $$$\text{yes}$$$. Otherwise answer is $$$\text{no}$$$.

Couldn't find the same approach in the same room, though.

For me, it was the opposite, B in 15 min cannot solve C1. How did you solve C1.

Same :/

I think C2 is easier than B

Let $$$b_x = x-a_x$$$, we also set $$$b_0=0$$$ and $$$b_{n+1}=n$$$ for convinience. Then if the sequence of prefix maximas is $$$b_{x_1}, b_{x_2},\ldots,b_{x_k}$$$. The answer is $$$(\sum\limits_{i=1}^{k-1} x_{i+1} \cdot (b_{x_{i+1}} - b_{x_i})) - \frac{n(n+1)}{2}$$$.

You can probably modify this blog to AC (if it works, we don't require updates to be independent). But I just bashed some stupid case work similar to prefix maximums from ICPC Gwalior-Pune Regionals 2021.

define end[i] = longest position j such that a[i..j] is good

then do casework on updates (binary search is needed)

you can try on paper how array end changes between updates

also note that update that increases a[i] should be considered differently from update that decreases it

i finished the code just now, not sure if my idea is correct

I made a vector called start, where start[i] indicates the lowest index that you can start a good subarray from and be able to include a[i] in the subarray. Then $$$start[i] = \max (start[i - 1], i - a_i + 1)$$$. This might look familiar if you solved C1 (though you may not have used a separate array for it).

Before making any changes, the desired answer would be $$$\frac{n(n + 1)}{2} - \sum (start[i] - 1) = \frac{n(n + 1)}{2} + n - \sum start[i]$$$.

Note that $$$start[i]$$$ is basically the largest value of $$$j - a_j + 1$$$ for $$$j \leq i$$$. We can prepare another vector, second, where $$$second[i]$$$ is the second largest value of $$$j - a_j + 1$$$ for $$$j \leq i$$$. Note that $$$second[i]$$$ can be equal to $$$start[i]$$$ if there are two (or more) indices with the same maximum $$$j - a_j + 1$$$ value.

We can prepare prefix sum arrays for both $$$start$$$ and $$$second$$$. You can probably figure out the rest from there, but if not, here are some details:

• if changing $$$a_p$$$ to $$$x$$$ does not change $$$start[p]$$$, then the answer doesn't change, and you can just print $$$\frac{n(n + 1)}{2} + n - \sum start[i]$$$.

• if changing $$$a_p$$$ to $$$x$$$ would cause $$$start[p]$$$ to increase to $$$newstartp$$$, then use binary search to find the next index $$$j$$$ in which $$$start[j] \geq newstartp$$$. So we use $$$newstartp$$$ for the range $$$[p, j)$$$ and use the original $$$start$$$ values for all other elements, which we can efficiently calculate totals using the prefix sums.

• if changing $$$a_p$$$ to $$$x$$$ would cause $$$start[p]$$$ to decrease to $$$newstartp$$$, then use binary search to find the next index $$$j$$$ in which $$$second[j] \geq newstartp$$$ (this might be $$$p$$$ itself) and another binary search to find the next index $$$k$$$ in which $$$second[k] \geq start[p]$$$ (original $$$start[p]$$$). Then we use $$$newstartp$$$ for the range $$$[p, j)$$$ and the $$$second$$$ values for $$$[j, k)$$$ and the original $$$start$$$ values for all other elements, again, all calculated efficiently using prefix sums.

My Submission: 175446833

Let's f(i) is the left-most index you can take when i is the right-most one, then f(i) >= f(i + 1).

Then, yeah, as we know, two pointers.

I didn't find it that hard

A lot of the hacked solves look similar and weirdly bad (to my brick-covered eyes, at least)... or they're good but messed up the indexing/bounds in some way that I'm not noticing with quick glances.

Hypothetically: weak pretests as anti-cheat would be an interesting and terrible choice...?

how do you know it's cheating ?

Yes, I did it that way. Waiting to submit my solution though. BTW how to use segment tree for this? I did not find any way to update.

Yes, by using prefix sums. My submission: 175446833

I explained my approach in another comment above, because the code might be difficult to read otherwise.

Actually I think everyone had really good chances at solving Problem D, because if you have found the idea, the solution is pretty simple.

Biggest mistake -> did not see that the changes were temporary in C2

b2 should be divisible by a1 and a2, so it is divisible by lcm(a1,a2). gcd(b1,b2)=a1, hence b1=a1. Proceeding similarly, you can have bi divisible by lcm(ai-1,ai), and bn+1 = an. For any bi not in [1,n+1], we have multiples of some number as possible inputs. You can convince yourself that taking the smallest one(that is the lcm itself) is most likely to produce a solution(taking a multiple, you only decrease the chances of gcd being whats specified). With this, you have a possible sequence bi. Just check its sanity and answer "YES" and "NO" accordingly. I hope this answers it.

I solved it by checking whether gcd(prev, after) divides curr or not.

If they do not for at least one number in A, then ans is No. Otherwise, yes.

I don't think D is too hard, tbh. Once you realize that it's redundant for the cyclic shifts to leave any bits unchanged, i.e., there is always an optimal answer where the cyclic shift will flip all bits of the subsequence or there is no answer, then I think the solution becomes really obvious after that.

I agree that it's easier than C2, but there isn't much that could be done about that, since it wouldn't make sense to have it before C1 (since it's still harder than C1) nor should C1 and C2 be separated. I suppose it may have helped to give C2 a slightly higher score than D, to encourage participants to check D before trying C2.

Since $$$a_2 = gcd(b_2, b_3)$$$, both $$$b_2$$$ and $$$b_3$$$ has to be divisible by $$$a_2$$$
Similarly both $$$b_3$$$ and $$$b_4$$$ has to be divisible by $$$a_3$$$
So the common element which has to be divisible by both $$$a_2$$$ and $$$a_3$$$ is $$$b_3$$$
That's why $$$b_3 = lcm(a_2, a_3)$$$
Now that you have $$$b_3$$$ just check if $$$gcd(b_2, b_3)$$$ is equal to $$$a_2$$$ or not. If it is not then answer is "no". Otherwise continue till $$$n$$$

What Your Logic for Problem B and C1

I would've probably got 2 wrong submissions if not for it, and rightly so.

Any hints, please? ^-^

You are so offensive, but I like it.

Well, they certainly didn't copy problem E, given that they got first solve on that problem. (3 minutes before 2nd solve and 23 minutes before 3rd solve!) Though it does seem a bit ridiculously fast, since unlike wildfire032, the 2nd and 3rd solves did not solve A and B first and they are very high ranked.

You are so offensive, but I like it.

Take a look at Ticket 16278 from CF Stress for a counter example.

Why downvoting this?

Simply divide the array in two subsequences, as per your choice

I don't think you can just choose any subsequence pair. Even and odd index works correctly, and is also what I used, because both bits in the same position of the two subsequences appear before all bits in later positions. So for each mismatching position, you can alternate between turning the 0 into a 1 and turning the 1 into a 0. Applying the cyclic shift on a subsequence where the bits alternate (consecutive bits don't match) is equivalent to flipping them all. My submission: 175422432 (note: pz means picking the 0 to add to the cyclic shift)

But if you tried to construct the subsequences differently, e.g., first half and second half, then it doesn't work. For example, consider 00001111. If you tried to match first half with second half, then there must be at least one half with 2+ indices being chosen for flipping, but then the shifting subsequence would have consecutive elements of the same bit, so the cyclic shift would NOT be equivalent to bit flipping.

How were you able to think of this construction?

I wonder too (cry

Read Problem again , for every new subarray of any size indexing will be according to new one not according to Initial Array .like one of subaarray [1,4,3] of size three is valid as per question.Hope you understand.