### divyamsingal01's blog

By divyamsingal01, 8 months ago,

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 is now a complete tutorial, covering all the 21 questions of Mathematics Section of CSES.

1. Exponentiation

Tutorial
Code

2. Exponentiation II

Tutorial
Code

3. Counting Divisors

Tutorial
Code

4. Common Divisors

Tutorial
Code

5. Sum of divisors

Tutorial
Code

6. Binomial Coefficients

Tutorial
Code

7. Creating Strings

Tutorial
Code

8. Distributing Apples

Tutorial
Code

9. Christmas Party

Tutorial
Code

10. Fibonacci Numbers

Tutorial
Code

11. Throwing Dice

Tutorial
Code

12. Graph Paths I

Tutorial
Code

13. Graph Paths II

Tutorial
Code

14. Dice Probability

Tutorial
Code

15. Moving Robots

Tutorial
Code

16. Candy Lottery

Tutorial
Code

17. Inversion Probability

Tutorial
Code

18. Stick Game

Tutorial
Code

19. Nim Game I

Tutorial
Code

20. Nim Game II

Tutorial
Code

21. Stair Game

Tutorial
Code

• +92

 » 8 months ago, # |   +5 Thanks man...
 » 8 months ago, # |   +5 Thanks a lot!
 » 8 months ago, # |   +3 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.
 » 8 months ago, # |   +1 I still do not get sum of divisors :(
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 link this might help, see the last answer
•  » » 8 months ago, # ^ |   0 Yeah sorry, I have updated the explanation. I hope it is clear now.
•  » » » 7 months ago, # ^ |   0 Thanks
 » 8 months ago, # |   0 THanks bro!
 » 7 months ago, # | ← Rev. 3 →   0 divyamsingal01 can you share the links to the editorials of other sections if you have found them?
•  » » 7 months ago, # ^ | ← Rev. 2 →   0
 » 7 months ago, # | ← Rev. 4 →   0 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?
 » 7 months ago, # | ← Rev. 2 →   +3 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.
 » 7 months ago, # |   0 divyamsingal01 can you pleaes elaborate on second problem Exponentiation II. I don't know much about Fermat's theorem.
•  » » 7 months ago, # ^ |   0 fermat's theorm says that if a,m are coprime and m is prime. then pow(a,m-1)%m = 1.
 » 7 months ago, # |   0 Thankyou so much for the contribution
 » 7 months ago, # |   0 dardev cdes graph and yours math are the best!!
 » 6 months ago, # |   0 Would you care to explain the question Exponentiation II again? I tried to solve it using simple Binary exponentiation but got WA. I see you're using Fermat there what is the reason behind it. can we not solve it using simple Binary Exponentiation?
 » 6 months ago, # | ← Rev. 2 →   0 divyamsingal01In 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!
•  » » 4 months ago, # ^ |   0 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.
 » 4 months ago, # |   0 Where can I find the proof of the recurrence relation in the "Throwing dice" editorial?
 » 4 months ago, # | ← Rev. 3 →   0 some additional explanation for Q-2 ,so we have a ^ b ^ calso note that m is a prime !from Fermat's little theorem we know a^ m-1 = 1 mod(m) for every prime mb^c = q*(m-1) + r where q and r are quotients and remainder resp ,a^(b^c) --> a^(q*(m-1)+r) --> a^q(m-1) * a^r = (1^q) * (a^r) mod(m)so our ans for a^b^c = a^r(mod m) where b^c = r mod(m-1)Hope it helps :-)
 » 4 months ago, # |   +3 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
 » 2 months ago, # |   +6 Counting Necklaces How to get the inclusion/exclusion right?Can sombody explain with example n=12?
•  » » 2 months ago, # ^ |   +6 It's not that trivial if you don't know group theory, try reading about burnside's lemma.
•  » » » 2 months ago, # ^ |   +6 Found this which gives basically the solution. Link
•  » » » » 2 months ago, # ^ |   +3 If you would like to solve a similar problem on this theory , you may try this one https://codeforces.com/gym/101873/problem/B
 » 2 months ago, # |   0 Thanks a lot!
 » 2 months ago, # |   0 anyone solved grundy's game ?
 » 7 weeks ago, # |   0 Several weeks age CSES problem set presented some interesting new problems, including "Josephus Queries", https://cses.fi/problemset/task/2164 , and I'm looking forward to editorials for these new problems:)