Good job, I appreciate that!

Thanks bro ❤ that will help

It will be tested in production

BledDest orz

I hope no queue issues during the contest

Why only Cyan? when you can become SuperCyan!

same

I will pray for your +19

both are very easy, there is little to no difference

for me it took very long time to do C. i could not proof my approach for so long...

I solved A and B in-contest, having penalties on B, but solved C in a few minutes after reading it post-contest!

A was straight forward.

Its simple DP problem

The key observation is to know how to calculate efficiently the number of groups for each set of color

if 2 numbers are closer to each other, their product will be bigger, e.g.: n^2 > (n — 1) * (n + 1) > (n — 2) * (n + 2) > ...

Solution can be proved using induction. My first thought is using (x + y) ^ 2 / 4 >= x * y. The equal sign happens when x = y => Then we should make x and y closer

If you have 2 numbers $$$x$$$ and $$$c-x$$$ whose sum is a constant $$$c$$$, then their product is $$$x \cdot c - x^2$$$. Differentiating with respect to $$$x$$$ you get $$$c - 2x$$$, and differentiating again you get $$$-2$$$, which is always negative. Thus, setting the first differential at $$$0$$$ gives you $$$x = c/2$$$, which means that the original numbers being closer to $$$c/2$$$ will have the higher product. This is "kind of" common knowledge, but now you have a proof. Algebraic proofs are also common. This one's for the calculus lovers.

$$$xy = \frac{(x+y)^2 - (x-y)^2}{4}$$$ , and as $$$x+y$$$ is constant we should minimize $$$|x-y|$$$

try to make numbers as close numerically to each other as possible 5*5 = 25 , 6*4 = 24 if numbers become equal product is maximum

The intuition behind it is that if the sum of two numbers is fixed, their product reaches max when each of them is set to SUM/2 (you can easily prove this). Since the sum won't change your goal is to minimize the greater number and maximize the lower one, so just figure out the first different digit of each and put the lower of the remaining digits in the one where first different digit is greater and the others in the smaller one.

hint: compare prefix from 0 to n-1

for the first index, you take the maximum of the two, then for the rest of the index take the minimum of the two. why that works? i dont really know lmao

Suppose $$$1 \le x \le y$$$, then we can show that $$$xy > (x-1)(y+1)$$$. Try solving it from here.

Need to make the difference between the two numbers as less as possible. It's a general rule to maximize product of two numbers.

can any one look at my submission and see if it's correct I passed system test but after I read your comments I don't know if it's correct any more https://codeforces.com/contest/1954/submission/256352583

yes I agree its way easier than A and B

Asterisk = unofficial participants != unrated participants. Basically there are no unofficial participants in div1/2 contests. In div3 or below, some class of people must participate unofficially to give less motivations to cheat by making official standings consist of "cleaner" people.

I also think this is weird. In normal div2 contests they don't appear on the scoreboard unless you tick the "Show unofficial" option. For some reason in educational contests they appear even though the contest is unrated for them, and the option to filter for div2 appears only after the hacking phase (or sometime after the contest, anyway)

How did you solve problem E? Your solution looks like it's O(n*logn) (or at least faster than n*sqrt), can you please explain it?

Maybe I really should :(

Me too lol I forgot to add the number of ways to the new state and got WA on pretest 5 three times lol

Had the same issue, tmp[{sum, mx}] += cnt; tmp[{tsum, tmx}] += cnt; You should take mod of them. Since they can get big.

tmp[{sum, mx}] += cnt;
tmp[{tsum, tmx}] += cnt;

you didn't use mod in this line. The wrong answer was because of overflow.

            tmp[{sum, mx}] %= MOD;
            tmp[{tsum, tmx}] += cnt;
            tmp[{tsum, tmx}] %= MOD;
            tmp[{sum, mx}] += cnt;

I fixed it and resubmitted, but got TLE on testcase 16.

It’s an Edu round
“Useful, even well-known ideas will be reused in order to introduce them to a wide range of participants”

Could you please tell me why were these classic and if yes where can i pratice problems like these, is there any archive or a filtered problem list?

how?

No language has any advantage, If The number can Go upto 10^100 then ofcourse you shouldn't even consider making it a number anyway, as the biggest number would almost take 300+ bits to be stored, If anyone even as to tries to store them in a int ( say someone stores it in a Big-integer in Java) then it just makes accessing individual digits harder, so a number isn't the way.

Actually, it's not really about large numbers, just the property that the product would be maximized when the numbers are closest to each other.

char[] x = in.next().toCharArray();
char[] y = in.next().toCharArray();

boolean same = true;
for (int i = 0; i < x.length; i++) {
    char larger = (char) Math.max(x[i], y[i]);
    char smaller = (char) Math.min(x[i], y[i]);

    if (same) { // numbers were same so far, assign the larger digit to x
        x[i] = larger;
        y[i] = smaller;
    } else { // x is larger, assign the larger digit to y (bringing it closer)
        x[i] = smaller;
        y[i] = larger;
    }

    same &= larger == smaller;
}

You didn't use knapsack?

how did you solve it? I did knapsack and that is a pretty important constraint.

Ehh? How did you do it without using the bound on the sum?

If the total sum of $$$a_i$$$ does not have that constraint, then the maximum total sum will be $$$5000^2$$$. How you can deal with it?

my solution was O(n * sum(a[i])) memory and time. is there a faster algorithm?

I didn't see the additional constraint during the contest. I solved it for a[i] <= 5000.

Problem E. Let's call F[i] is the number of connected components when there were i damages dealt to all elements. We can find this by DSU or simple array. Lets for k from 1 to max(a[i]). Consider when the damage strike is k. At damage 0, F[0] = 1, so we need one strike. Next, when the damage is k, we need F[k] strike (because there were F[k] components). F[2 * k], F[3 * k], F[4 * k], ... is similar. The complexity is n / 1 + n / 2 + ... + n / n = n log n.

I did the same mistake in D

just realised I was getting WA in E because I was taking mod.

I see you draw attention to the channel

And if this will be considered with less than 1000 watches then this channel can stop the rating for CF div2 till its owner die

is it possible to ban these cheaters IP address so that they can never visit codeforces website again with their device...

When you want to "merge" 2 nearest numbers, neither of which is equal to a[0], you merge them using only v[i] — v[i-1] — 1 deletions. (However, you are correct in your count of moves, necessary to made first and last numbers in array differ from each over).

This is your code after the mentioned changes 256361851

I think I'm the only one who didn't notice that line:

Additional constraint on input: the total number of balls doesn't exceed 5000

I think they set $$$n$$$ to only $$$10^5$$$ on purpose, letting $$$O(n^{1.5})$$$ solutions (easier to come up with) to pass.

Can you pls provide a proof of "If the maximum of a subset is greater than the sum of the rest of the elements, the value is the maximum; otherwise, the value is ceil(sum/2)" for problem D (for the ceil(sum/2) part)

Pretty well known. I guess high-school math covers such stuff

I just wrote the samples on a paper in this form 73 = 7*10 + 3 31 = 3*10 + 1

73 * 31 = (70 + 3) * (30 + 1) = 70 * 30 + 70 * 1 + 3 * 30 + 3 * 1 (Tried swapping numbers later)

I noticed that after I find the most significant number in a that is larger than a number in b (assuming a > b), b is more important in making the product a larger number, so I need to maximize the numbers in b after that first different number.

That's how I concluded it, not sure if everybody did the same.

you could have written a brute force solution and tried to find a pattern

you can easily see the trick by quantities, x*y and (x+1)*(y-1)

here when y>x+1 its always better to reduce from bigger quantities i.e., y and and increase in smaller quantities i.e, x.

simple recursive dp 256322429

groups will be max(sum/2,max_element)

If you brute force over all possible sets, that would be $$$2^{5000}$$$, which is infeasible. A hint here would be to consider that the sum of all possible subsets is very small, and you can probably do just as much with a $$$CountOfSubsetsWith[SubsetSum]$$$ as brute-force.