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?

Before contest

Codeforces Round #687 (Div. 1, based on Technocup 2021 Elimination Round 2)

14:30:03

Register now »

Codeforces Round #687 (Div. 1, based on Technocup 2021 Elimination Round 2)

14:30:03

Register now »

*has extra registration

Before contest

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)

14:30:03

Register now »

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)

14:30:03

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3687 |

2 | ecnerwala | 3600 |

3 | Benq | 3503 |

4 | ksun48 | 3421 |

5 | Um_nik | 3412 |

6 | Radewoosh | 3382 |

7 | maroonrk | 3323 |

8 | Itst | 3239 |

9 | apiadu | 3238 |

10 | ko_osaga | 3232 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 205 |

2 | SecondThread | 199 |

3 | Monogon | 196 |

4 | vovuh | 190 |

5 | Um_nik | 186 |

6 | pikmike | 185 |

7 | antontrygubO_o | 184 |

8 | Ashishgup | 181 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

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?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/28/2020 19:34:58 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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).

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

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.

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