Couldn't solve C,D on time, but the problems were great

Thanks for the problems. It was one of the most fun Div. 2 rounds in quite some time.

Problem E was easier than usual, but I think a lot of people would fail the testcase where every character is T, which results the answer being 1 rather than 0. The given solution also produced the same wrong answer.

Somehow D(by greedy logic) got accepted. Here for the expected solution.

Nice contest : )

Friendiks

Solution for A,B,C isn't visible, it says loading

UPD: It's finally visible, Thank you!

c can be solved with bfs and lca too

first of all for eg there lies a level which is 2 5 6 7

let the parents of 2 and 5 be 3 and parents of 6 and 7 be 4 then

the total number of different lcas you get is how your answer increases from n

for example

lca of 2 and 5 is 3 then lca of 5 and 6 is basically lca of 3 and 4 so let that be 1, then lca of 6 and 7 is 4 so 3 different lcas you got for this level so increase your answer by 3

do this for all levels

this works because naively you can run bfs for every node and count distinct levels, but if you observe then you'll see each level gets merged into one level which is a guild for an ancestor

I solved (not in time unfortunately) E in $$$O(n^2)$$$. Consider the following subproblem for fixed $$$D$$$: minimize the number of T under the constraint that $$$\sum_{i=l}^r x_i \le D$$$ for all intervals $$$[l, r]$$$. The subproblem can be solved greedily in $$$O(n)$$$ by starting setting all N->F and going left-to-right and maintaining the current prefix sum and maximum prior prefix sum of $$$x_i$$$; each time we violate the constraint, flip the rightmost (before our current position) possible N->F to be N->T. Solve the subproblem for each possible $$$D\in[0,n]$$$.

Yet Again D<C

Why contradiction proof for B? Direct proof is more educational and straightforward.

1) By definition of LCM:

and

2) Then:

3) Therefore b divides the left hand side, and so

meaning b divides both a and c, as desired.

Great contest! But I feel like cheating seemed much more prominent in today's contest because I didn't expect C to get that many solves to be honest.

B is pretty OEISable, but great set overall!

This was one of the best Div. 2 rounds I've ever done!

Unfortunately didn't have time to solve E or F

Has anyone more clean explanation of task D? I just don't understand

Math-heavy questions always feel charming. Although I overcomplicated B

I know B is possible in $$$O(\sqrt{n})$$$ with square root algorithm combining or using blocks of equal values, but is there a better time complexity obtainable?

Hello Codeforces, I know I have low rating and I was unable to solve B in the contest. But here is my approach to proving the idea behind B, I feel this approach is less arbitrary and easier to come up with, please let me know if there are any flaws in my reasoning: gcd(lcm(a, b), lcm(b, c)) = gcd(a, c)

lcm(a, b) = a * (b / gcd(a, b))
lcm(b, c) = c * (b / gcd(b, c))

gcd(b / gcd(a, b), b / gcd(c, b)) = 1, this is a MUST for the condition to hold


this means these two terms share no common prime factors

X = b / gcd(a, b)
Y = b / gcd(c, b)

gcd(X, Y) = 1

a, b, c -> t, u, v (the corresponding exponents for each prime factor p)

X: u - min(t, u)
Y: u - min(v, u)

min(u - min(t, u), u - min(v, u)) = 0 <-> u - min(t, u, v) = 0

u = min(t, u, v) -> t, v >= u

since t, v >= u, for every prime factor p, b MUST be a factor of a and c

Funnily enough, $$$O(t \sqrt{n})$$$ is allowed for D

Nice contest! Problem F is really cool.

All divisors with the same $$$\Omega \ge 2$$$ can be ordered so that adjacent ones have a common prime divisor.

This assertion is not trivial. I cannot prove it strictly in contest. It is intuitively correct, though.

My post contest discussion stream here and hints here

guys im getting really demotivated my rating isnt improving. How should I grind? I used to solve 2 now idk if i have lost skill or smthing

great contest!

For C, there is a better way to solve the question, which looks cleaner on the implementation side.

Instead of tracking absolute depths from the root and subtracting them later, the bottom-up DFS can directly return the maximum relative height of the subtree. Since every node contributes 1 to the answer we can initialize our answer from n. During the single DFS traversal, we can directly accumulate the unique guilds formed by the branching channels by adding the 2nd largest child height to the answer. Also to add on the official answer used 4 arrays, but it can be solved only using one.

you can check my submission here Submission

All problems are interesting!

Here’s an explanation for D which may be easier to understand:

First, find the prime factorisation of $$$n=p_1^{\alpha_1}\dots p_m^{\alpha_m}$$$

For example, let’s say $$$n=2^5\cdot 3^5 \cdot 5^5$$$.

Consider the divisor chain $$$[2], [2^2],\dots, [2^5],[2^5\cdot 3],[2^5\cdot 3^2]\dots [2^5\cdot 3^5\cdot 5^5]$$$

Since each divisor $$$d_i$$$ is a proper divisor of all other divisors $$$d_j$$$ for $$$j \gt i$$$, they each have to be in their separate layers.

Furthermore, all primes must be in their own layer, for which there are $$$m$$$ of them.

So $$$n$$$ must at least be in layer $$$A+m-1$$$, where $$$A=\sum_{i=1}^m \alpha_i$$$. We subtract 1 since we already considered $$$2$$$ as a layer so we don’t double count it when counting the number of primes.

Then to prove that these layers created are sufficient to fill all other divisors, consider the condition that no two numbers in a layer can be proper divisors of each other.

An easy way to avoid adding a number which divides some other number already in the layer, is to remove a prime factor and add another.

For example, in the layer with $$$[2^5\cdot 3^2]$$$, an easy way to add a divisor is to remove one multiple of 2, and add a multiple of 3 or 5. We will never add a proper divisor since a proper divisor must have a multiplicity (i.e. its value of $$$\Omega(x)$$$) strictly less than the current layer.

Note that we can’t only add or only remove prime factors, since that might end up adding a multiple or divisor some number in the layer. But for numbers with the same value of $$$\Omega(n)$$$, they will never be proper divisors of one another.

My Solution for Problem B. And I think its unique. no one has commented it yet.

Firstly lets change the equation by a bit.

$$$lcm(a,b)$$$ and $$$lcm(b,c)$$$ must contain all factors of $$$b$$$, so their gcd certainly contains $$$b$$$.

Beyond $$$b$$$, the only extra prime powers that can appear in both numbers are those common to both $$$a$$$ and $$$c$$$. So we can say that $$$gcd(lcm(a,b),lcm(b,c)) = lcm(b,gcd(a,c))$$$. So now the equation becomes $$$lcm(b,gcd(a,c)) = gcd(a,c)$$$.

The equation will only hold when $$$b$$$ is a divisor of $$$gcd(a,c)$$$.

Now, to solve this problem, we can either fix $$$b$$$ or $$$gcd(a,c)$$$. I fixed $$$gcd(a,c)$$$. As $$$a,c \leq n$$$, we have $$$1 \leq gcd(a,c) \leq n$$$. Let $$$gcd(a,c)=x$$$. (We will iterate over all $$$x$$$, where $$$1 \leq x \leq n$$$.) Now we need to count the number of pairs $$$(a,c)$$$ such that $$$gcd(a,c)=x$$$.

Since both $$$a$$$ and $$$c$$$ are divisible by $$$x$$$, write $$$a=xi$$$ and $$$c=xj$$$.

Then $$$gcd(a,c)=x$$$ if and only if $$$gcd(i,j)=1$$$.

So, for every $$$x$$$, our task reduces to counting the number of coprime pairs $$$(i,j)$$$ with $$$i,j \leq \lfloor n/x \rfloor$$$.

This can be computed efficiently using the Euler Totient Function. We precompute all totient values beforehand to answer each $$$x$$$ quickly. Now let the number of such pairs be $$$y$$$.Also, let $$$d$$$ be the number of divisors of $$$x$$$.

Since $$$b$$$ must be a divisor of $$$gcd(a,c)=x$$$, there are exactly $$$d$$$ possible choices for $$$b$$$. Therefore, for a fixed value of $$$gcd(a,c)=x$$$, the contribution to the answer is $$$y \times d$$$.

I solved A by myself like solution,but could't know why:(