Hello / 你好，Codeforces, ₍^. .^₎⟆

As a tester, I can confirm that nifeshe is goated at queens, and I hope he reaches gm one day

Congratulations satyam343 on his first coordinated round!

Years in the making

As a retired tester, this was my first in a while.

As a python beginner, I'll begin to solve problems with Python in this round. Also thanks to fatalerror's guidance when I was learning it.

P.S: What a good time for Chinese users! God bless the authors and coordinators!

I have never ever seen a blue coordinator

As a tester this round is amazing! All problems are enjoyable to solve and well-prepared.

This contest went through two rounds of testing, so don’t expect any issues.

On a separate note, I want to mention satyam343. He was thoughtful during the testing phase, making polls, suggesting problem corrections, and, most importantly, sending monkey emoji.

As a tester, I tested this round one year ago :cold_face:

Downvote me

Thanks everyone for participating in Codeforces Round 1113 (Div. 2). Although it was initially difficult to understand from the editorial when I first participating in Codeforces contests. However I found that once I got used to it, the explanations felt very easy to understand, accurate, and highly academic.

We should read the hint and solution before reading code (Sorry for my bad English)

hope to be like the last one!!

l really want to achieve 1000 contest rating❤️

Why is this round 22:35 again, I remember it being 19:05 originally (All times are UTC+8)

Now I can't participate because I don't usually go to bed that late :(

Hey everyone, I wanted to know if there are any requirements for proposing problems for Codeforces rounds. I've made a few problems on HackerRank just for fun, and I was wondering if anyone would be willing to review them. I'm a newly promoted Specialist, so I think they're mostly around Div. 4 or April Fools' Contest level. I'd really appreciate any feedback or suggestions. Thanks!

Problem A: 500
Problem B: 1250
Chuckles, we're in danger (:
Hope we(I) will enjoy the WA's...

Love satyam343 round. Love chromate00 as a tester.

till you guys make more contest I'm happy and I think others are happy too.

what is the penalty in div3 ?

Seeing the score distribution, I feel that it would be better to open the entire problemset (which one should generally do); read problems B, C and D altogether and then attempt the one we're most comfortable with first.

Either it is going to be a very tough B or a SpeedForces round!

₍^. .^₎⟆

NOooooooooooooo WHY these contests are always so late for the Chinese user? I cannot join any contests in my summer holiday Because I should get up about 6:50

what, samsoom is the real goat

As a tester, i hope everyone has a good performance

Down_vote me

all the best guys!!!

I will be live post contest discussion stream here

I hope to solve 3 to 4 problems in this contest :-)

I am unable to register now

uh I late registered and it got accepted, but after submitting two problems it seems it says I am not registered anymore? Could someone please resolve, I cannot submit C rn

just a nice round ._.

After a long time non constructive D, and for me that makes B >> D, i got smashed by B, i give up on it

I registered for the contest during extra registration and submitted code for two problems.

Now, with half an hour left, the submit button is no longer there, and if I try submitting using the submit code tab, it is showing "You must be registered."

Good problems, thanks for the round.

I got lucky to guess that we just try any 2 blocks in $$$E$$$ to get a solution, lol.

what's the idea behind C? I try to search everytime max distance between two nums, add to result (r-l+1)^2, if not exist any pairs, add remaining count of nonpair elements. I think the idea not pretty hard.

I don't get how my DP solution got AC on Problem C. It feels wrong to me, but got ac. DP Definition: dp[i] = maximum score achievable on the prefix 0...i. Transitions: If i is the first occurrence of arr[i]: dp[i] = dp[i-1] + 1 If i is the second occurrence of arr[i] (first seen at lst_seen): dp[i] = max(dp[i-1] + 1, dp[lst_seen — 1] + len * len) (where len = i — lst_seen + 1)

My Doubt: I don't get why taking dp[i] = dp[i-1] + 1 here is always valid. Why is dp[i-1] + 1 guaranteed to work even if the interval lst_seen...i is disjoint to the rest of the elements? can anyone explain me this?

nice problems

i spent an hour to code, randomly testing problems B and C, idk but i think this contest is so difficult T-T

ad-hocforces

Why D is D? isn't it like 3 times easier than C, basically just a small case work.

EF is a bit of strange combo. F is rather clear what is happening, solution is obvious (if you ask me, F with n, m >= 2 a proper div2D difficulty, however case handling for single row makes it harder which is always unpleasant. E is just a bit of guessforces problem, as it usually is where you look for examples with such freedom in inputs. Like, not that they don't fit their positions, they are just types of problems for which you don't get enjoyment from getting Accepted...

Really cool C by the way. G also interesting, but don't know how to solve

Thanks for the round! Outlines of my solutions:

A: Alice and Bob should delete the first $$$0$$$ and $$$1$$$, respectively. Proof sketch for Bob; the proof for Alice is analogous: suppose the first $$$1$$$ occurs at position $$$i$$$ and Bob instead deletes a $$$1$$$ at position $$$j$$$. Then, outside of positions $$$i, \cdots, j-1$$$, the resulting string is identical to if he had deleted the $$$1$$$ at position $$$i$$$ instead.

Let $$$t$$$ be the string consisting of characters $$$i+1$$$ through $$$j-1$$$ in the original string; then, deleting position $$$i$$$ results in $$$t$$$ appearing before the $$$1$$$ originally at position $$$j$$$, while deleting $$$j$$$ results in $$$t$$$ appearing after the $$$1$$$ originally at position $$$i$$$. Moving a $$$1$$$ to the right in the string never makes it lexicographically larger, so the string if Bob deletes $$$i$$$ is at least as lexicographically small as if he deletes $$$j$$$.

B: Since the $$$n+m$$$ integers are distinct, we need to use at least two values in $$$a$$$ to produce each value in $$$b$$$, so the answer is no if $$$n \lt 2m.$$$ Then, it is optimal to use the smallest $$$m$$$ and largest $$$m$$$ elements in $$$a$$$ to create $$$b$$$, using the $$$i$$$'th element of the first set and the $$$i$$$'th element of the second to create the $$$i$$$'th element of $$$b$$$. Thus, we can check whether element $$$i$$$ of $$$b$$$ is between the $$$i$$$'th smallest and $$$(m-i-1)$$$'th largest elements of $$$a$$$ for all $$$i$$$; if so, the answer is yes.

C: Consider the set of values for $$$x$$$ that we choose while both copies of $$$x$$$ remain in the array. Note that we cannot choose two values $$$x$$$ and $$$y$$$ if the copies of $$$x$$$ and $$$y$$$ appear in the array in the order $$$x, y, x, y.$$$ Also, if they appear in the order $$$x, y, y, x,$$$ then it is not optimal to choose $$$y$$$ and then $$$x$$$ (never operating on $$$y$$$ and operating on $$$x$$$ instead will lead to a higher answer because the objective function is convex).

Thus, the elements we choose when they appear twice must form a set of non-overlapping intervals. This allows us to do DP, where $$$dp_i$$$ is the maximum score that can be achieved using the first $$$i$$$ elements. To transition from $$$dp_i$$$, we can either use element $$$i+1$$$ when only one copy remains, achieving a score of $$$1$$$, or we can use element $$$i+1$$$ when both copies remain. If the other copy of element $$$i+1$$$ is at position $$$j$$$, this allows us to transition to $$$dp_j$$$ while earning a score of $$$(j-i)^2$$$. The answer is then $$$dp_n$$$.

D: Note that any two operations with $$$c = 0$$$ can be combined, and likewise for $$$c = 1$$$. Thus, we can assume we do one operation of each type for each query.

Split the positions into four groups based on whether their values in $$$s$$$ and $$$t$$$ are $$$0$$$ or $$$1$$$; define $$$cnt_{ij}$$$ to be the number of positions with values $$$i$$$ and $$$j$$$ in $$$s$$$ and $$$t$$$. Without loss of generality, assume $$$cnt_{01} \geq cnt_{10}$$$ (the other case is symmetric). Then, if $$$cnt_{01} \gt cnt_{00} + cnt_{11} + cnt_{10}$$$, the answer is no: $$$01$$$-positions will need to make up a majority of either the $$$0$$$ operation or the $$$1$$$ operation, and in either case one of the two strings ends up with the wrong mode.

Otherwise, the answer is yes. Pair off all $$$10$$$-positions with a $$$01$$$-position; we can add each pair to either operation without affecting the modes. Then, pair off the remaining $$$01$$$-positions with a $$$00$$$-position or a $$$11$$$-position; these pairs can be added to the $$$c = 0$$$ operation or the $$$c = 1$$$ operation, respectively, without causing either string to have the wrong mode (since they add at least as many $$$0$$$s as $$$1$$$s, respectively, to both strings). We can add any leftover $$$00$$$-positions and $$$11$$$-positions to the $$$c = 0$$$ and $$$c = 1$$$ operation, respectively.

E: We can quickly observe that $$$a$$$ should end with $$$c = p_i$$$ for some $$$i$$$. Note that in an array consisting of $$$|a|$$$ ones, the contribution of each index to $$$v$$$ forms an array with period $$$n$$$. If, for any $$$p_i$$$, there exists $$$j$$$ such that the contribution of the $$$p_i + 1$$$ elements starting from position $$$j$$$ in this cycle is less than the contribution of the first $$$p_i$$$ elements, then we can take $$$a$$$ to be $$$j-1$$$ ones followed by a $$$0$$$ and $$$p_i$$$ 1s. Otherwise, it can be seen that the answer is NO, as we can delete the last $$$0$$$ and all succeeding $$$1$$$s without decreasing $$$f(a) - f(I(a))$$$, and if we repeatedly perform this operation we will end with an array $$$a$$$ containing only ones, which has $$$f(a) - f(I(a)) = 0$$$.

This gives an $$$O(nm)$$$ solution (with $$$m$$$ choices for $$$i$$$ and $$$n$$$ choices for $$$j$$$). The key observation from here is to realize that we should take $$$j = p_k + 1$$$ for some $$$k$$$, since if $$$j$$$ takes any other value, decreasing it by $$$1$$$ will never increase the sum of the next $$$p_i + 1$$$ elements of our cycle. This gives only $$$O(m^2)$$$ cases to check, which is sufficient to solve the problem.

F: Consider the value $$$3v_{x, y} - \sum_i v_{i, y} - \sum_j v_{x, j}.$$$ This sum has to be nonnegative for $$$(x, y)$$$ to be a peak; call this value the margin for $$$(x, y)$$$. Performing an operation on the entire array will increase the margin of all elements by $$$n+m-3.$$$ The only way to potentially increase the margin by a greater value in a single operation is to cover all elements in the row or column except for $$$(x, y)$$$, which increases the margin for $$$(x, y)$$$ by $$$\max (n, m) - 1.$$$ This is greater than $$$n+m-3$$$ if $$$\max (n, m) \gt n+m-3$$$, which is equivalent to $$$\min (n, m) \lt 2.$$$ Thus, if $$$n, m \geq 2$$$, we should perform all our operations on the entire array, and we can binary search for the answer to solve the problem.

Now, suppose $$$m = 1$$$. In this case, if we perform an operation on all elements but the first or last, the excluded element's margin increases by $$$n-1$$$ while all other elements' margins increase by $$$n-3.$$$ It can be shown that we should perform no operations other than operating on the entire array or operating on all elements except either the first or last. Additionally, if we perform one operation on all elements but the first and another on all operations but the last, it is superior to replace both with operations on the entire array, so we should only perform one of these two types of operations.

If we fix the number of operations we will perform, we can compute how many operations have to exclude the first element for that element to be a peak, and likewise for the last element. This gives us three cases (performing all operations on the whole array, forcing the first element to be a peak, and forcing the last element to be a peak), and we can check each of them individually. This allows us to binary search the answer as in the $$$n, m \geq 2$$$ case.

G: Let $$$K = 125000.$$$ We first compute which bundle costs up to $$$K$$$ are achievable. To do this, note that we can split any number of goods with cost $$$c_i$$$ into either zero or one each of goods with cost $$$c_i, 2c_i, 4c_i, \cdots.$$$ Thus, we repeatedly add $$$2c_i$$$ to the list of valid prices for each valid $$$c_i$$$. Then, we can use bitsets to compute the list of achievable bundle costs in $$$O(K^2 / 64).$$$

Now, let's first imagine we can only make purchases that reduce our number of coins and figure out which balances can be reduced to zero. For each achievable bundle price, figure out how much it reduces our balance and the minimum ending balance. Then, we can maintain a bitset of achievable balances and simulate the process in reverse. Initially, 0 is the only achievable balance. We can sort the baskets by minimum ending balance and use bitsets to maintain the set of achievable balances (toggling off all balances less than the minimum ending basket for the current balance). Note that we have to use a similar trick to the first step: if it's possible to end at a certain balance after decreasing our balance by $$$x$$$, we can also do this for $$$2x$$$.

What if we can increase our balance? First, find the minimum starting balance from which we can increase our balance. Then, we can make our balance arbitrarily large. From here, we can change our balance by any multiple of the GCD of all possible balance changes from any basket. If our balance is congruent to $$$0$$$ mod this GCD, and if the smallest price is less than the first rebate cutoff, we can win by turning our balance into a large multiple of the smallest price and then buying the smallest price item repeatedly. Otherwise, we cannot win (since our balance will never become $$$0$$$ mod this GCD, or since we can never get to balance zero if there's no bundle we can buy without getting a rebate).

It remains to compute this GCD. We can directly find the balance changes achievable with baskets costing less than $$$K$$$. Any baskets costing greater than $$$K$$$ must achieve the largest rebate; we can choose an arbitrary such basket and compute how much it changes our balance, incorporating it to our GCD. Then, since we can add any price to the bundle of our basket, the Euclidean algorithm tells us that the GCD of all balance changes must be divisible by all of the prices. This is enough to find our GCD (as all balance changes from a basket with cost greater than $$$K$$$ must be a multiple of the GCD of our starter basket and all item prices), which completes the problem.

D < C?

Hello Codeforces,

Could anyone please review user p3n_ph1’s submission to Problem F in Codeforces Round 1113?

Submission:

https://codeforces.me/contest/2248/submission/385184180

The F code is completely different from the user’s A-E submissions: their usual template, macros, formatting and naming style disappear, while polished comments such as “1D Array Routing” and unnecessary defensive input checks suddenly appear.

GPTZero (https://app.gptzero.me/) classified the complete F code as 100% AI-generated. I understand that this result is not proof by itself, so I am only requesting a manual comparison and investigation.

Thank you.