minimario's blog

Assistance for Timus 2052: Physical Education
By minimario, history, 8 years ago, In English

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

Tags dp
  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
8 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Hello, I think this problem very easy, simple use of maxflow with george bulkerson algorithm. please let me know if this is correct

themaskedhero

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

    Really, here. Are you serious? I ask some question, and you reply with me for some random crappy fake method, pretending you can solve it?

    It is not really needed for these trash kind of post. Maybe you can start participating in a contest, let me see you can solve some problems instead of wasting your time posting trash comment like this.

    Perhaps you are on codeforces for fun, but people like I are here to learn something. So please start learning, respect for others.

    Thanks!

    → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +11 Vote: I do not like it

Your first observation is correct. Generally, I would solve this problem exactly as you suggested.

As you said, for fixed sum of digits s it's possible to find the number of numbers with this exact sum of digits. So, we can also find p — the number of numbers with lower sum of digits (sum up values for 1, 2, ..., s - 1).

Now, in interval [1, n] we binary search a number x that x = p + f(x, s) + 1 where f(x, s) denotes the number of numbers smaller than x with sum of digits exactly s. So, the term p + f(x, s) represents the number of numbers before x in the list (order) described in the statement.

So, the remaining thing is to calculate f(x, s). It is the exact same thing you can solve ("classical digit dp") because at the beginning you calculated f(n, s) (or f(n + 1, s), whatever).

→ Reply