HaabyHings's blog

CODECHEF NCC — Geeky Love Returns
By HaabyHings, history, 10 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

»
10 years ago, hide # |
 
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
»
10 years ago, hide # |
← 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
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← 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