hit023's blog

Help required in solving a number-theoretic problem.
By hit023, history, 6 years ago, In English

Could someone help me in solving this problem : https://www.codechef.com/LOCMAY18/problems/DSERIES ? Here is my solution which, obviously, TLE'ed : https://www.codechef.com/viewsolution/18677401 . Also, it would be great if you could point me to some, other similar problems. Thanks!

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

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

If you indagate in this sums: you will able to prove that solution is: .

Then we can chancge the original problem to which has as solution:

. This can be calculated in O(t) which is good enough

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

    Thanks a lot for the answer. It's clear to me now. I was , initially, able to come up with the first relation. Couldn't get to the second. Could you point me to questions involving a similar logic? Also, shouldn't there be (t+1)! in the denominator in the final answer cbosch_carlgauss?

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

      I solve similar problems before but I don't recall where, a good place to seek is here and hackerrank, also of course codechef is great I have like 14 math problems in my codechef todo.

      In the other hand, no the solution does not involve a inverse of a factorial, is only rhe solution of the first sum without the first term of that sum, but that term is so the answer is exactly what I said before.

      Sorry there was a little mistake, is fixed already hit023

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

        Just to add to that, AtCoder is a great place to practice too :)

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

          Yeah, is one of the greatest sites, but the contest for me are to early.

          → Reply