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...

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) > ...

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

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

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://mirror.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?

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.