Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### Ashishgup's blog

By Ashishgup, history, 11 months ago, ,

I hope you guys enjoyed the contest and we hope to host another one soon! The next one will be more balanced :P

With that said, here are the tutorials:

Author: Ashishgup

C++ Code: 51651509

Java Code: 51651164

Author: Ashishgup

C++ Code: 51651887

Java Code: 51651375

Author: Ashishgup

C++ Code: 51652029

Java Code: 51651756

Author: Vivek1998299

C++ Code (Above Logic): 51652491

C++ Code (Mobius Inversion): 51652104

Author: Jeel_Vaishnav

Java Code: 51652167

Author: Jeel_Vaishnav

Java Code: 51652020

• +128

 » 11 months ago, # |   +4 Thanks for fast editorial !
 » 11 months ago, # |   0 What is insight of gcd for the solution of problem D? What leads us towards gcd? It is not described in the editorial.
•  » » 11 months ago, # ^ |   +3 I’m not sure what you’re asking. gcd is mentioned in the problem statement.
•  » » » 11 months ago, # ^ |   0 My bad. I read problem D, then read problem E and F and back to D again. By the time I forgot that sequence will terminate when gcd will be 1, and worked with problem D thinking "sequence will terminate, when the last number is 1".
 » 11 months ago, # |   +6 Can D be done by considering all primes separately and each prime makes an AGP. So sum of infinite AGP from length 2 to infinite? In the end add 1/m for length 1?
•  » » 11 months ago, # ^ |   0 Yeah. I did it like that
•  » » » 11 months ago, # ^ |   +3 Can you please write down the formula ?
 » 11 months ago, # |   +6 Can anybody explain me the first recurrence for problem D. I am not getting the idea behind it?
•  » » 11 months ago, # ^ |   +9 Let dp[x] is the expected number of steps to get a gcd of 1 if the gcd until now is x. Now you can choose from any of the m numbers i.e. from 1 to m to be the next number of the sequence. After choosing from any of the m numbers ( let the chosen number be k ) the gcd of the sequence of the numbers you have chosen becomes gcd(k,x). Obviously the new gcd is less than or equal to x. Therefore, the expected number of steps to get to a gcd of one after you have chosen the number k would be 1 + dp[gcd(k,x)]. Here we are adding 1 as expected length increases by one after we choose the number k and dp[gcd(k,x)] would give us the expected number of steps required to get to a gcd of 1 after choosing the number k. Doing this for the numbers from 1 to m and dividing by m would give us dp[x]. Therefore,${dp[x] = \sum_{j = 1}^m\left( \dfrac{(1+dp[gcd(j,x)])}{m} \right)}$ Which becomes, ${dp[x] = 1+\sum_{j = 1}^m\left( \dfrac{(dp[gcd(j,x)])}{m} \right)}$
•  » » » 11 months ago, # ^ |   0 So after having this recurrence, what's the answer exactly?
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 After we have choosen the first number $x$, the total $gcd$ becomes $x$ so the answer is $dp[x]$. Since we choose the first integer from $1$ to $m$ uniformly, The answer is $1+\sum_{i=1}^{m}\frac{dp[i]}{m}$. Note that the $+1$ term accounts for the first integer.
 » 11 months ago, # | ← Rev. 3 →   0 Can someone check if my solution for E is correct? It's not maximum matching.First, I find max mex for the given situation without considering updates. Here's how I do that: I go from $0$ to as far as I can go by randomly picking a club which has a member of the required potential. When I choose the $i$'th club for potential $j$, I make a directed edge from all other clubs who have a member with potential $j$ to $i$. Now, if I get stuck at some potential k, I will bfs from the unused clubs to find a club which has a member with potential $k$. Now, if the path to this club is like $p_{x}$ -> $p_{a_{1}}$ -> ... -> $p_{y}$, where $p_{x}$ is the unused club and $p_{y}$ has a member with potential $k$, I can replace $p_{a_{1}}$ with $p_{x}$, and $p_{a_{2}}$ with $p_{a_{1}}$ and so on. After this I update the edges of the graph as required. By the end, I will find the max mex for the given situation.Now, for updates: First notice that the max mex can only decrease or remain same. Now, I maintain the reverse of the graph I mentioned above, if a member from club $i$ is chosen for potential $j$, then I make a edge from club $i$ to every other club which also has a member with potential $j$. Now, for each member which leaves, we see if we were using this member in our chosen max mex, if not, we do nothing. If yes, then we bfs from this club to either find a club which is unused right now (in which case max mex remains same) or we find a used club from which we have taken a member with the highest potential (in this case max mex becomes this new potential). In both cases we update the entire graph again as required.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 I am not sure... I think your solution is very similar to maximum matching QwQ..
 » 11 months ago, # |   +45 Can someone explain the Mobius Inversion solution for Problem D? TIA.
•  » » 11 months ago, # ^ | ← Rev. 3 →   +29 Here's what I did:E[i] = The expected value of the length of the sequence such that $i$ is the gcd before terminating.The answer to this is: 2*(m/i)*(m-m/i)+3*(m/i)^2*(m-m/i)+......This can be calculated as the sum of AGP.Now, this also includes sequences where 2*i and 3*i and so on are GCD's. So, subtract them from E[i]. E[i]-=E[2*i]E[i]-=E[3*i] and so on..Refer this submission.
•  » » » 11 months ago, # ^ |   +5 Thank you.
•  » » » 11 months ago, # ^ |   0 Can you please tell me the derivation of this AGP?
•  » » » » 11 months ago, # ^ |   -11
 » 11 months ago, # |   +19 For problem D, can someone show the mathematical steps that use mobius inversion and justify the equation used in the mobius-based solution code.
 » 11 months ago, # |   +71 About the möbius solution in D.Let me explain the solution with an example. Suppose we were to start out with the number $6$. Then the game could go many different ways, for example the gcd could be$6 \rightarrow 2 \rightarrow 2 \rightarrow 1$or $6 \rightarrow 6 \rightarrow 3 \rightarrow 3 \rightarrow 1$.So what decides the length of the game is how many turns you survive by either keep getting a random even number or by getting a random number divisible by 3. So it is almost $\text{length of game} = (\text{random numbers divisible by }2 \text{ in a row}) + (\text{random numbers divisible by }3 \text{ in a row})$. But that would over count as sometimes the random numbers are divisible by both $2$ and $3$. So the actual formula for starting value $6$ is$(\text{random numbers divisible by }2 \text{ in a row}) + (\text{random numbers divisible by }3 \text{ in a row}) - (\text{random numbers divisible by }6 \text{ in a row})$.This generalized will give the möbius solution.
•  » » 11 months ago, # ^ | ← Rev. 3 →   +47 The generalized version: The length of the game can be contributed to how many random numbers that are generated in a row that have $gcd > 1$. So the expected length of the array is given by $1 + E(\text{#randomly generated numbers in a row: }gcd > 1)$Note that at any time during the game the $gcd$ could be divisible by for example 2, or maybe 3, or maybe both. We can use this to calculate the probabilty that the $gcd>1$.Formally, let $A = \{\text{event that }gcd > 1\}$, and let $A(x) = \{\text{event that }x \mid gcd\}$, then using the inclusion exclusion principle $A = \sum_p A(p) - \sum_{p1} (-\mu(i)) A(i)$here $p,q,s,...$ denotes primes and $\mu(i)$ is the Möbius $\mu$ function. This equation tells us how to calculate the probability that the $gcd > 1$ by using the probabilities that the $gcd$ is divisible by some number $i>1$. These probabilities can pretty easily be calculated because to make the $gcd$ divisible by $i$ every random number generated must be divisible by $i$.With this we can give the final formula, the expected length of the array is $1 + E(\text{#randomly generated numbers in a row: }gcd > 1)$ $= 1 + \sum_{i>1} (-\mu(i)) E(\text{#randomly generated numbers in a row: }i\mid gcd)$and by noting that the distribution of the $(\text{#randomly generated numbers in a row: }i\mid gcd)$ follows a negative binomial distribution we get that $E(\text{#randomly generated numbers in a row: }i\mid gcd) = \frac{P(i \mid \text{randomly generated number})}{1 - P(i \mid \text{randomly generated number})}$(here is an implementation in python)
•  » » » 11 months ago, # ^ |   +8 Thank you very much for your idea.I learned a lot from this.
•  » » » 11 months ago, # ^ |   0 Impressive... Thanks for the explanation.Most of things make sense to me, but I do not understand how the final answer $E(\text{#randomly generated number}| gcd(\text{except the last one}) > 1 \land gcd(\text{all of them}) = 1)$ can be written as $1 + E(\text{#randomly generated numbers in a row: }gcd > 1)$. Can you explain it further? (Sorry I am not good at probabilities and statistics...)
•  » » » » 11 months ago, # ^ |   0 Of course you can, because when you append element to the array, they have gcd(all) > 1. After you append the last element, the gcd(all) = 1, so you need plus 1 for the last element.
•  » » » » » 11 months ago, # ^ |   0 Oh thank you. I was having a brain fart... It is actually not hard to understand...
•  » » » 5 months ago, # ^ |   0 can anyone explain the reason for negative mu(i) in the expression?
 » 11 months ago, # | ← Rev. 6 →   0 Thanks! One typo: For C, "black sequences" should read "BAD sequences". (These are actually the RED ones without black.)PS: One could mention that it is crucial that there is no cycle in the graph. I was first blocked because I didn't see that we have this, and I wondered how I can be sure that, if I have an "only red" path from A to B, there cannot be different, shorter path from A to B going through a black node (given that the problem makes precise that one has to use the shortest path -- so I feared that the "only red" path might not be the shortest one).
•  » » 11 months ago, # ^ |   0 Yes it is important that trees are acyclic, that is, every pair of points has a unique shortest path.
 » 11 months ago, # |   +1 Can anyone please explain where the very first recurrence in D came from? Also, the alternative solution (presumably using inclusion-exclusion) is still a bit of a mystery.
 » 11 months ago, # |   0 in problem E the matching is maximum matching ?
•  » » 11 months ago, # ^ |   0 please say me , i want to solve it as soon as possible that i can
•  » » » 10 months ago, # ^ |   +3 Yes, It is a maximum matching problem more specifically a maximum bipartite matching problemyou can find a code sample and a tutorial for it here: https://e-maxx.ru/algo/kuhn_matching
 » 11 months ago, # |   0 In B, instead of taking all candies, if it was possible to take a prefix of array instead of all the candies, what would be an optimal algorithm to solve it other than O(n^2)
 » 11 months ago, # |   +1 I even don't know what mobius is.
 » 11 months ago, # |   0 In problem B : the solution says that we should move greedily from the back. However from the problem statement it can be inferred that it is not necessary to include all the types in your solution. If say for the following array : [1 , 3, 5 ,6 , 2, 1]. In 0 based indexing, we can exclude [4,5] range and only include the numbers from [0.3](and then make sure that we follow all the constraints in the question). Did I understand the question wrong ?
•  » » 11 months ago, # ^ |   +3 Yeah too started solving with this approach of yours, but by "not necessary to include all the types", they meant saying few/all candies be 0. but there can't be any arr[j]>arr[i] for i>j for all i&j pairs as per constraints. So final array will have gauranteed maximum as the rightmost, and thus the greedy approach.
•  » » » 11 months ago, # ^ | ← Rev. 4 →   0 not getting. This cant be the test case?? TestCase : 10 2 // ans =3 // expected ans =10
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 This was evil question :D So basically the algo works only because if you don't buy for example xi amount of type i of candy, according to the question it is equivalent to buy 0 candies of type i so the all j's before i needs to be 0. I didn't get that at first. I was angry that for example if i have [4,50,5,7,6] the answer is not [4,50] because i didn't get at first that [4,50] actually means [4,50,0,0,0] which obviously do not satisfy constraints. So to quickly recap first the question states that "if you buy xi" then al j's need to be smaller or zero. So you think that if you do not buy then there are no constraints for that i. And then from the line 0<=xi<=ai you need to figure out that actually not buying still means buying 0 amount:D
 » 11 months ago, # |   +3 Why can't D be modeled as a sum of infinite arithmetic Geometric series.My approach:Form groups of numbers having gcd !=1 so, For each group expected length having some numbers (possibly zero) from the current group and atleast 1 number form some other group. For example if M=6 then there would be 3 distinct groups 2,4,6 with group size 3 3,6 with group size 2 5 with group size 1 Let x be the size of the group and y be m-xthen for each group the expected length would bey/m (If zero elements from this group are present) + 2*(x/m)^2 + 3*(x/m)^3 + ......upto infinityThis series (apart from the first term) is a infinite arithmetic geometric series with a=2 r=x/m d=1.When I implemented this using infinite sum formula, got a WA verdict.Can anybody explain me where exactly I went wrong.
•  » » 11 months ago, # ^ |   +5 Let’s say we’re trying to calculate the expected length of the first group. By your reasoning, it means that we take all numbers from the first group and then one number from another group. One such sequence could be {6, 6, 6, ..., 6, 3} (we take all sixes from the first group and one 3 from the second group). As you can see, the gcd of this sequence is not equal to 1, therefore it is invalid.
•  » » » 11 months ago, # ^ |   0 Thank you, got it.
 » 11 months ago, # |   0 is it rated?
•  » » 11 months ago, # ^ |   +6 is this an attempt to get downvotes?
•  » » » 11 months ago, # ^ |   0 seems like i failed .. ))
 » 11 months ago, # |   +8 Here's my code for D with sum of infinite geometric progressions.
•  » » 11 months ago, # ^ |   +9 Can you please explain the approach
•  » » » 11 months ago, # ^ | ← Rev. 3 →   +20 Let $P(E)$ denote the probability that event $E$ happens. The expected value of $len$ is: $1+\sum\limits_{x=1}^{\infty} P(len>x)$$Notice that $len>x$ means that the first $x$ numbers aren't coprime. Let's try to calculate $P(len>x)$. $P(len>x)=\sum\limits_{i=2}^{m} P(gcd\;of\;the\;first\;x\;numbers\;is\;i)$$Let $ans_i=\sum\limits_{x=1}^{\infty} P(gcd\;of\;the\;first\;x\;numbers\;is\;i)$. Then, combining the equations, our answer is $1+\sum\limits_{i=2}^{m} ans_i$. How to calculate $ans_i$? To calculate the probability that the $gcd$ of the first $x$ numbers if $i$, we can calculate the probability that it's a multiple of $i$, and then subtract the probability that it's a multiple of $i$ not equal to $i$. In math: $ans_i=\sum\limits_{x=1}^{\infty} P(all\;first\;x\;numbers\;are\;multiples\;of\;i)-\sum\limits_{j=2}^{\lfloor\frac{m}{i}\rfloor} ans_{j*i}$$Since there are $\lfloor\frac{m}{i}\rfloor$ multiples of $i$: $P(all\;first\;x\;numbers\;are\;multiples\;of\;i)=(\frac{\lfloor\frac{m}{i}\rfloor}{m})^x$$So if you loop from the end to the start, the first part of calculating $ans_i$ is a sum of an infinite geometric progression, and the second part is already calculated!PS: there's a formatting bug in codeforces: the first thing I write in math mode after a "" isn't rendered correctly. I partially solved it, but see rev. 2.
•  » » » » 11 months ago, # ^ |   0 A very nice approach, thank you!
•  » » » » 11 months ago, # ^ |   0 I saw the relationship between the Mobius solution and this one, but I wasn't intuitively feeling good with the inclusion-exclusion on the expectation of the length (on the Mobuis solution). However, your first line reminds me that we can split it into probability for each one more number, and everything starts to make sense! Thanks!
•  » » » » 11 months ago, # ^ |   0 such a nice explanation just need one clarification which formula are you using for infinite geometric sum? like a+a^2+a^3+....= a/1-a this is the formula that I know but I'm not able to understand the sum part of your code can you explain a bit?
•  » » » » » 11 months ago, # ^ |   +1 Sure. $\sum\limits_{x=1}^{\infty} P(all\;first\;x\;numbers\;are\;multiples\;of\;i)$ $=\sum\limits_{x=1}^{\infty} (\frac{\lfloor\frac{m}{i}\rfloor}{m})^x$ $=\frac{1}{1-\frac{\lfloor\frac{m}{i}\rfloor}{m}}-1$
•  » » » » » » 11 months ago, # ^ |   0 thank you for your nice detailed simple explanation because of you now I'm able to submit the solution and learned a lot <3
•  » » » » 11 months ago, # ^ |   0 I don't know why the expected value of len is 1+sigma(P(len>x)).Could you give some tips?
 » 11 months ago, # |   +4 How to solve E? I don't know how to find matchings in a graph.
•  » » 11 months ago, # ^ |   +3 in Chinese way, it is called 匈牙利算法, or you can google it. If you can not understand, you can use dinic to solve it.
 » 11 months ago, # | ← Rev. 2 →   0 What's wrong with this idea for D : g(i) is number of multiples of i <= m For expected len 1 : take 1 with p=1/mFor exp len 2 : sum of i [{g(i)*(n-g(i))}/(m^2)]For exp len 3 : sum of i [{g(i)*g(i)*(n-g(i))}/(m^3)]Continuing this and Then arranging them to form Arithmetic-Geometric Progression(AGP).
 » 11 months ago, # |   0 static void dfs(int i) { vis[i] = 1; cnt++; for(int j : adj[i]) { if(vis[j] == 0) dfs(j); } } Can anyone explain me the use of this function/method of question C. Thanks
•  » » 11 months ago, # ^ |   0 If you set cnt=0 before calling the function dfs(v), after the call it gives you number of connected vertices connected to v inclusive.
 » 11 months ago, # |   0 I'm happy that my solution idea was correct :) Need to improve more implementation skill!
•  » » 11 months ago, # ^ |   +1 Thats why i dont take part in contest where the setter is indian , they dont reply to ur doubts although being a problem setter
 » 11 months ago, # |   0 I understand everything about problem D completely but can anyone tell me how to find for all i from 2 to m for all divisors of i and find the total count of numbers b/w [1,m] such that gcd b/w the p belongs to [1,m] and i is that divisor. Find total count such that gcd(p,i)=divisor of i we have to do this for all divisors of i and for all i from 1 to m. Sorry for my poor English e.g for m=10 the list wiil be 5 2 1 7 3 1 5 4 1 3 4 2 8 5 1 3 6 1 4 6 2 2 6 3 9 7 1 5 8 1 3 8 2 1 8 4 7 9 1 2 9 3 4 10 1 4 10 2 1 10 5 Here 1st column is the count 2nd column is i and third column is the divisor of i.
 » 11 months ago, # |   0 Any good tutorial on bipartite matchings ! if any one has can please share it with me . Thanks !
 » 11 months ago, # |   0 In the c++ code of the C no problem,i have not understood line: ans += MOD; ans %= MOD; can anyone tell why it is done?
•  » » 11 months ago, # ^ |   0 if ans is negtive, ans%mod is negtive, and if you want positive ans, you should add mod to ans to get positive ans.(-2)%5 = -2; (-2+5)%5 = 3;
•  » » » 11 months ago, # ^ |   0 Thanks.... Can you please tell me how this process gives the correct answer for this problem?
 » 11 months ago, # | ← Rev. 2 →   0 Here is a question for problem E: Would it work if we consider the queries in the originally order? When we want to delete some vertices and edges in the graph, we unmatch the edge if it is already matched. Then we run the matching algorithm again. I think the complexity here will still be $O(5000 \cdot 5000)$. Is that right? The implementation will be harder though.
 » 11 months ago, # |   +7 hello,I think the second formula on question D should be like this. $dp[x] =1+ \sum_{y \in divisors(x)}{\frac{dp[y] \cdot f(y,x)}{m}}$
•  » » 11 months ago, # ^ |   0 Thanx ..updated
 » 11 months ago, # |   0 Can anyone explain the first code in D problem's Tutorial .There is a sentance in main(): ll cnt=m/i; dp[i]=rhs*m%mod*pow_mod(m-cnt,mod-2,mod)%mod; 
•  » » 11 months ago, # ^ |   +1 The cnt of p which gcd(p, x) = x, p is multiple of x, and the cnt = m /i; so move the cnt / m * dp[x] to lhs, we get (1- cnt/m) dp[x]= rhs, so dp[x] = m /(m-cnt)*rhs. then Fermat's little theorem.
•  » » » 11 months ago, # ^ |   0 Thank you very much .I think I have completed understood.
 » 11 months ago, # | ← Rev. 5 →   0 I'm not able to understand the solution of problem E also I don't understand JAVA code. Can anyone share their approach with their C++ code
 » 11 months ago, # |   0 In problem D, could you please explain how the findCount() method in the code works ?
•  » » 11 months ago, # ^ |   +1
•  » » » 11 months ago, # ^ |   0 Thanks!
 » 10 months ago, # |   0 just testing $x^3 + y^3 \neq z^3$
 » 8 months ago, # | ← Rev. 3 →   0 For problem E I used this matchmaking technique.I implemented the same and acc. to me my code is having complexity o(n^2) but got TLE on test 24. The way I calculated the complexity is bpm is like dfs so bpm is o(n) hence match is also o(n) and match will be called maximum n time hence total is o(n^2)please correct me where am I wrong and also tell the correct algo to be used for match making. @Jeel_Vaishnav @Ashishgup
 » 6 months ago, # |   0 can anyone please tell me the meaning of these lines :--------"So if the size of the current component is p, then we have pk bad sequences corresponding to this connected component.Thus, the overall answer is nk−∑pk where p is the size of different connected components, considering only red edges." I DO NOT KNOW HOW DOES THIS FORMULA GIVING CORRECT ANSWER AND HOW TO THINK THIS FORMULA