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:
Tutorial is loading...
Author: Ashishgup
C++ Code: 51651509
Java Code: 51651164
Tutorial is loading...
Author: Ashishgup
C++ Code: 51651887
Java Code: 51651375
Tutorial is loading...
Author: Ashishgup
C++ Code: 51652029
Java Code: 51651756
Tutorial is loading...
Author: Vivek1998299
C++ Code (Above Logic): 51652491
C++ Code (Mobius Inversion): 51652104
Tutorial is loading...
Author: Jeel_Vaishnav
Java Code: 51652167
Tutorial is loading...
Author: Jeel_Vaishnav
Java Code: 51652020
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?
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.
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.
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.
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?
https://en.wikipedia.org/wiki/Arithmetico%E2%80%93geometric_sequence
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.
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?
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.
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
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
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
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
(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?
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 problem
you 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.
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
Let x be the size of the group and y be m-x
then for each group the expected length would be
y/m (If zero elements from this group are present) + 2*(x/m)^2 + 3*(x/m)^3 + ......upto infinity
This 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?
Here's my code for D with sum of infinite geometric progressions.
Can you please explain the approach
Let $$$P(E)$$$ denote the probability that event $$$E$$$ happens. The expected value of $$$len$$$ is:
$
Notice that $$$len>x$$$ means that the first $$$x$$$ numbers aren't coprime. Let's try to calculate $$$P(len>x)$$$.
$
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:
$
Since there are $$$\lfloor\frac{m}{i}\rfloor$$$ multiples of $$$i$$$:
$
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.
I don't know why the expected value of len is
1+sigma(P(len>x))
.Could you give some tips?Notice that
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:
Next take out one $P(len=i)$ of each term again
Continue doing it till infinity and you get the
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.
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/m
For 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).
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.
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;
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():
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.
In problem D, could you please explain how the findCount() method in the code works ?
https://cp-algorithms.com/combinatorics/inclusion-exclusion.html#toc-tgt-11
Thanks!
just testing $$$x^3 + y^3 \neq z^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
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.
but isnt it assured that we wont get a negative ans? since the no of sequences can never be less than 0
no of sequences can not go negative but we are calculating no of sequences using modular arithmetic.
exp: