I changed the testcase so that now most of the answers for the test are above 10.

I changed the testcase and now the average answer is larger. Thanks for your suggestion.

Thanks for your suggestion. I have changed my solution.

Thank you so much for your corner case.

If you use the solution of subtask 6 to solve subtask 4, it will return the Time limit exceed verdict, since it has to precalculate a lot of things and has a big complexity per query with both small and large number.

Solutions from subtask 3 and 4 cannot solve subtask 1, so that I think publish subtask 1 is okay. I unpublished subtask 2 and maybe I will unpublish subtask 3 too.

Thanks for your suggestion.

Maybe I can unpublish subtask 2. I think it can be tricky to improve the sum digit count from subtask 3 to subtask 4.

I hosted a contest in my page (TLEoj) and I saw my contestants stuck in different subtasks except subtask 3 (maybe nobody use dp top-down, you can check the ranking of that contest here: https://tleoj.edu.vn/contest/024/ranking/ , problem 5). So that I think 6 katas for 6 subtask is ok to test how good you can impove your algorithm. This is such a nice problem that i think the points for solving a 1-kyu problem is not enough =))) You can try to solve the 6th subtask :D

Anyway, I think I will not post the subtask 5 because of the memory limit. In my page subtask 5 n will be up to 10 ** 9 and this will lead to a memory limit exceed if you use an array of a billion integers. But to make this problem suitable with Python language, I have to reduce the limit and subtask 5 will not be any tricky.

Thanks for your suggestion.

Hmmm I cannot see any corner cases that I can put in sample tests. And I fixed the seed of the random test, so that all test are fixed.

• I tried to run the sample tests without import anything (and suprisingly it passed) :D. So what is the difference when you imports?
• If you use dp top-down, you can see the difference =))) I discovered this bug while I brute test this problem :D.

My bad. Thanks for your correction.

Thanks for your suggesstion. I have added some tags for this problem.