HaabyHings's blog

CODECHEF NCC — Geeky Love Returns
By HaabyHings, history, 8 years ago, In English

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

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

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

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

    Thanks asawasa that was helpful.
    I am getting Access Denied to the page.
    please ideone your submission.

    EDIT — never mind, done that.

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

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply