### Ashishgup's blog

By Ashishgup, history, 5 years 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

| Write comment?
 » 5 years ago, # |   +4 Thanks for fast editorial !
 » 5 years 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.
•  » » 5 years ago, # ^ |   +3 I’m not sure what you’re asking. gcd is mentioned in the problem statement.
•  » » » 5 years 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".
 » 5 years 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?
•  » » 5 years ago, # ^ |   0 Yeah. I did it like that
•  » » » 5 years ago, # ^ |   +3 Can you please write down the formula ?
 » 5 years ago, # |   +6 Can anybody explain me the first recurrence for problem D. I am not getting the idea behind it?
•  » » 5 years 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)}$
•  » » » 5 years ago, # ^ |   0 So after having this recurrence, what's the answer exactly?
•  » » » » 5 years 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.
 » 5 years 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I am not sure... I think your solution is very similar to maximum matching QwQ..
 » 5 years ago, # |   +45 Can someone explain the Mobius Inversion solution for Problem D? TIA.
•  » » 5 years 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.
•  » » » 5 years ago, # ^ |   +5 Thank you.
•  » » » 5 years ago, # ^ |   0 Can you please tell me the derivation of this AGP?
•  » » » » 5 years ago, # ^ |   -11
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 from ur method how can we ensure that sequence "such that i is the gcd before terminating" will end up having gcd 1.like we can't say gcd(multiple of i,non-multiple of i) is always 1.(m-m/i) is the no. of non multiple of i and m/i is no. of multiple of i.
•  » » » 2 years ago, # ^ |   0 Yeah, can someone explain why it makes sure that "that i is the gcd before terminating." Because for example if i=15, then the m-m/i includes numbers like 3 and gcd(3,15) is not 1, so this formula should not work right?
 » 5 years 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.
 » 5 years 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.
•  » » 5 years 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)
•  » » » 5 years ago, # ^ |   +8 Thank you very much for your idea.I learned a lot from this.
•  » » » 5 years 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...)
•  » » » » 5 years 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.
•  » » » » » 5 years ago, # ^ |   0 Oh thank you. I was having a brain fart... It is actually not hard to understand...
•  » » » 5 years ago, # ^ |   0 can anyone explain the reason for negative mu(i) in the expression?
 » 5 years 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).
•  » » 5 years ago, # ^ |   0 Yes it is important that trees are acyclic, that is, every pair of points has a unique shortest path.
 » 5 years 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.
 » 5 years ago, # |   0 in problem E the matching is maximum matching ?
•  » » 5 years ago, # ^ |   0 please say me , i want to solve it as soon as possible that i can
•  » » » 5 years 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
 » 5 years 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)
 » 5 years ago, # |   +1 I even don't know what mobius is.
 » 5 years 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 ?
•  » » 5 years 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.
 » 5 years 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.
•  » » 5 years 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.
•  » » » 5 years ago, # ^ |   0 Thank you, got it.
 » 5 years ago, # |   0 is it rated?
•  » » 5 years ago, # ^ |   +6 is this an attempt to get downvotes?
 » 5 years ago, # |   +8 Here's my code for D with sum of infinite geometric progressions.
•  » » 5 years ago, # ^ |   +9 Can you please explain the approach
•  » » » 5 years 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.
•  » » » » 5 years ago, # ^ |   0 A very nice approach, thank you!
•  » » » » 5 years 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!
•  » » » » 5 years 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?
•  » » » » » 5 years 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$
•  » » » » 5 years ago, # ^ |   0 I don't know why the expected value of len is 1+sigma(P(len>x)).Could you give some tips?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 $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 :)
•  » » » » » » 4 years ago, # ^ |   0 Thanks a lot!This is very helpful
 » 5 years ago, # |   +4 How to solve E? I don't know how to find matchings in a graph.
•  » » 5 years 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.
 » 5 years 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).
 » 5 years 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
•  » » 5 years 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.
 » 5 years ago, # |   0 I'm happy that my solution idea was correct :) Need to improve more implementation skill!
•  » » 5 years 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
 » 5 years 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.
 » 5 years 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?
•  » » 5 years 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;
 » 5 years 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.
 » 5 years 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}}$
•  » » 5 years ago, # ^ |   0 Thanx ..updated
 » 5 years 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;
•  » » 5 years 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.
•  » » » 5 years ago, # ^ |   0 Thank you very much .I think I have completed understood.
 » 5 years ago, # |   0 In problem D, could you please explain how the findCount() method in the code works ?
•  » » 5 years ago, # ^ |   +1
•  » » » 5 years ago, # ^ |   0 Thanks!
 » 5 years ago, # |   0 just testing $x^3 + y^3 \neq z^3$
 » 5 years 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
 » 4 years ago, # |   0 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
•  » » 4 years ago, # ^ |   +1 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.
 » 4 years ago, # |   0 In the solution to the C problem, why does he add MOD to the ans.
•  » » 4 years ago, # ^ |   0 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.
•  » » » 21 month(s) ago, # ^ |   0 but isnt it assured that we wont get a negative ans? since the no of sequences can never be less than 0
•  » » » » 20 months ago, # ^ |   0 no of sequences can not go negative but we are calculating no of sequences using modular arithmetic.exp: w/ Modular arithmetic: (4 ^ 3) % 7 — (3 ^ 3) % 7 = 64 % 7 — 27 % 7 = 1 — 6 = -5 w/o Modular arithmetic: (4 ^ 3) — (3 ^ 3) = 64 — 27 = 37