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.

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?

Can anybody explain me the first recurrence for problem D. I am not getting the idea behind it?

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.

Can someone explain the Mobius Inversion solution for Problem D? TIA.

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.

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).

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 ?

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 ?

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

1. 2,4,6 with group size 3
2. 3,6 with group size 2
3. 5 with group size 1

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.

is it rated?

Here's my code for D with sum of infinite geometric progressions.

How to solve E?

I don't know how to find matchings in a graph.

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).

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

I'm happy that my solution idea was correct :) Need to improve more implementation skill!

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?

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}}$$$

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;

In problem D, could you please explain how the findCount() method in the code works ?

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

In the solution to the C problem, why does he add MOD to the ans.