Ashishgup's blog

Codeforces Round #548 Editorial
By Ashishgup, history, 6 years ago, In English

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

  • Vote: I like it
  • +128
  • Vote: I do not like it

Comments Comments (80)
| Write comment?
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Thanks for fast editorial !

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is insight of gcd for the solution of problem D? What leads us towards gcd? It is not described in the editorial.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I’m not sure what you’re asking. gcd is mentioned in the problem statement.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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?

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like 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)}$$$

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So after having this recurrence, what's the answer exactly?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like 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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I am not sure... I think your solution is very similar to maximum matching QwQ..

    → Reply
»
6 years ago, # |
  Vote: I like it +45 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +29 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thank you.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please tell me the derivation of this AGP?

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

For problem D, can someone show the mathematical steps that use mobius inversion and justify the equation used in the mobius-based solution code.

→ Reply
»
6 years ago, # |
  Vote: I like it +71 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +47 Vote: I do not like it

    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_{p<q} A(p) \cap A(q) + \sum_{p<q<s} A(p) \cap A(q) \cap A(s) - \ldots $$$
    $$$ = \sum_p A(p) - \sum_{p<q} A(p q) + \sum_{p<q<s} A(p q s) - \ldots $$$
    $$$ = \sum_{i>1} (-\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)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thank you very much for your idea.I learned a lot from this.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh thank you. I was having a brain fart... It is actually not hard to understand...

          → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can anyone explain the reason for negative mu(i) in the expression?

      → Reply
»
6 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes it is important that trees are acyclic, that is, every pair of points has a unique shortest path.

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem E the matching is maximum matching ?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I even don't know what mobius is.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is it rated?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    is this an attempt to get downvotes?

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Can you please explain the approach

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +20 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        A very nice approach, thank you!

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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!

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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$$$
          → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know why the expected value of len is 1+sigma(P(len>x)).Could you give some tips?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it
          $$$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 :)

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks a lot!This is very helpful

            → Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve E?

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    in Chinese way, it is called 匈牙利算法, or you can google it. If you can not understand, you can use dinic to solve it.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like 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).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thats why i dont take part in contest where the setter is indian , they dont reply to ur doubts although being a problem setter

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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;

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much .I think I have completed understood.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

just testing $$$x^3 + y^3 \neq z^3$$$

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • 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.
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but isnt it assured that we wont get a negative ans? since the no of sequences can never be less than 0

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        no of sequences can not go negative but we are calculating no of sequences using modular arithmetic.

        exp:

        1. w/ Modular arithmetic: (4 ^ 3) % 7 — (3 ^ 3) % 7 = 64 % 7 — 27 % 7 = 1 — 6 = -5
        2. w/o Modular arithmetic: (4 ^ 3) — (3 ^ 3) = 64 — 27 = 37
        → Reply