Hello all,

Today I will bring you some interesting problem: Oh, I forgot to mention I cannot solve it...Dx

So here is the problem. Well, the first observation I have is that we can divide the numbers 1 to n into groups based on digit sum. Since two numbers with same digit sum have to differ by 9 or more, there can only be at most one number that does not change position after the sorting. So there are at most 81 different digit sum. (1 to 9 x 9)

So now there is new idea. This is part I am quite fuzzy with. It is not too bad to find the number of integers in the range 1...n with some digit sum k. (Some classical digit DP) But how this will help us? In particular, maybe there is a way to find the position of a number in a sorting in some good complexity, then apply some binary search method? I'm not sure, I have been working this problem for a while.

So if anyone has any ideas or can provide some hints, I would really appreciate!

Thanks,

minimario