Блог пользователя HaabyHings

Автор HaabyHings, история, 8 лет назад, По-английски

Link to the yesterday's codechef contest.
Unable to solve it.
Any hint or approach would be Appreciated.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Auto comment: topic has been updated by HaabyHings (previous revision, new revision, compare).

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

You can split a number X in sum of M non-negative numbers in C(X+M-1, M-1) ways. Find this answer for all such multiples of N below R.

You can view my submission here.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve the problem 'Greedy Harshit' from the contest?

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    dpk
    I solved the problem using dynamic programming.
    let dp[i][j] be the maximum amount of gold harshit can get using subarray a[i].....a[j].
    Answer needed is dp[1][n].
    dp[i][j] can be calculated using dp[i + 1][j] by picking a[i]th jar or using dp[i][j — 1] by picking a[j]th jar
    base case would be picking the a[i]th element at last.
    link to my submission.