Thanks for your participating!

author: 74TrAkToR, developer: marzipan, zwezdinv

Tutorial is loading...

author: OR_LOVe, developer: marzipan

Tutorial is loading...

author: azureglow, developer: marzipan

Tutorial is loading...

author: OR_LOVe, developer: zwezdinv

Tutorial is loading...

author: marzipan, developer: marzipan

Tutorial is loading...

author: zwezdinv, developer: zwezdinv

Tutorial is loading...

author: 74TrAkToR, developer: 74TrAkToR

Tutorial is loading...

author: platelet, developer: errorgorn

Tutorial is loading...

Ok, why is the editorial being downvoted now?

where is the tutorial for problem G?

got removed so no editorial

Great contest! Hope you all have a good new year!!! :)

Please don't downvote the tutorial,it's always helpful.

downvote, if you liked editorial

I liked your comment too, so I downvoted it.

Where is tutorial of G?

It was removed since the author's solution was incorrect.

Bro expects to get upvotes

C'mon, what's done is done. I wasn't a fan of the contest either but dwelling on it when the rating change has been established is not going to achieve anything.

Started as Good bye 2023, ended up with RIP 2023

Hello azureglow,

Really nice editorial!

Could you please add spoiler tags for each hint? Would be really helpful.

Thanks and wish you a Happy New Year!

Can some explain me the solution of E please some what elaborately?

First, note that you can calculate the maximum answer by considering for each node: the two largest diff values from that node to any nodes in its subtree.

So what we are doing is taking a tour of the entire tree, and updating the diff values from each node in a subtree to the current node that we are visiting. If the activity of our current node is x, then we add 1 to the diff values of all nodes in the subtree such that the sample path to them does not contain the activity x. This can be achieved by simply adding 1 to the diff values of the whole subtree, while just subtracting 1 from the subtrees of nodes in which the first additional instance of activity x is seen (basically if any node in the subtree has value x, we don't need to consider any of the nodes in this new nodes' subtree, as we have already accounted for the diff value change). We can find the nodes in a subtree with activity x in log time with a set, and after we account for the additional instances of x, we can remove them from the set, so each node is only considered at most once in this set. After we are done visiting a node, we add it to the set as well.

Now to find the largest diff values for each subtree, we consider each child of the current visited node separately. We can do a range query over the entire subtree of each child to find the largest diff value, and multiply the two largest values of different children.

So we want to support both range updates and range queries to the diff values, which is achieved with a lazy segtree. The segtree will contain the nodes in order of our tour, so subtrees will always be contiguous, and for each node we can simply store the range of its subtree in our segtree, which we then use for range updates and queries.

I don't really have a sample code, but you can probably just look at any submission to E for an example of implementation.

nice explanation, thanks!

this may be a dumb question but why can't we just use a simple DFS to find "the two largest diff values from that node to any nodes in its subtree"

If you do this for every subtree, then it takes n^2 time, which will TLE

but since we DFS from the root of the entire tree, isn't it true that we will go through every subtree with a single DFS? it's like DP on tree (but without the second DFS)

How would you "find the two largest diff values from that node to any nodes in its subtree" for every node with just a single dfs?

I have implemented this but it gives WA on test case 88 of test 2. The problem is I'm not using sets to retrieve the nearest nodes in the subtree that match the current color. But I can't figure out what's wrong with my 'easy' approach though wherein once I reach any node of color v[i], I push_back the current node to the last parent that had v[i]. Can anyone help me please? Thank you!

Submission: 239931057

You have to update the value of mp[v[node]] to its original value when the whole subtree dfs is completed. For reference, you can see my solution.

At least, nice editorial in some ways, thank you.

However, I think, for a single day, we contestants have proven to you that, if you cannot do something, learn from others, learn from participants, learn from ones with a much higher rating (exclude me, though).

In that case, can you stop writing the long, tedious, lengthy, cumbersome, voluminous and confusing solution to H? It should be quite simple and can be described much shorter...

Also I have already seen a number of solutions to G which have been proven to have correct complexity. Why don't you show your original solution (you should have written one before the contest is started, shouldn't you) and try to analyze it with a similar method? Even if it is totally wrong, can it be better if you just ignore it and explain, there's a little mistake but our solution is proven by AC, ..., etc.?

We want to see all your problemsetters' attitude towards everybody's anger!And after all, let's don't downvote him. He has received too much. Please downvote 74TrAkToR as much as you want, sir, that's what you really should do —— ban him from coordinating shit contests.

Q: What is "H2.

wMatrix Rank (Hard Version)"?I want to know the authors for each problem.

And indeed, G has solutions, given by djq_cpp and ksun48

G has

WRONGpretests, and that affected ksun48 in the contest!For H, the official solution is ridiculously verbose. In the contest, I referred to MSE/A1117521 and MSE/A2147194. This is tractable for anyone studied linear algebra and combinatorics.

BTW, I

upvotedthe tutorial, because the authors deserve it.Can anyone explain me E? Here is what I understand so far, we will traverse all vertices, suppose we are at node x, we will consider this as our lca, then for each child subtree we just need the maximum distinct and second maximum distinct and the subtrees that we select must be different, then we multiply them both(also considering the color of current node x). It is written in the tutorial to use euler tour, suppose I am doing the euler tour, what should I add or subtract in the euler tour array?

.

and how will that help to get our answer, if you can please elaborate, that would be helpful.

more specifically, when we are doing these +1 and -1 operations, I'm not getting how the children subtrees would give maximum distinct activities across a path and not for the whole child subtree

I finally understand it. We need to maintain: the value diff(u, i) for all the node u's descendant node i. To avoid the repeated calculation of the same color, we need to subtract 1 for those that has the same color as u. Then we can calculate the first and second maximum. And finally for node u's parent v, diff(v, i) would be diff(u, i)+1, so we need to +1 to the subtree of u (assume that no repeated color exists. If yes, when visit v, we will subtract 1 for the repeated color). Here is my submission

nvm

Can anyone explain C to me, I couldn't understand it at all

it's sad:(

why ?

let there be m total numbers and total sum = sum out of those m numbers x numbers are odd not that which ever player's turn it is does not matter the new number added to the array is as ((a[i] + a[j]) / 2) / 2 is even so if a[i] and a[j] are of same parity the score will reamain same but if a[i] and a[j] are of different parity then the score decrease by 1 so for first player it is optimal to choose a[i] and a[j] of same parity (more specifically both should be odd) and for second player will chose ai and aj of different parity. you might have a question why first player tries to choose ai and aj both. it is because if he choose both odd then there will be fewer chance of the second player choose different parity numbers. so if there are X odd number then the first player will choose 2 odd numbers and insert an even number total score remain same SUM. X -> X — 2 now the second player will chose 1 odd and 1 even score will become SUM — 1 and X -> X — 3. now this pattern will continue till X >= 3 if X is 2 then first player will both odd numbers and the score remain same SUM. if X = 1 then the it has to be chosen atleast once so the score will decrease by 1 SUM -> SUM — 1. simple formula to calculate this is ans = (SUM — (X / 3) — ((X % 3) % 2)). hope this helps. here is my submission 239685245 to understand better what i'm saying. please forgive my english

I have a similar code, can I send it to you?

yes share it here

What am I wrong here?

as much as i can understand you code you subtracting 1 from ans for each odd number but have to subtract 1 for every 3 odd numbers

if the sum of the odd numbers is odd, then I decrease the sum of the odd numbers by 1. You say it should be done every 3 odd numbers. I didn't understand why

for even numbers no affect on the final result but for odd there is two steps done repletely which are

1 — choose 2 odd and do the operation to don't waste it's value

2 — choose 1 odd + 1 even and do operation to decrease the value by 1

so here we get that there is decreasing by 1 per 3 odd numbers also you can check my answer 239675910

Thank You so much :)

input: 5 7 13 11 19 1

output: 7 20 30<- okay but after 48 why not 50 ? 7, 13, 11, 19 7+13 11+19 20+30=50 WHY ?!

suppose there are 6 odd number 1 3 5 7 9 11 First -> remove 9 11 insert 20 A = {1 3 5 7 20} Second -> remove 7 20 insert 26 A = {1 3 5 26} First -> remove 3 5 insert 8 A = {1 26 8} Second -> remove 1 and 26 insert 26 A = {8 26} First -> remove 8 26 insert 34 A = {34} ans = 34 notice that there are 6 odd numbers first first 2 turns SUM decresed by 1 then for next 2 turn SUM decrease bu 1 ans = (36 — (6 / 3) — ((6 % 3) % 2)) = 34

I wrote it a little differently but it was accepted

great continue upsolving GL&HF

Thank You so much too :)

This was a very good explanation. Thank you. It was helpful.

Thanks! Happy new year

Wanderfull round guys. People who are downvoting everything are a punch of noobs actually

[ Deleted ]

can u stop whining everywhere bruv, we get it but this is the editorial

[ Deleted ]

wdym lmao, go cry about it in the announcement or something, there has already been enuff complaints , bruh this shit is past and irrelevant, in the editorial at least

[ Deleted ]

it's clear that you're Folka but in 2nd account

I don't even have any other accounts!

ok maybe I'm wrong idk

Just a request If you are going to make this contest unrated, do it this year itself please. I understand why most people are unhappy with the contest and therefore I am fine with it being converted to an unrated one. But I also don't want to end 2023 with a rating of 1383 and then wake up in 2024 seeing myself back at 1270. So this was just a request, hope you consider it :)

Can anyone prove this to me or explain why?

`In this case, b=a⋅p, where p is the smallest prime factor of x. Then x=b⋅p=b⋅ba`

So (b mod a = 0) means that a is a divisor of b. If b and a are the first and second biggest divisors of some number x respectively and a is a divisor of b, a must be the greatest divisor of b. To show by contradiction: assume a isn't the greatest divisor of b. Then there is some middle number between a and b, call it c, which divides b. Since x % b = 0, x % c must be = 0, and a and b wouldn't be the first and second largest divisors of x.

Now how do you find the greatest divisor of b? By dividing b by the smallest divisor of b, which will always be the smallest prime factor of b, call it p. So a = b/p, or b = ap.

Now we show that, assuming b and a are the first and second greatest divisors of some number x and b % a = 0, one solution for x = bp.

We will show that, assuming x = bp and b % a = 0, the second greatest divisor a = b/p.

Since p is the smallest prime factor of b, p is also the smallest prime factor of bp. So in order to get the greatest divisor of bp, we just divide by p. Our greatest divisor of x = bp is b, which is what we want.

Now we are left with b as the greatest divisor of x = bp and we can pull out another smallest prime factor of b to get b/p = a. And so a is then the second greatest divisor of bp. Or is it?

What if our smallest prime factor of b is p = 2 for example but our second smallest prime factor of b is s = 3? Then surely we would have a = bp/s = 2b/3 rather than bp/p^2 = b/2, right?

Well let's assume that the second greatest divisor, a, of x = bp is bp/s rather than bp/p^2. Recall that, in this case, a = bp/s must be the greatest divisor of b. So b/(bp/s) must be an integer. b/(bp/s) = s/p which is not an integer since s and p are both primes. So a = bp/s doesn't work. s can be generalized to any single prime factor of b where s > p.

And of course, when dividing by two prime factors of bp to find a, it will always be correct to divide by the two smallest primes, which is p^2, otherwise a wouldn't be the second greatest divisor.

Now we have shown that, for the case where b % a = 0, one solution for x = bp where p is the smallest prime factor of b. And since a is the greatest divisor of b, we can compute this easily by doing b^2/a.

Hope this helps. I guessed the solution in the contest and thought about it later and realized it had a nice little proof.

What if our smallest prime factor of b is p = 2 for example but our second smallest prime factor of b is s = 3? Then surely we would have a = bp/s = 2b/3 rather than bp/p^2 = b/2, right?here you mean to say a=bp/ps and not a=bp/s, right?

please ignore this comment, i had misread and codeforces isn't letting me delete this

I meant to say a = bp/s because if a were bp/ps = b/s then a wouldn't be the second greatest divisor of bp since there is b/p > b/s and bp % (b/p) = 0.

In this part of the explanation I was basically showing why a cannot be bp/s.

Edit: haha ok I see your edit too. Unfortunately codeforces doesn't let you delete comments lol

Don't just write the statement (for this case, the answer is this and for that it is that) . Prove your Solution ,that is what editorials are for.

My proof for problem H doesn't use any generating function and I find it more natural. I have very bad latex skills so I couldn't really manage to write everything so I'll link some pictures of my draft if someone is interested in the computations.

Disclaimer: I don't do math in english so my wording might be inaccurate sometimes (although I think you should roughly get the idea if you're familiar with the concepts I'll use)

The general idea is the following:

Let $$$S_r = {\{M \in \mathbf{Mn(\mathbf{F_q})} | rank(M) = r\}}$$$.

We are interested in the cardinal of $$$S_r$$$. As the constraint is on the rank of the matrix, it's pretty reasonable to solve this by considering equivalence classes.

Let's consider the group morphism:

$$$(P, Q) -> (M - > PMQ^{-1})$$$

where P and Q are in $$$\mathbf{GLn(\mathbf{F_q})}$$$.

It is a group action.

The orbits of this action are fixed by the rank (two matrixes are equivalent iff they have the same rank, this is a consequence of the rank theorem (more specifically, the fact that restricting a linear application to a supplementary of the Ker gives an isomorphism)).

Having this group action in mind, we get that

$$$|S_r| = \frac{|\mathbf{GLn(\mathbf{F_q})} \cdot \mathbf{GLn(\mathbf{F_q})}|}{|Stab_r|}$$$

(my cdot here should be an x but idk how to type this :/)

Now, to compute $$$|Stab_r|$$$, the easiest matrix to pick is $$$J_r$$$ (the canonical representant of the equivalence class of matrixes of rank r, a matrix that has 0 everywere and 1 on the first $$$r$$$ positions of the diagonal).

Now, $$$P, Q$$$ are in $$$Stab_r$$$ iff P Jr = Jr Q

I'm unable to type the whole thing because my latex is bad but essentially it is just about writing P and Q as block matrixes (with dimensions matching Jr), it gives an isomorphism between the stab and:

$$$GLr(Fq) \cdot GL_{n-r}(Fq) \cdot GL_{n-r}(Fq) \cdot M_{n, n - r}(Fq) \cdot M_{n - r, r}(Fq)$$$

(again the cdots should be x)

Now you're only left with some powers of q and some cardinal of $$$GLn(F_q)$$$ to compute.

This is easy to compute as we can see a matrix M in GLn(F_q) as a free family of n vectors of the space (F_q)^n (so a basis).

Thus, by the usual basis construction process, there are q^n — 1 possibilities for the first vector (everything except 0), then q^n — q possibilities for the second vector (everything that is not in the subspace generated by the first vector), then q^n — q^2 for the third etc

details about the cardinal of the stab

details about the final result

Alternatively, to obtain a matrix $$$n \times m$$$ of rank r over $$$F_p$$$, you can :

Choose a subspace of $$$F_p^n$$$ of dimension r : there are $$$(p^n - 1) \cdots (p^n - p^{r - 1})$$$ ways to choose $$$r$$$ independent vectors, but each subspace is counted once for each of its basis, of which there are $$$(p^r - 1)\cdots (p^r - p^{r - 1})$$$

Given a basis of this subspace, you need to choose $$$m$$$ vectors in $$$F_q^r$$$ such that the resulting subspace is of dimension $$$r$$$, which is the same as choosing $$$r$$$ vectors in $$$F_q^m$$$ such that the resulting subspace is of dimension $$$r$$$ (this can be seen by swapping the rows and columns of the matrix). Therefore you have $$$(p^m - 1)\cdots(p^m - p^{r - 1})$$$ possibilities

In the end, you get the wanted formula $$$f(n, m, r, p) = \displaystyle\prod_{j = 0}^{r - 1} \frac{(p^n - p^j)(p^m - p^j)}{p^r - p^j}$$$ which can be trivially calculated in $$$\mathcal{O}(r)$$$ and easily in $$$\mathcal{O}(1)$$$ amortized over $$$r = 0 \ldots k$$$

By the way very nice draft pictures and even nicer profile picture !

orz, I think this is roughly the same thing except you implicitly compute the cardinal of the stabilisator which makes things easier

I guess the power of a Jambon beurre is unfathomable

What's the proof for n+2 in problem D? When we have 2 number rhat we should fill??

Here in problem B, I Understand the toturial and the code. But I don't know WHY ? okay we have two cases:

case 1 where (b%a != 0) , here LCM is the answer. but why? why X= LCM? Can't it be X>LCM or X<LCM ? WHY X=LCM ?

case 2 where (b%a == 0), Here we assume that there is a smallest factor P of X. Then we assume that this smallest factor of X makes the following rerlation (b= P.a) valid ..WHY ? Then we assume that X=b.P WHY?

IS there some mathimatical proof or only intuation?

If d divides x then x/d divides also x. a and b are the biggest divisor smaller than x. Conversely x/a and x/b are the smallest divisor bigger than 1. Here two cases are possible : either they are two DIFFERENT prime factor p and q, this corresponds to case 1. Either they are p and p^2 which correspond two case 2.

first, thank you bro for replying.

I get that If there are two largest factors (a , b) of (X), Then (q=X/b ,p=X/a) are the two smallest factors.

here you say "either they are two DIFFERENT prime factor p and q"

but the question did not obligate a a&b to be primes, much less p,q. I didn't understand this point. please explain more

Okay, you understand that $$$p$$$ and $$$q$$$ are the two smallest factors greater than $$$1$$$ of $$$x$$$.

The fact that $$$p$$$ is prime and $$$q = p^2$$$ or $$$q$$$ is prime is just a general property of the two smallest factors greater than $$$1$$$ of any integer (that has two such factors). Here is the proof:

Claim: $$$p$$$ is prime.

Proof (by contradiction): Suppose $$$p$$$ is the smallest factor greater than $$$1$$$ of $$$x$$$ and $$$p$$$ is not prime. Since $$$p$$$ is not prime, it can be represented as $$$p = st$$$ for some integers $$$1 < s, t < p$$$. Now, $$$s$$$ is a factor of $$$p$$$ and $$$p$$$ is a factor of $$$x$$$; thus $$$s$$$ is a factor of $$$x$$$. But $$$s < p$$$, so $$$s$$$ is a smaller factor than $$$p$$$ — a contradiction. Thus, $$$p$$$ must be prime.

Claim: Either $$$q = p^2$$$ or $$$q$$$ is prime.

Proof (by contradiction): Suppose $$$q$$$ is the second smallest factor greater than $$$1$$$ of $$$x$$$, $$$q \ne p^2$$$ and $$$q$$$ is not prime. Since $$$q$$$ is not prime, it can be represented as $$$q = uv$$$ for some integers $$$1 < u, v < q$$$. If $$$u = p$$$ and $$$v = p$$$, then $$$q = p \cdot p = p^2$$$ — a contradiction. Otherwise, either $$$u \ne p$$$ or $$$v \ne p$$$. Now, both $$$u$$$ and $$$v$$$ are factors of $$$q$$$ and $$$q$$$ is a factor of $$$x$$$; thus $$$u$$$ and $$$v$$$ are factors of $$$x$$$. But $$$u < q$$$ and $$$v < q$$$, so $$$u$$$ and $$$v$$$ are smaller factors than $$$q$$$. One of them might be equal to $$$p$$$ which we already considered but one of them must be not equal to $$$p$$$ but instead, be a new, smaller factor of $$$x$$$ we didn't yet count — a contradiction, since $$$q$$$ was meant to be the second smallest factor. Thus, $$$q$$$ must be prime or $$$q = p^2$$$.

@vgtcross fantastic! thank you, bro. I'm presuaded that p must be prime and q must be either prime or p^2.

and form above, @123gjweq2 proved that if

`b%a=0`

and are the two greatest divisors of X, then a is the greatest divisor of b. Then`b/a`

gives the lowest divisor of b, which he assumed to be the lowest divisor of X which is p.which gives the following equation:

`p= b/a`

then`x/b=b/a`

then`x=b^2/a`

. All is well, if we proved that assumtion that the lowest factor of b is the same as the lowest divisor of X.For case 1 it is the lcm of a and b due to the reason that the lcm will be the smallest number to exist for a and b such that both a and b are its factors. get it?? that is like the definition of lcm.

for the second case we assume p is the smallest factor of X because it is given that b will be the largest factor of X. therefore by this relation b*p = x as b is the largest factor p has to be the smallest factor. for example for x = 64 its factors(except 1 and 34 ofcourse) are: 2, 4, 8, 16, 32. to make 64 we take one factor from left (2) and one from right (32) and so on.

first, thank you bro for replying.

LCM of a and b is the smallest number that can be devided by the two factor (a,b) of a givin number (X). But what problem B here asks us is to give him the number with largest two factors a,b . then we deducte that X can be devided by a and b. and LCM is the smallest number that can be divisable by a and b. But can we deducte that a and b will be the greatest divisors?

I feel there is a strong relation, but I don't see why LCM MUST be used logically or mathimatically?

here is an example, 63 has the following factors: 1 3 7 9 21 63 the largest two factors here (21,9) okay?

but if I give you (7,9) with your definition, you will give me 63, but 63 has (21,9) as largest divisors not (7,9)

do you see what I'm trying to get to?

Your doubt is very valid. I see what you are trying to get to.

However the problem statement is not asking for a $$$x$$$ in such a general sense for

anygiven $$$a < b$$$. The statement is more like: "IfI take the guaranteethat $$$b$$$ and $$$a$$$ ARE CERTAINLY the two greatest divisors of some $$$x$$$. Can you find that $$$x$$$ for me ?"If you understood what I mean you will also understand that although you can calculate an answer for the case $$$(7,9)$$$, it is

nota valid test input.That is to say the case $$$(7,9)$$$ is beyond the scope for the problem.

first, Thank you @SXZZ5 for replying.

you're right. I've noticed that a while after asking. Seizing the opportunityof of you being here, Could you tell me why we considered that in case

`b%a=0`

that the lowest divisor of b is the same as lowest divosr of`X`

(let it p) leading us to the solution that`x= b.p= b.b/a`

.I knew the proof that

`a`

is the largest factor of`b`

. So dividing`b/a`

will give the lowest divisor of`b`

. why must this lowest divisor apply to`x`

itself as well?https://mirror.codeforces.com/blog/entry/124138?#comment-1103110 See this comment for an alternate way of arriving at the $$$x = b\cdot \frac{b}{a}$$$ solution for the case $$$b\;mod\;a = 0$$$.

For the short answer to why smallest factor of $$$b$$$ should be the same as the smallest factor of $$$x$$$ consider the opposite case.

Let's say the smallest factor of $$$x$$$ is smaller than that of $$$b$$$. But,then that would mean that $$$b$$$ is no longer the largest divisor of $$$x$$$, which is a contradiction to the requirement. This proves why smallest factor of $$$x$$$ cannot be smaller than that of $$$b$$$.

Similarly consider the smallest factor of $$$x$$$ is larger than that of $$$b$$$. But, that is simply not possible. How can the smallest factor of $$$x$$$, be larger than the smallest factor of some intermediate factor $$$b$$$ of $$$x$$$ ?

Thus, with these two contradictions smallest factor of $$$b$$$ must be the same as smallest factor of $$$x$$$.

As a failure after taking this contest, I realized that I feel more like a failure than a failure.

What does "And we still have $$$2$$$ numbers left, let's construct them as follows:$$$ 9...6...1 , 1...6...9$$$ where in the gaps between the digits there should be $$$(n−3)/2$$$ zeros, these will correspondingly be the squares of the numbers $$$1...3,3...1$$$ with $$$(n−3)/2$$$ zeros in the gaps between the digits." mean? I don't get it.(D. Mathematical Problem)

for n=3 it corresponds to 13 and 31 whose square are 169 and 961, for n=5 to 103 and 301 whose squares are 10609 for n=7 to 1003 and 3001 whose square are 1006009 and 9006001 and so on

thanks.

Thanks for a wonderful contest.

in problem D, you just tell a simple solution, where is the proof? where is it???

$$$13^2=169,103^2=10609,130^2=16900$$$

$$$(10^k+3)^2=10^{2k}+6\times 10^k+9$$$

adding

`00`

to the end of number = adding`0`

to the end of its square root961 is just the same

We can generate $$$n-1$$$ numbers in this way. Add

`196000000`

to reach $$$n$$$.$$$(3\cdot10^x + 1)^2 = (3\cdot10^x)^2 + 2\cdot(3\cdot10^x)\cdot1 + 1^2 = 9\cdot10^{2x} + 6\cdot10^x + 1$$$

Here, the number of zero digits between $$$3$$$ and $$$1$$$ in $$$3\cdot10^x$$$ is $$$x-1$$$.

The numbers $$$9\cdot10^{2x}$$$ has $$$2x$$$ trailing zero, and the number $$$6\cdot10^x$$$ has $$$x+1$$$ digits. So when you add them, the number of zero digits between $$$9$$$ and $$$6$$$ is $$$2x - (x+1) = x-1$$$. Likewise, if you add up the whole thing, the number zero digits between $$$6$$$ and $$$1$$$ is $$$x-1$$$.

So, we can say that numbers of form $$$9...6...1$$$ are always square of the integer $$$3...1$$$.

Same proof for $$$1...6...9$$$.

And you can always append two zeros to a number by multipling by $$$100$$$. If the original number is can be written as $$$x^2$$$, where $$$x$$$ is some integer, the resulting number will be $$$x^2 \cdot 10^2 = (10x)^2$$$, still a square of an integer.

I tried a lot but am not able to fit the solution of E in the time limit. Can someone please help me ?

Link — https://mirror.codeforces.com/contest/1916/submission/239811018

Shouldn’t MAXN be 3e5 + 5?

I tried that as well. I am not able to get AC even though I see it is very similar to many accepted solutions. Please help.

Not sure, but I see a lot of people having to constant optimize.

Update — I was able to solve it. I was doing point updates instead of range updates in the segment tree. This was causing TLE.

AC Code — https://mirror.codeforces.com/problemset/submission/1916/239873943

How would someone think of a solution for problem D during contest? It looks like a very specific observation to make.

i just check all squares some size and find this, uisng c++)

I did a brute force and find the answers for n=5. There are only 2 answers, one is the sample and the other has the multiset "16900". The fact that it contains two zeros made me feel it a key to the solution. Then everything is trivial.

D was despicable. It looks like someone reverse-engineered the fact that you can add 0's between 1 and 3 and still get something that looks like 169, and built a whole problem about that. This type of problem is intensely annoying; while verifying and using the pattern is trivial, finding it is often torturous and menial.

Personally the way I found it was by noticing that n is always odd, so maybe it doesn't work in evens because solution wants us to multiply by 100 which is a square, and then i permuted 0's in 16900 and realized oh hey it's still a square sometimes.

Any square will be of the form: $$$(c_1.a+c_2.b)^2$$$

-> $$$N_i$$$ = $$$( c_1^2\cdot a^2 + (2\cdot c_1c_2)\cdot (ab) + c_2^2\cdot b^2 )$$$.

We'll keep $$$a,b$$$ as powers of $$$10$$$, so that the only digits in our answer are : $$$c_1^2,c_2^2,(2\cdot c_1\cdot c_2)$$$.

By obvious reasons, $$$c_1^2,c_2^2,(2\cdot c_1\cdot c_2)$$$ should be unique and $$$c_1^2,c_2^2,(2\cdot c_1\cdot c_2) \lt 9$$$

This gives us the value of $$$c_1,c_2$$$ to be either of $$$1,3$$$.

Now, any number will have $$${1,6,9}$$$ and their length and relative position can be adjusted by using suitable powers of $$$10$$$ as values of $$$a,b$$$. The rest is trivial ig.

Alternative solution for D:

Here

In problem D, it seems that there is no answer for n which is even, can anyone prove this?

I have found through brute force programs that there are existential answers when $$$n$$$ is partially even, for example when $$$n = 8$$$ we have the following squares numbers that fit the requirements:

At the same time, it can be verified that $$$8$$$ is the minimum even number that satisfies solvability.

can problem E be done by dsu on tree?

Thanks for not restricting O(nmlog(n)) in F :)

Approach smjhado yrr

74traktor's editorial is Ultra annoying

Seems as if he is explaining his soln to himself, rather than someone else :/

My solution is based on the following observation(much like 74traktor):

Given a graph G with no articulation point, with Vertex set $$$V$$$, for any $$$v$$$ $$$\in$$$ V, you can always find a neighbor $$$n_v$$$ of $$$v$$$ such that contracting $$$n_v$$$ to $$$v$$$ edge, also leads to a graph with no articulation point.

Proof: Is a bit unstructured to write for now, will add it later.

Given this we can get an answer by the following algorithm:

Create a graph with all people as nodes and all friendly connections as edges. Given the above observation pick an arbitrary node $$$v$$$ and keep on contracting one of it's neighbors into $$$v$$$, $$$n_1 - 1$$$ times.

Label all nodes contracted into $$$v$$$ as computer scientists, and rest as mathematicians.

Why is this a valid solution?: Since we always merge two ends of an edge, all the nodes contracted in $$$v$$$ are connected, Hence all computer scientists are connected. Also since after all the contractions we still get a graph with no articulation points(by above property), removing $$$v$$$ from graph all other nodes are still connected, hence all mathematicians are also connected.

Thanks a lot. Very well explained!

I think we can prove it as follows:

Lets consider the case where all nodes connected to v(heavy node) are cut vertices, and letthesecut vertices form a set C. Lets condense any group of light(original) nodes into 1 node, which will still be a connected component if the a vertex in C is removed. Let these condensed nodes form a set D.The new graph has C + D + v vertices. We can see that no node in D, can connect 2 non-adjacent nodes in C, otherwise some vertex in C stops being cut. So since all nodes in D are only connecting adjacent nodes in C + v OR are leaves, we can remove them without hurting inter relation among nodes of C + v.

Finally, we could see that all vertices in C, among themselves: (should be a connected component + shouldn't form a cycle = should be a tree) + can't be leaves =

not possibleEdit: one correction

There is also a more straightforward solution to Problem D.

Initially my aim was to find a pattern by obtaining some other answers through a brute force program.

But I found a set of squares whose size is much larger than $$$99$$$.

This means that when $$$n$$$ is small we can preprocess the answer or brute force enumerate it, and when $$$n$$$ is large we can just add the corresponding number of zeros to the end of the numbers in this set to get the answer.

Here is an example of a set of squares with size $$$143$$$ when $$$n = 11$$$.

Spoiler10057482369, 10208475369, 10859307264, 12938607504, 13470852096, 13985427600, 14050783296, 14809673025, 15284376900, 15309607824, 15732684900, 16203507849, 16375809024, 17049830625, 17206093584, 17345680209, 17530289604, 17689532004, 18497360025, 20134758609, 20635897104, 20851937604, 20859736041, 20897015364, 21538497600, 21753890064, 23054170896, 23081509476, 24589376100, 25083907641, 25481736900, 25713084609, 25874009316, 25930016784, 25936780401, 26913058704, 27003691584, 27058934016, 27905368401, 28391576004, 28403709156, 29754180036, 30264517089, 30410825769, 30829741056, 30902475681, 31807652409, 32059618704, 32659718400, 34900217856, 35042716809, 35047209681, 35249687001, 35600897124, 35907218064, 36108740529, 36187452900, 36805271409, 37018529604, 37019684025, 37546812900, 37984061025, 38294576100, 38417960025, 38529764100, 39207564081, 40053217689, 40305782169, 40935810276, 41273985600, 41602537089, 41753200896, 43678910025, 45038601729, 45090823716, 45231080976, 45390728601, 48621573009, 48702310596, 49370618025, 50201987364, 50704681329, 51072836049, 52381476900, 52908740361, 52987436100, 53721968400, 53968400721, 54800937216, 54807960321, 54938672100, 57408639201, 58743216900, 58932417600, 59608734201, 59736248100, 60054893721, 61538724900, 62017435089, 62795348100, 64592730801, 65392718400, 65701480329, 67105348209, 67293548100, 67520983104, 68750413209, 68915700324, 69743528100, 69827534001, 70651234809, 70849130625, 71465328900, 71503829604, 73086419025, 73206501489, 73598264100, 74380016529, 74381652900, 74980130625, 76132950084, 76841503209, 78391040256, 79634018025, 80431796025, 80907251364, 82109756304, 82304150769, 82369574001, 82971650304, 84050127396, 84297315600, 84715923600, 85046307129, 85207361409, 86540107329, 87430210596, 87526039104, 89147030625, 90387416025, 92318745600, 98306704521, 98310467025

Here's my submission from the competition:239697493

I found a legal set for $$$n = 13$$$, and chose to preprocess the answer rather than brute-force it in the program because the answer was larger for $$$n = 11$$$.

nice one though :)

For the second question, Can anyone explain me how the p will be the smallest prime factor of x in b = a.p ? If you have some resources to study about it, share that too. Thanks in advance.

It is not difficult. Consider some basis in a k-dimensional subspace and n vectors. Which decompositions are suitable for us? For the first vector we will be satisfied with everything except 0, i.e. $$$(p^n - 1)$$$. For the second vector, everything is suitable except the expansion in the first vector, multiplied by a constant, so that there are 2 linearly independent vectors, i.e. $$$(p^n-p)$$$. And so on, we get

I'm sorry for my English(

Nice contest. Was problem E solvable in java with given time limits? zwezdinv. I think I did exactly what's mentioned in editorial in 239700440, but couldn't get it to pass.

check this submission

Bad round but good editorial.

video sol for (

Problem E — Happy Life in University) (Hindi Audio): Youtube LinkIn an interesting way such that a newbie could also understand.

Topic used :

Euler Tour, Segment TreeLazy RMQ (Range maximum query)) ;Nice explanation. Keep up the good work!

D could be made pretty easy using precomputation of squares on a constraint of 1e6. and then usign it in every case to get all values corresponding to given length

Can anyone tell me where can I learn math for Cp? This round made me realize that I should learn.

I have understood D solution. But is there any other methods to do it or the more relevant question, how do I reach to such a solution. Like which topics shall i cover more?

In problem D, for the alternate solution, how would you know that at n = 11 you can generate 99 such answers? And how would you generate the squares in O(sqrt(10^n))?

guessing :/

Can anyone explain F? I did dfs from each node and cut whenever a dfs subtree has size n1 or n2 (240093733) and it says MLE.

Alternative way to think of the observation for

Problem Bfor the case when $$$b\;mod\;a = 0$$$.First, lets step back and think about $$$b$$$. If it has to be the biggest factor of $$$x$$$, what do you know about the quotient $$$x/b$$$ ?. We can claim that the quotient must be prime.

Proof by contradiction: If the quotient is composite, we can easily shift even one prime factor in the factorisation of the quotient into $$$b$$$ to get a yet bigger factor $$$b'$$$ of $$$x$$$. That would be a contradiction.On similar lines what should be the quotient $$$x/a$$$ if $$$a$$$ has to be the second largest factor of $$$x$$$ ? Well, it is clear that the quotient can be a prime or a composite both. If it is a prime, it must be different from $$$x/b$$$ and the rest is fine.

Let's focus on the case if $$$x/a$$$ is composite. For this case, we can claim that $$$a$$$ must divide $$$b$$$ and that the corresponding quotient must be a prime.

Proof by contradiction: Assuming the quotient is composite, we can certainly "shift" some factors into $$$a$$$ so as to get a larger $$$a'$$$. This possibilty of getting a larger $$$a'$$$ is infact unavoidable/guaranteed but that would defeat the constraints of the problem. So, the only way to make it work is iff this $$$a' = b$$$ and that this is theonly possible$$$a'$$$. This inturn implies that $$$b/a$$$ must be prime (because then there will only be a single prime factor available for the"shifting"into $$$a$$$. This way, $$$a' = b$$$ is deterministic/guaranteed). In any other case(that is $$$b/a$$$ being composite) there is another $$$a_{alt}$$$ between $$$a'$$$ and $$$b$$$.So, till now we are convinced that if $$$(b\;mod\;a = 0)$$$ then $$$(b/a)$$$ must be a prime number. This means we can choose any multiple of $$$b$$$ and that will still be divisible by $$$a$$$ too. But also by arguments in point 1, we will/can only consider prime-multiples of $$$b$$$ as prospective values of $$$x$$$.

Let us say we took $$$x = y\cdot b$$$ where $$$y$$$ is some prime. Also, lets say that $$$b/a = z$$$ where $$$z$$$ is some other prime (WHICH WE JUST PROVED). Now, we claim that it must be that $$$z = y$$$ or else $$$a$$$ won't be the second largest divisor of the chosen $$$x$$$.

Proof by contradiction: Note that $$$b \cdot y = a\cdot z\cdot y$$$. Assume $$$y \neq z$$$ then that would mean $$$a\cdot y$$$ divides $$$x$$$. But $$$a\cdot y > a$$$ which means we just found a new divisor between $$$a$$$ and $$$b$$$. This is a contradiction to the requirement of $$$a$$$ being second largest divisor of $$$x$$$.With this in mind, which prime-multiple of $$$b$$$ should we choose as the appropriate $$$x$$$ ? That exact-same prime which we get as the quotient $$$b/a$$$. If we don't do so, $$$a$$$ will not be the second largest divisor for any other prime-multiple of $$$b$$$.

In problem F: 'Otherwise, consider a cut vertex such that, if removed, at least one of the resulting components will not have any other cut vertices.' How do we prove that such cut vertex exists?

I came across the same question after reading the editorial

I'll write a stricter proof

Consider two sets of vertices $$$L$$$ and $$$R$$$, where $$$L \cup R = V$$$, $$$L \cap R = \varnothing$$$, $$$L = {1}$$$ at the beginning and $$$R$$$ is connected since there are no cut points. Now we can always choose a vertex $$$v \in R$$$, delete it and add it to $$$L$$$, while $$$L$$$ and $$$R$$$ remain connected (which is the invariant).

Let's look at non-cut vertices in $$$R$$$. If $$$L$$$ is connected to any, we can choose one arbitrarily and the invariant holds.

Now, let's suppose all the neighbors of $$$L$$$ in $$$R$$$ are cut vertices. If not all cut vertices are neighbors of $$$L$$$, any vertex that is not a neighbor of $$$L$$$ is a cut vertex in the starting graph,

which contradicts the statement.Otherwise, all cut vertices are neighbors of $$$L$$$ and we can build a tree on cut vertices and choose any list in this tree. This cut vertex is also a cut vertex in the starting graph, since the hanging strongly connected component is not connected to $$$L$$$ or other vertices in $$$R$$$,

which contradicts the statement.QED

74TrAkToR, maybe improve the editorial for problem F, please

Okay, we'll fix it.

solution to problem C

In each operation, there is a chance that the total sum (sum) could be reduced by 1. Player One's goal is to keep the sum as large as possible; Player Two's goal is to keep the sum as small as possible.

All actions of Player One aim to avoid triggering the operation that reduces 1; there are two conditions to achieve this: 1. Select two odd numbers; 2. Select two even numbers. Both of these operations will increase the value of even numbers in the array by 1;

Player Two aims to trigger the operation that reduces 1 as much as possible. There is only one condition to achieve this—select an odd and an even number. Since Player One's action will surely leave an even number, Player Two can select an odd number and the even number left over from Player One's previous round, triggering the operation that reduces 1 as long as there are odd numbers in the array. For this reason, Player One needs to reduce the number of odd numbers as much as possible. The optimal operation for Player One is to select two odd numbers because this can consume the largest number of odd numbers, and an even number must be left after this operation.

If there are still odd numbers in the array at this point, Player Two can trigger the operation that reduces 1. Therefore, during this entire process, if there are 3 odd numbers, Player Two can most certainly trigger the operation that reduces 1.

Through this analysis, we can understand that under the optimal operation of both players, the operation that reduces 1 must be triggered for every 3 odd numbers. Thus, all we have to calculate is the number of groups of three odd numbers, which is certainly the total loss in this game. At the same time, we need to consider whether the odd numbers left after grouping three odd numbers into a group will cause new losses. In this case, the number of odd numbers could only be 0, 1, or 2. We also need to consider whose turn it is at this time. Since Player One eliminates two odd numbers and Player Two eliminates one odd number to complete a group, any remaining odd numbers should be Player One's turn. Therefore, in this case, when the number of odd numbers is 0 or 2, the optimal solution for Player One is to eliminate the two odd numbers. When the number of odd numbers is 1, no matter whether the player chooses to eliminate it immediately (causing the sum to be reduced by 1) or escape and leave it to Player Two (who will certainly choose this odd number and the even number left from the last operation, causing the sum to be reduced by 1), the player will inevitably bear the cost of reducing the sum by 1. Thus, we learn that the answer for every k numbers is pre[k] — odd_num/3 + ((odd_num%3)&1).

Can someone please explain B? Also in the tutorial they said "First case: b mod a = 0" but 3%2 is not equal to 0. Please help me out

mod 3 is not 0 then we will follow the second case ans = a*b/gcd(a,b)

In B, I had a doubt, when b % a == 0, how do we know p is the smallest prime factor of x where p = b / a. Is it because a and b are largest divisor ?

Sorry, but there is an error in the editorial for problem D: it should say $$$(n-1)/2$$$ zeros instead of $$$(n-3)/2$$$ zeros. It sounds unimportant but this typo could confuse some people.

1916B - Two Divisors 240657753 My code was like that

If (LCM(A,B)==B) then print:=(B/A)*LCM(A<B) else print:= LCM(A<B)

The issue arises when A = 15 and B = 60, resulting in an output of 240. However, for 240, A should be 80, B should be 120. indicating that the solution is not optimal. Can anyone suggest an optimal solution?

The issue is that your input is not a valid case. There is no integer such that its two greatest divisors are 15 and 60. For anything to have a divisor of 60, it will have a divisor of 30, making your case invalid.

That being said, the code works successfully, and outputs the right value of 240 for the proper inputs A = 80, B = 120.

I have a similar code, can I send it to you?

I have a similar code, can I send it to you?

interesting

244455567 Can someone help me why this greedy algorithm doesnt work. I cant check the test inputs because ""wrong answer 30955th numbers differ — expected: '4', found: '6'""

Take a look at Ticket 17328 from

CF Stressfor a counter example.thank you!

In problem b, in second case, I can't understand this "gcd(a, b) = x / p.q". Help me please!