vkditya0997's blog

Help !!

By vkditya0997, 9 years ago, In English

Hello everyone,
I am trying to solve this problem on topcoder ( SRM 678 div2 1000 ptr )
Not able to get the idea on how to solve!
Please help me in arriving at the solution !
Thanks in advance ! :)

EDIT : Anyone please?

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

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

I'm not sure whether my solution is correct..

First consider if we can shift all these n-1 stairs, we will want to shift them averagely. So we can do a dp[now_stair][shifting_used], make sure that now_stair is not shifted. For transition we enumerate how many stairs after now_stair to be shifted, and shift them to average positions. The time complexity is O(n^4).

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

    I didn't get you, Can you please explain?

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

      Suppose we have 2 stairs, the bottom is 0, the top is 10, and we can shift both of the 2 stairs. Then shifting them to 0, 3, 6, 10 won't be worse than any other shiftings. Like this, in our shifting plan, a consecutive shifted stairs should be averagely placed between the stair before them and the stair after them. So we can use a dp to solve this.

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

      The reason that the position should be chosen averagely is Lagrange Multipliers.

      → Reply