divyamsingal01's blog

By divyamsingal01, 2 months 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 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
 
 
 
 
  • Vote: I like it
  • +92
  • Vote: I do not like it

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

Thanks man...

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

Thanks a lot!

»
2 months 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 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I still do not get sum of divisors :(

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

THanks bro!

»
7 weeks 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?

»
7 weeks 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?

»
7 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

divyamsingal01 can you pleaes elaborate on second problem Exponentiation II. I don't know much about Fermat's theorem.

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

    fermat's theorm says that if a,m are coprime and m is prime. then pow(a,m-1)%m = 1.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thankyou so much for the contribution

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

dardev cdes graph and yours math are the best!!

»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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?