ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1057. Amount of Degrees

Any simple approach?
Posted by Artem Khizha [DNU] 5 Sep 2010 15:46
Well, after all, I solved this problem, but it took a long time for me to find all mistakes in my calculations.

My idea was to generate F[N,K] in a O(log(N)*log(N)) time, which means an amount of numbers with N or less digits (in a certain base) with K one-digits. Then I wrote a function C(N, K), which finds an amount of numbers with K one-digits in [1, N] using F and deleting its first digit every time. Actually it's all about dynamic programming.

But I think there must be more clear and efficient solutions, than mine (O(log(N)*log(N)) for time and memory). If it does, please, would you be so kind to share it?