One round ago I was pupil)

coaches don't play

Bcoz now a Specialist was once a Candidate master and probably future master

As a tester, wish me luck! ..... (●'◡'●)

Pa_sha [user:Vladosiya][user:MikeMirzayanov] Why are people with a popular history of cheating like him are allowed to test? He will leak the problems even before the contest is conducted!

my friend told me once that kids started using codeforces , I didn't believe him at first , but now I do

it will soon be in div1/2 too

You have to be master or a writer in the past, as blog with rules say

The comment below literally has +18. STOP TESTERISM!

MikeMirzayanov attention plz there are lots of cheaters

and I did it

ahh it seems i got it, but i just couldnt implement it. good job

no reduction in points in error/wrong in 1st testcase

It is not increasing it, the answer for the third testcase is a fraction so it is the $$$numerator \cdot modular inverse(denominator) (mod 10^{9} + 7)$$$.

$$$\big(a\cdot b^{-1}\big)\bmod p = \big(a\cdot b^{p-2}\big)\bmod p$$$ for prime $$$p$$$.

You can check this blog about modular arifmetic. Particulary, about modular division, which is pretty common.

So true. I don't know what is the issue with my c++ code, I handled all the overflows and yet it keeps giving me WA Test 4

FOR REAL I had submitted two C solutions which got Wrong Answer at test 5. At that point just gave up and used my beloved Python.

I just hacked it

answer = $$$\sum_{i = 1}^{n} \sum_{j = i + 1}^{n} \frac{2 \cdot a_i \cdot a_j}{n \cdot (n - 1)}$$$

modulo $$$10^9 + 7$$$ of course.

There are $$$\frac{n(n - 1)}{2}$$$ possible pairs. Since we want to obtain the expected value, we know that we want to multiply the product of each pair by its probability. Clearly, each pair $$$(a_i, a_j)\, /\, i \lt j$$$ has the same probability of occurring. This means that the probability of each pair is $$$p = \frac{1}{\frac{n(n - 1)}{2}}$$$. Now then, we can see that the final result will have the form $$$pa_1a_2 + pa_1a_3 + ...$$$. So, we can extract the $$$p$$$s and obtain $$$p(a_1a_2 + a_1a_3 + ...)$$$. Here, we know what $$$Q = p^{-1}$$$. At this stage, you must choose a method to calculate $$$Q^{-1} \mod 10^9 + 7$$$. This can be achieved by any number of methods using the modular multiplicative inverse. The value obtained from this we will multiply with the calculated value of the numerator $$$P$$$ to obtain the final result.

On the other hand, we must find a way to efficiently calculate $$$a_1a_2 + a_1a_3 + ...$$$. This can be done by simply calculating $$$s = \sum_{j = 1}^{i - 1}$$$ and adding $$$sa_i$$$ to the numerator for each $$$2 \leq i \leq n$$$.

Hope this helps.

PS: Please do be careful with the modulos.

Both (.-__-. and fisher199) your comments were helpful, and I have solved that problem. Thank you.

Why are you using Chat-GPT during the contest? What is even the point of solving a problem with GPT?

imagine using ChatGPT. using it should be banned because it can sometimes solve template problems regardless of their difficulty.

for n>1, you can set the array to 0, gcd, 2*gcd, 3*gcd, ..., (n-1)*gcd. I believe this will be enough for you to be able to solve it now.

Not quite. Compute gcd, let it be G. Then you can always make the array to be of the form 0, G, 2G, 3G ... (n - 1)G. Then finding the kth MEX is O(N).

Yea but I dont know how to inverse modulo if not im spec by now

Iterate over each letter to remove and maintain a count of each character at even and odd positions. Notice that the removal of a character will flip the parities of indices in front of it.

I just iterated from 1 to n and checked if i delete the current element in string , how many operations would i need to do in order to obtain alternating string and stored minimum of all those operations . For doing it in time limit , I stored the count of occurence of alphabets at odd and even positions at each index.

You can check this out , there may be better approaches but this came to me

https://mirror.codeforces.com/contest/2008/submission/279203992

To calculate the number of operations required for an arbitrary string s, you need to find the maximum count of a character at odd indices and another count for even indices, then subtract both from the size of the string, because that's how many characters you need to change. Also, notice how removing a character at some index i flips the parity of all characters in front. Moreover, if you remove a character at index i and flip the parity of a character at index i+1, then that character will have the same parity for the removals of characters at indices < i. Knowing this, going down from i=n while i>=0 you only need to update the counts related to the characters at index i and i+1, where s[i] is the removed character

We will try removing ith character for all $$$ i $$$ such that $$$ 1 \lt = i \lt = n $$$. with some precomputation, at each $$$ i $$$ we can calculate the most frequent character at even positions and odd positions in $$$ pref_{0\cdot\cdot\cdot i-1} $$$. You can do the same for $$$suff_{i+1 \cdot\cdot\cdot n} $$$. During the precomputation you can also store the characters which occur the most in prefixes and suffixes respectively. Then it is easy to observe that whatever balanced string we'll have will contain either of the 4 characters we just stored (most frequent even from prefix, most frequent odd from suffix) and (most frequent odd from prefix, most frequent even from suffix). (After writing some cases you can observe that after the removal $$$ith$$$ character, the parities of suffix flip). and that's it. you can check my submission

I couldn't get AC during the contest but I just had to add ans = 1e8. feeling super sad rn :(

upd: got it just it just an extra equal to symbol

Probably this line:

for(int i = 0; i < n - 1; i++) sum += ( a[i] * prefixSum[i + 1] );

That's a very standard trick. It even appeared in a recent CF Problem : Med-imize.

I added more details here

I precalculated the answer for each x by binary search. Since $$$a_i \leq n$$$, each x splits the numbers int $$$\frac{n}{x}$$$ patterns of $$$0, 1, 2, ..., x - 1, x$$$, I used prefix sums to avoid iterating over that.

My submission: 279218027

Time complexity: $$$O(n log^2{n})$$$

congrats! Long way to go!

Yes. We will try to do it as soon as possible

I made the same error as std in G :D

The hard part about problem C is proving the simplest solution runs without the risk of TLE. Which I think not many people did.

you're a cheater, bro, rating matters more bro, no one cares about your self righteeousness get answer from chat gpt or telegram oa group to get good rating, and placement