divyamsingal01's blog

By divyamsingal01, 8 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

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

Thanks man...

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

Thanks a lot!

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

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

I still do not get sum of divisors :(

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

THanks bro!

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

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

  • »
    »
    7 months 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.

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

Thankyou so much for the contribution

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

dardev cdes graph and yours math are the best!!

»
6 months 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?

»
6 months 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!

  • »
    »
    4 months 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.

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

Where can I find the proof of the recurrence relation in the "Throwing dice" editorial?

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

some additional explanation for Q-2 ,

so we have a ^ b ^ c

also note that m is a prime !

from Fermat's little theorem we know a^ m-1 = 1 mod(m) for every prime m

b^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, # |
  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

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

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

Thanks a lot!

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

anyone solved grundy's game ?

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

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