### Ashishgup's blog

By Ashishgup, history, 18 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 Tutorial of Codeforces Round #548 (Div. 2) 548, div2, Comments (84)
 » Thanks for fast editorial !
 » What is insight of gcd for the solution of problem D? What leads us towards gcd? It is not described in the editorial.
•  » » I’m not sure what you’re asking. gcd is mentioned in the problem statement.
•  » » » 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".
 » 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?
•  » » Yeah. I did it like that
•  » » » Can you please write down the formula ?
 » Can anybody explain me the first recurrence for problem D. I am not getting the idea behind it?
•  » » 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)}$
•  » » » So after having this recurrence, what's the answer exactly?
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   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.
 » 18 months ago, # | ← Rev. 3 →   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.
•  » » 18 months ago, # ^ | ← Rev. 2 →   I am not sure... I think your solution is very similar to maximum matching QwQ..
 » Can someone explain the Mobius Inversion solution for Problem D? TIA.
•  » » 18 months ago, # ^ | ← Rev. 3 →   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.
•  » » » Thank you.
•  » » » Can you please tell me the derivation of this AGP?
•  » » » »
 » For problem D, can someone show the mathematical steps that use mobius inversion and justify the equation used in the mobius-based solution code.
 » 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.
•  » » 18 months ago, # ^ | ← Rev. 3 →   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)
•  » » » Thank you very much for your idea.I learned a lot from this.
•  » » » 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...)
•  » » » » 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.
•  » » » » » Oh thank you. I was having a brain fart... It is actually not hard to understand...
•  » » » can anyone explain the reason for negative mu(i) in the expression?
 » 18 months ago, # | ← Rev. 6 →   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).
•  » » Yes it is important that trees are acyclic, that is, every pair of points has a unique shortest path.
 » 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.
 » in problem E the matching is maximum matching ?
•  » » please say me , i want to solve it as soon as possible that i can
•  » » » 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
 » 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)
 » I even don't know what mobius is.
 » 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 ?
•  » » 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.
•  » » » 18 months ago, # ^ | ← Rev. 4 →   not getting. This cant be the test case?? TestCase : 10 2 // ans =3 // expected ans =10
•  » » 17 months ago, # ^ | ← Rev. 2 →   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
 » 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.
•  » » 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.
•  » » » Thank you, got it.
 » is it rated?
•  » » is this an attempt to get downvotes?
•  » » » seems like i failed .. ))
 » Here's my code for D with sum of infinite geometric progressions.
•  » » Can you please explain the approach
•  » » » 18 months ago, # ^ | ← Rev. 3 →   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.
•  » » » » A very nice approach, thank you!
•  » » » » 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!
•  » » » » 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?
•  » » » » » 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$
•  » » » » » » thank you for your nice detailed simple explanation because of you now I'm able to submit the solution and learned a lot <3
•  » » » » I don't know why the expected value of len is 1+sigma(P(len>x)).Could you give some tips?
•  » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   $ExpectedLength = 1 \times P(len=1) + 2 \times P(len=2) + 3 \times P(len=3) + 4 \times P(len=4) + ...$Notice that $P(len>i) = P(len=i+1) + P(len=i+2) + P(len=i+3) + ...$Now let's group the terms in the right hand side of the first equation so that the term $P(len>i)$ appears. I'll try with $i=0$ and $i=1$ and surely you will see how the next $i$ appear.Here I just take out one $P(len=i)$ of each term and sum them up. This sum covers all the probabilities and thus equals 1. Therefore: $ExpectedLength = 1 + 1 \times P(len=2) + 2 \times P(len=3) + 3 \times P(len=4) + 4 \times P(len=5) + ...$Next take out one $P(len=i)$ of each term again $ExpectedLength = 1 + P(len>1) + 1 \times P(len=3) + 2 \times P(len=4) + 3 \times P(len=5) +...$Continue doing it till infinity and you get the $Expected_length = 1 + P(len>1) + P(len>2) + P(len>3) + ...$Hope that this helps even after 16 months :)
•  » » » » » » Thanks a lot!This is very helpful
 » How to solve E? I don't know how to find matchings in a graph.
•  » » in Chinese way, it is called 匈牙利算法, or you can google it. If you can not understand, you can use dinic to solve it.
 » 18 months ago, # | ← Rev. 2 →   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).
 » 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
•  » » 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.
 » I'm happy that my solution idea was correct :) Need to improve more implementation skill!
•  » » Thats why i dont take part in contest where the setter is indian , they dont reply to ur doubts although being a problem setter
 » 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.
 » Any good tutorial on bipartite matchings ! if any one has can please share it with me . Thanks !
 » 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?
•  » » 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;
•  » » » Thanks.... Can you please tell me how this process gives the correct answer for this problem?
 » 18 months ago, # | ← Rev. 2 →   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.
 » 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}}$
•  » » Thanx ..updated
 » 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; 
•  » » 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.
•  » » » Thank you very much .I think I have completed understood.
 » 18 months ago, # | ← Rev. 5 →   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
 » In problem D, could you please explain how the findCount() method in the code works ?
•  » »
•  » » » Thanks!
 » just testing $x^3 + y^3 \neq z^3$
 » 15 months ago, # | ← Rev. 3 →   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
 » 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
 » in problem C i was getting wrong answer during my practice ans so i added (ans += mod ;) this line and it went ac could somebody tell me why its necessaray ig its there for somehow dealing with negative nos but dont know the exact reason behind it, thanks in advance
•  » » yes, it is exactly necessary in order to deal with negative values. As we work with the remainders of real values, it is possible the remainder of total sequences is smaller than the remainder of bad sequences.
 » In the solution to the C problem, why does he add MOD to the ans.
•  » » If you do (num%mod), then the value will be in the range of 0 to mod-1. Hence if you got a negative number somehow, then you have to add mod into our result. Because, (num+mod)%mod = ((num%mod)+(mod%mod))%mod = (num%mod+0)%mod = num%mod. Which will be positive. Hence we have to add the mod in negative number until it becomes positive.