divyamsingal01's blog

By divyamsingal01, 2 years ago, In English

So I did not find a tutorial for Maths section of CSES on codeforces, so thought of writing one.

I have put all my codes on https://github.com/div5252/CSES-Problem-Set.

This tutorial covers 29 questions of Mathematics Section of CSES.

1. Josephus Queries

Tutorial
Code

2. Exponentiation

Tutorial
Code

3. Exponentiation II

Tutorial
Code

4. Counting Divisors

Tutorial
Code

5. Common Divisors

Tutorial
Code

6. Sum of divisors

Tutorial
Code

7. Divisor Analysis

Tutorial
Code

8. Prime Multiples

Tutorial
Code

9. Counting Coprime Pairs

Tutorial
Code

10. Binomial Coefficients

Tutorial
Code

11. Creating Strings II

Tutorial
Code

12. Distributing Apples

Tutorial
Code

13. Christmas Party

Tutorial
Code

14. Bracket Sequences I

Tutorial
Code

15. Bracket Sequences II

Tutorial
Code

16. Counting Necklaces

Tutorial
Code

17. Counting Grids

18. Fibonacci Numbers

Tutorial
Code

19. Throwing Dice

Tutorial
Code

20. Graph Paths I

Tutorial
Code

21. Graph Paths II

Tutorial
Code

22. Dice Probability

Tutorial
Code

23. Moving Robots

Tutorial
Code

24. Candy Lottery

Tutorial
Code

25. Inversion Probability

Tutorial
Code

26. Stick Game

Tutorial
Code

27. Nim Game I

Tutorial
Code

28. Nim Game II

Tutorial
Code

29. Stair Game

Tutorial
Code

30. Grundy's Game

Tutorial
Code

31. Another Game

UPD: I have also added tutorials for the newly added problems in Maths section. I am yet to do two problems — Counting Grids and Another Game. It would be helpful if someone could come up with tutorials for these.

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

| Write comment?
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks man...

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks a lot!

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

UPD: The tutorial is now complete. I have put the explanations and codes for all 21 problems.

If you find any typo or any improvement in the explanation, please comment below.

I haven't put the complete code(template portion) in the tutorial above, so as to prevent people for directly copying. Still if you wish to see the complete code, I have to the link to my github which contains AC solutions.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I still do not get sum of divisors :(

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

divyamsingal01 can you share the links to the editorials of other sections if you have found them?

»
2 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

can you please verify if i understood moving robots correctly —

for each robot we first get what is the probability for it to be on some i, j cell after k iterations.

then for each cell what is the probability that it was empty after k iterns? — probability that robot 1 isnt there * probability that robot 2 isnt there and so on.... so we multiply the 1 — dp[i1][j1]

now expectation — sum(P(xi)*xi) we calculated P(xi) and xi is 1?

»
2 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

For 21, here's a fairly straightforward proof:

This game is essentially equivalent to Nim with a restricted number of additions permitted, with the piles being on the even indices, and the permitted additions being precisely the ones which can be done due to the shift from the pile on the immediate right (if it exists), with the only other possible move being removal of one element from an even pile at most a finite number of times, and thus this game is equivalent to vanilla Nim (proof here: https://cp-algorithms.com/game_theory/sprague-grundy-nim.html#toc-tgt-5), from where it is obvious.

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

divyamsingal01

In Graph Paths II, how did you decide the value of INF?

I took INF=7e18 and it was giving WA, but on changing it to 4e18, it got Accepted!

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

    You might be having long long overflow due to 7e18. Initialize, it sufficiently large so that it serves its purpose and encounters no overflow scenario.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Mathematical Proof for Q21. It is a Staircase Nim Problem and can be easily proven that only even position value affects our answer. For the proof click here

»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Counting Necklaces How to get the inclusion/exclusion right?

Can sombody explain with example n=12?

»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone solved grundy's game ?

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In exponentiation II , why we use fermat's theorem ? Can't we just find x = power(b,c) and then power(a,x) ? I tried but it didn't work. So I want to know why? Note : I am not from Maths background so if you will share any resources it will be very useful.

  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's because $$$b^c$$$ will overflow (doesn't fit in long long), so we used Fermat's Theorem.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi In COUNTING DIVISORS (problem-4), I understand that an array of 0s is created and then each 0 in the array is incremented in the for-loops.

I want to know the rationale behind this. Why this works?

  • »
    »
    19 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Explained it here

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The program given there and even mine gives RE and TLE (at times) when i am executing.

      What's wrong in the code given there?

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Not mentioned in the snippet but value of $$$N$$$ is $$$10^6+1$$$. That could be the reason for RE.

»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For Another Game, the first player wins iff there is at least one heap with an odd number of coins.

If all heaps have an even number of coins, the second player can win, by taking coins from the same set of piles as the first player on the previous turn. This ensures that all heaps have an even number of piles at the end of the second player's turn, so the strategy can continue.

If at least one heap has an odd number of coins, the first player can win by taking one coin from each pile with an odd number of coins, reducing the game to the first scenario.

Proof of Stair Game is as follows:

Consider the nim game on the even-numbered piles. If the first player wins this game, they can win the entire game. A valid strategy:

  • In the first move, play in the even-numbered piles with an optimal nim strategy.

In subsequent moves:

  • If the second player moves coins from an odd-numbered pile $$$p$$$ to pile $$$p-1$$$, the first player should move the same number of coins from $$$p-1$$$ to $$$p-2$$$. Note that the nim game on the even-numbered piles is unaffected, and it is impossible for the first player to lose during this.

  • If the second player moves coins from an even-numbered pile, they have effectively made a move in the nim game, so the first player's next move should be to play an optimal move in the nim game.

After all the moves in the nim game have been exhausted, we know that the second player has the next move and that all coins are in odd-numbered piles, which means the first player ultimately wins using this strategy.

If the second player wins the nim game, use a similar strategy as the one above (i.e. if first player plays on odd-numbered pile, mirror their move; if they play on even-numbered pile, play nim game).

»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

17. Counting Grids

Tutorial
Code

(Sorry for the Necropost)

  • »
    »
    16 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    in case someone is wondering how to get $$$250000002$$$ without using online calculator

    Code
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for stair game, the proof is as follows:

say player A ( let it be first or second ) have winning strategy in the nim game you considered, how can A still have a winning strategy in the original game?

the new strategy is simple, when player B moves n coins from an odd-numbered stair k, A moves the same amount of coins from stair k-1 to k-2, this preserves the nim game; when B's move is on an even numbered stair, we proceed with our original strategy.

the way I found this property is through testing some possibilities for n = 1,2,3,4,5. Hope this helps!

»
16 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Another proof for Another Game:

  • $$$\lbrace 1 \rbrace$$$ is winning for you, just take the coin.

  • $$$\lbrace 2 \rbrace$$$ is losing, because you can only take one coin, leading to $$${1}$$$ for your opponent, which is winning.

  • $$$\lbrace \rbrace$$$ is losing, there are no moves to be done.

Let $$$E_{i,j}$$$ be a set which contains the multisets of any $$$i$$$ even nonzero numbers ($$$i \ge 1$$$), with their sum $$$j$$$ ($$$j \ge 2i$$$).

Also, let $$$E_{i,0} = \lbrace\lbrace\rbrace\rbrace$$$ for any $$$i \ge 1 \Rightarrow E_{i,0}$$$ contains only losing multisets for any $$$i \ge 1$$$.

(Induction A)

If $$$E_{1,j}$$$ (any $$$j \ge 2$$$), $$$E_{2,j}$$$ (any $$$j \ge 4$$$), .., $$$E_{i-1,j}$$$ (any $$$j \ge 2i-2$$$) all contain only losing multisets, we will prove by induction that $$$E_{i,2i}$$$ also contains only losing multisets.

$$$E_{i,2i}$$$ is only formed from the multiset $$$\lbrace 2, 2, 2, .., 2 \rbrace$$$ (i times)

Any move we will do will lead to $$$\lbrace 2, 2, .., 2 \rbrace$$$ (i-k times) ∪ $$$\lbrace 1, 1, 1, .., 1 \rbrace$$$ (k times) | $$$1 \le k \le i$$$

Our opponent will mimic our move, leading to:

$$$\lbrace 2, 2, .., 2 \rbrace$$$ (i-k times) $$$\in E_{i-k,2i-2k}$$$ , which we already claimed it is losing.

(Induction B)

If $$$E_{1,j}$$$ (any $$$j \ge 2$$$), $$$E_{2,j}$$$ (any $$$j \ge 4$$$), .., $$$E_{i-1,j}$$$ (any $$$j \ge 2i-2$$$), $$$E_{i,2i}$$$, $$$E_{i,2i+2}$$$, .., $$$E_{i,2k-2}$$$ all contain only losing multisets, we will prove by induction that $$$E_{i,2k}$$$ also contains only losing multisets.

Let $$$E \in E_{i,2k}$$$, $$$E = \lbrace e_1, e_2, .., e_i | e_1 + e_2 + .. + e_i = 2k \rbrace$$$

Any move we will do will lead to the following split of $$$\lbrace e_1, e_2, .., e_i \rbrace$$$: $$$\lbrace e_{a_{1}}, e_{a_{2}}, .., e_{a_{x}}} ∪ {e_{b_{1}}-1, e_{b_{2}}-1, .., e_{b_{y}}-1 \rbrace$$$ with $$$\lbrace a_1, a_2, .., a_x \rbrace ∪ \lbrace b_1, b_2, .., b_y \rbrace = \lbrace 1, 2, .., i \rbrace, x + y = i$$$.

Our opponent will mimic our move, leading to: $$$\lbrace e_{a_{1}}, e_{a_{2}}, .., e_{a_{x}}} ∪ {e_{b_{1}} - 2, e_{b_{2}} - 2, .., e_{b_{y}} - 2 \rbrace$$$, which $$$\in E_{i,2k-2y}$$$, which we have already claimed to be losing; since it is again our move, $$$E$$$ is losing.

Since $$$E_{1,2} = \lbrace\lbrace 2 \rbrace\rbrace \Leftrightarrow E_{1,2}$$$ contains only losing multisets, by applying (Induction B) (we can apply it, $$$\lbrace\rbrace$$$ is losing) $$$\Rightarrow E_{1,4}$$$, $$$E_{1,6}$$$, $$$E_{1,8}$$$, ... all contain only losing multisets.

So $$$E_{1,j}$$$ (any $$$j \ge 2$$$) contains only losing multisets. Now we apply (Induction A) $$$\Rightarrow$$$ $$$E_{2,4}$$$ contains only losing multisets.

We now apply (Induction B) again $$$\Rightarrow E_{2,6}$$$, $$$E_{2,8}$$$, $$$E_{2,10}$$$, ... all contain only losing multisets.

...

By continuing to repeatedly swap between (Induction B) and (Induction A), we can conclude that $$$E_{i,j}$$$ (any $$$i \ge 1$$$, any $$$j \ge 2i$$$) contains only losing multisets.

In other words, any multiset that contains only even numbers is losing.

If we start with even numbers only, we lose. Otherwise, during our first turn we will subtract $$$1$$$ only from the odd numbers we have, leaving our opponent with a losing configuration of even numbers only.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have spent over 2 hours over the Josephus Queries Problem, I find it to be most difficult, I can understand we have to halve the range and query for the next and modify the queried value accordingly to the parent caller. But still not able to formulate, It feels too random, what should I do, I want a solution with a proper explanation for EDGE cases :(

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hope this helps. Josephus Queries seems to be modified version of standard Josephus Problem.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me Q.2 Why to do "mod-1" for b^c ?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Euler's theorem states that if $$$\gcd(a, c)=1$$$ then $$$a^b \equiv a^{b\pmod{\varphi(c)}} \pmod{c}$$$. Since MOD is a prime, $$$\varphi(MOD)=MOD - 1$$$. Thus $$$a^{b^c} \equiv a^{b^c \pmod{MOD - 1}}$$$

»
2 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

My solution for Josephus queries.
I actually simulated the selection process iteratively, instead of recursively reducing it to smaller subproblem.

Before every iteration, the current set of numbers is stored with three number : $$$st$$$, $$$end$$$, $$$period$$$.
It implies that the current set contains these numbers $$$[st, st+period, st+2*period, ... end]$$$
Then we just simulate how the numbers will be chosen and find $$$cntchoosen$$$ denoting the number of elements chosen in this iteration.
If $$$k \le cntchoosen $$$, then we will just choose the $$$k$$$ th element of current set, else we continue the iterations.

Here is the accepted code.

Accepted Code
»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I came up with a different solution for Inversion Probability.

Lets denote $$$SS[i]$$$ by number of all unique arrays of size $$$i$$$. We can find using this way. $$$SS[i] = r[1]*r[2] ... r[i]$$$

Lets denote $$$sumf[y][i]$$$ by sum of frequency of $$$y$$$ in all unique arrays of size $$$i$$$. We can find using this way. $$$sumf[y][i] = r[i]*sumf[y][i-1] + (j<=r[i] ? SS[i-1]:0)$$$

Lets denote max value of $$$r[i]$$$ by $$$mx$$$.

Lets denote $$$sum[i]$$$ by the sum of inversion count of all unique arrays of size $$$i$$$. $$$sum[i] = sum[i-1]*r[i-1] + \sum_{x=1}^{x=r[i]} \sum_{y=x+1}^{y=mx} sumf[y][i-1] $$$

Finally our answer is $$$sum[n] / SS[n]$$$

Complexity : $$$O(n*max(r[i])*max(r[i]))$$$ Complexity can be bought down to $$$O(n*max(r[i]))$$$ by computing the prefix sum of frequencies.

Accepted Code :

Code
»
2 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

I do not understand the importance of the problem "Counting Divisors". We previously calculate all answers and then outputting them. I count each prime factor and then apply Combinatorics.

Tle on two test case

Secondly, I tried to optimize the factor calculation.

Pass
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

in PRIME MULTIPLES , ans+=n at last because iteration was start from i = 0 and for this reason extra n is added to the answer, you can start from i = 1 then everything will be fine.