this is about your imagination than, not about physics

it was in statement (and why do you need to know what is it to solve?)

physics? it doesn't need anything from physics to know to solve b

the saddest thing in this is rating is a number that doesn't matter almost anywhere. It is just a number that can (in the past) show you your progress. And doing codeforces not really improve your life. It is just fun to write contests an rating is just the way to compare yourself performance with other or with yourself in the past. So sad people cheating (if you check many top20 participant's codes of last few d2s, they are 100% written by chatgpt). This is some sort of my cry of heart :(

you can do binary search not on the initial array (for example $$$arr$$$), but on $$$arr_i - arr_{i+1}$$$. Firstly sign of this function will be negative, then positive, so you can use binary search

yep, I agree it is hard even for some 2100+ guys, but still solvable. Also I would like to have more 2300+ tasks in div2s, rather then 2700+. But challenging tasks create strong programmers)

Wow, only GM solved this? This is really strange)

It's honestly not very obvious to me why so few people have solved problem E. I'm not saying this is a simple task, I haven't solved it either (I really don't like this kind of task), but judging by the analysis, this is a common task a little more complicated than d2E, definitely not deserving of the complexity of 3000

how to solve E?

me too, but why them work?

prefsums + binary search. you can check my sol https://codeforces.me/contest/2026/submission/288582700

how to solve E?

thanks!

wow, thats cool! can you plz explain why it works?

how to solve d1C?

Can you send me a link to website you are talking about?

If rating doesn't matter for you then why you care about cheaters?

5 points can be gained easily on next round unless you are gm (btw never saw gm who said cheating is a very big problem). And also it shows that not really big amount of people cheat on contests usually. And as I see on your comment below, you suggest to use spoofers. This spoofers will basically remove all fun from cp but for what? For 5 extra rating points?

Firstly, I don't blame people for beeing low rated. I'm just tired of 998244353 same blogs where one grey guy blaming another grey for cheating on div4a.

Secondly, about cheating on div2. Firstly, guys who cheat on problems like div2d are usually smart enough to change code dramatically, so you can't find these cases and chance of false positive cases is high.

Lastly, is 5 points you didn't get because of cheaters is very big problem that worth thousands of posts? I think no

to avoid fake reports, this feature can be implemented for experts+/cms+, like it is for tagging problems now. but here another problem appear, most of cms+ don't affect by cheating and won't report anyone since they don't care about it. so this feature seems useless)

I don't think so. most of these blogs written by newbies/pupils, seems like whining for me (sorry for toxicity, hope I won't get ban because of this comment), so why should we listen to people who prefer posting blogs instead of upsolving and practice?

This system already exists. Antiplagiarism check will ban most of cheaters, and if cheating dramatically impact on one's rating, after this check the one will get underrecieved rating. But I never saw f.e. even +20 points after this check, so I guess problem with cheaters taking away rating is overvalued

Got you, thanks)

I saw this too, but f.e. guys who host next div3 will do it for the first time

agree with you. D was not an easy problem in my opinion, 3k ACs at round with 18k participants seems sus

yes, we need, forgot about it

we can notice that if triangle is correct and $$$(x, y)$$$ is one of point of this triangle, than $$$(x + \frac{d}{2}, y + \frac{d}{2})$$$ also belong to this triangle. now all we need is to check that third point exist.

as was mentioned in comments earlier you need to calculate number of permutations $$$\frac{n+m}{2}$$$ 1 and $$$\frac{n - m}{2}$$$ -1 where doesn't exist prefix with negative sum. How many permutations of 1 and -1 exist? $$$\binom{n}{\frac{n - m}{2}}$$$. But some of them are bad.

Now we need to count bad permutations. Any bad permutation will have prefix with sum -1 (because should exist prefix with negative sum, and every number is either 1 or -1). Let's replace every -1 with 1 and every 1 to -1 in this prefix. What happened? Number of -1 decreased by 1. So number of bad permutations is same as number of permutations with $$$\frac{n+m}{2} - 1$$$ 1 and $$$\frac{n - m}{2}$$$ -1, which is $$$\binom{n}{\frac{n - m}{2} - 1}$$$.

Now we have answer: $$$\binom{n}{\frac{n - m}{2}} - \binom{n}{\frac{n - m}{2} - 1}$$$

you can calculate using same logic as for calculating catalan numbers. I guess it will be something like $$$\binom{n}{\frac{n-m}{2}} - \binom{n}{\frac{n-m}{2} - 1}$$$.

it forces you to "if else if else if else if else if else if else..."

nowadays not many people have sense of humour :(

yes, my submission is n log n

I don't want problems like today's C to get normalized

no, your solution can't be hacked since it is correct) you are searching for all possible LCMs only if LCM of elements is already in array, so it is less then $$$10^9$$$, and obviously all possible LCMs of any subsequence are divisors of global LCM so there are less than $$$\sqrt{10^9}$$$ possible LCMs hence your time complexity is $$$O(n \sqrt{maxA})$$$ (oh I see you find global LCM wrong way and solution already got hacked :(( )

how to solve D?

Why have you been waiting almost a year before posting a blog? Anyway strange actions from 300iq

As a tester, I want to reach pupil after this round

it doesnt matter do cpers leetcode or not (by the way they do). This problem has its editorial published and this is unfair

B is same as https://leetcode.com/problems/minimum-replacements-to-sort-the-array/description/ D is almost same as https://codeforces.me/contest/1513/problem/F how?

even a2oj is old, it still has many very cool problems with useful techniques, especially in 1800+ rated problems

thanks you people_plus_plus for great testcase, now I know that I don't know how to use knapsack properly

Anyone who had wa7 on e1, how did you deal with it?

Can you help me with d2D? I have a bit different approach with dp: dp[i].first = minimal cost of cards to unlock ith card, dp[i].second = max j that jth card can be unlocked using same set of cards as ith card can. I recalc dp with segtree. Why this idea can lead to WA?

https://codeforces.me/contest/1855/submission/216348756

So could you tell your solution?)

Wow I like Constructive and MathForces so much!!!

Thanks to authors! The problemset was very cool

what is testcase 39 for D?

I think you can try do something like this: make 30 arrays, ith position in jth array will be 0/1 depending on jth bit in ith number in intial array, and then make 30 segtrees on each array, and in nodes of trees will be number of ones and zeros. When we have type 1 query, we iterate all bits in x, and if ith bit is 1, we need to invert bits in ith segtree in range [l; r], you can make it with lazy segtree and swaping number of zeros and ones in each node that the segment contains. When we have type 2 query, firstly ans = 0, then we iterate i = 0...30, and if value of ones in segment [l; r] in array responsible for bits on ith position is at least 1, ith bit in ans will be 1, else 0. This work in O(logN * logA) for each query which should get AC. Also, can you provide link to this problem?

yeah, i actually struggled a lot with all problems, even A

bruh c was kinda... interesting

Wow, thanks a lot, pretty cool solution. I was close to it during the round, but wasn't able to write exact solution

Bruh

how to solve D?

What should happen for putting cf on normal servers?

This problem can be easily solved without segtree. For each element lets store how many type 2 was before the last type 1 operation in array S. When we have type 2 query, we increase counter of type 2 operation and put x of this operation in another array. When we have type 1 query we just change pth element in array and update our second massive on pth position with our counter of type 2 queries. Due to the fact, that type 1 query for ith element "kills" all previous type 2 operations for this element, so we only should find a maximum type 2 operation x which is equal to suffix maximum of array of type 2 queries from S[i] and if it is greater than ith element update this element with found maximum