I wish you get green.

Are interesting and original segment tree problems ok?

Bruh NOOOOOO. This is bad :(

Why? :(

That was really so

I didn't know envy was a tester lol

This is the problem set that was originally intended for Go Study Round 1. It's possible that the Go Study round could still happen in the future with a different problemset, but I don't know anything about it.

It clashes with ABC 244 not ARC 137

Timings of CF round will most probably not be changed as it is based on Technocup finals.

At 11 o'clock Moscow time, as it was written in the announcement, the Russian Olympiad for schoolchildren Technocup starts. Obviously, the round based on this Olympiad should not start much later, because otherwise the participants will have time to tell all the tasks and their solutions

yes, 8 problems, time should be 3 hours!

Because it's SpeedForces XD

I'm glad to see that you're glad to see this problem has been fixed.

Lemme guess, you're gonna choose this round.

such orzness

It means it will be rated for both div1 and div2 and questions could be expected to have difficulty accordingly. Like generally, these 2 are held separately. To get a better idea go through other div1+div2 rounds' questions. All the best btw.. :)

plant trees

plant trees

Thank you kind sir

Score(B+C) == Score(D)

rated.

It doesn 't say whether the competition will be rated or not ?

You guys can solve C????

Store all the values in the array in a map. Find the sum and use recursion to see if you can construct the number backwards.

Keep dividing the biggest piece of the cake if it exists delete it if not then it should be bigger than the biggest number in array a because if the biggest piece you have right now is smaller than the biggest piece in array a then you can't achieve that number

It should be $$$O(n2^n)$$$, but I'm still debugging my code due to some annoying border cases.

It can be solved with classic suffix array construction. If you sort prefixes of length $$$2^k$$$ for every $$$j$$$, then

Thus, you can compare prefixes of length $$$2^{k+1}$$$ by comparing pairs of prefixes of length $$$2^k$$$.

I want to know this too

My approach is as follow:

Let $$$b_i=a_{i+1}-a_{i}$$$ for $$$1\le i<n$$$

If final $$$|b_i|> \sqrt n$$$,there will be less than $$$\sqrt n$$$ elements not being operated. Calculate for every $$$i$$$ with brute force is okay.

Otherwise we have $$$|b_i|\le \sqrt n$$$ we can calculate the most remaining element for every $$$b\in[-\sqrt n,\sqrt n]$$$. We can classify every $$$a_i$$$ with $$$a_i-(i-1)b$$$.

Either $$$|\text{difference of AP}| \lt \sqrt{a_{max}}$$$ or $$$len(AP) \lt \sqrt{a_{max}}$$$.

We can check for all possible differences in the first case in $$$O(n \sqrt {n})$$$

In the second case realize that for a difference $$$d$$$, the difference between two terms at positions $$$i \lt j$$$ must be $$$(j - i) \cdot d$$$. Since $$$|d| \gt \sqrt{a_{max}}$$$, this will exceed $$$a_max$$$ in at most $$$\sqrt{a_{max}}$$$ steps.

Unfortunately I didn't realize that the initial statement directly gives you the way to solve the second part during contest T_T.

You need to find maximum sub-sequence $$$i_1, \dots, i_m$$$ such that for each $$$k$$$ in the sub-sequence

where $$$b$$$ and $$$c$$$ are some constants. If $$$i$$$ and $$$j$$$ both belong to the sub-sequence, then

But $$$|a_i - a_j| \leq 10^5$$$, so either $$$|b|$$$ or $$$|i-j|$$$ is less than $$$\sqrt{10^5}$$$.

So, you check all $$$b$$$ that are smaller than $$$\sqrt{10^5}$$$ and also all sub-sequences that their width is at most $$$\sqrt{10^5}$$$.

I think we both tried prime factorisation. Apparently it isn't the intended solution

How do you say this is a great problemset when you haven't even participated in it? Do you have an alt account?!

This is actually $$$O(26 * n)$$$ — it traverses the string only once for each letter of the alphabet

Surprised to see multisets works. I thought we must use maps.

$$$O(c + log(n))$$$, see complexity section of these docs.

With the grace of cpp20 now we get a new function known as contains(x), which can be used like s.contains(x), as the name suggests it checks if the data-structure contains the value x or not. The great fact about this is that its just log(n) and plus is more good suiting name

It's not quite clear what's going on, but I'm going to guess that given a '1 1 2' you do not know if it combines to 2 2 or to 1 3.

Imagine when you have 200000 numbers each 10^9, and you have to break everything into 1 before returning NO

Complexity is O(2 * sum * logn)

Solve function goes like that

Sum + Sum / 2 + Sum / 4 + .... + Sum / Sum = Sum * (1 + 1/2 + 1/4 + ...) = 2 * Sum

For me, $$$O(n \sqrt n)$$$ with unordered_map got TL, but just sorting and solving in $$$O(n \sqrt n \log n)$$$ somehow passes...

well.. I just failed system tests.. I should have done more constant optimization xD

upd: my solution got rejudged and got accepted. Is that a new feature?

Dear contestant,

Please don't worry if you had to make some formulas shorter in order to pass a time limit that was set as a triple of our solution's running time. In a programming competition, the way you express your ideas in code actually matters. Apologies if this does not fit your view.

Thanks for the feedback,

A mere alt account.

I agree with your perspective that requiring constant factor optimization does not make the contest any more interesting. We did not want any solution with correct complexity to get TLE (at least I didn't, I cannot speak for the other preparers). In this case, we made the constraints of E more lenient several times during testing, until the official solution (which uses hashmaps) ran in 1700ms -- at that point we thought the time constraints were reasonable.

In the majority of cases where contestants complain about problems requiring constant factor optimization, it's not because the authors intentionally wanted to require it, but rather because there was a known brute force solution that could easily pass if the constraints were more lenient, or because changing the constraints would give away the intended complexity, or because increasing the TL would lead to queuing during the round.

In this case, in hindsight, I would say we perhaps should have lowered the constraint on $$$n$$$, but I'm not 100% sure about it. Such a change would have likely allowed a few highly optimized $$$O(n^2)$$$ solutions to pass, and it's not clear whether that's a "lesser evil" than causing some solutions with poor constant factor to get TLE.

Instead of Priority Queue I was wondering why not normal queue would work. I took some test cases and dry run it, luckily I found that normal queue would work. Anyways thanks for your intuition, it helped me a lot.

What is your original idea?

Due to AtCoder ABC today?

This happens to someone every contest. The CF grading servers have some variance in time measurements, and there is nothing we can do about it.

If you submit a new solution after passing all the pretests, the earlier ones will be skipped.

you can limit the times of split operation, the times can't be greater than N.

The pieces in your piecewise algorithm have different constant factors.

I use 100 to pass it...

I can't, it says "you are not allowed to view the req page"

Nope, I think they are editing it. It worked yesterday.

In case answer is "NO" loop can run long before it breaks. If origi.begin() is 1 and x is 1e9 it can create near 2^30 elements for split multiset when the x is invalid.