I_Hate_Physics's blog

Please Help me solve this (Amazon OA)
By I_Hate_Physics, history, 19 months ago, In English

For any array of positive integers a[a[1]..a[k]], its score(a) is calculated as follows: • For each a[i] where 1 ≤i≤k in order, add the current maximum element in the array to a[i]. • score(a[k]) is the sum of the final elements in a. Since the sums may become large, score(a) should be calculated modulo (10^9+7).

Question link(Google Drive Link

  • Vote: I like it
  • -10
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
19 months ago, # |
← Rev. 6   Vote: I like it +3 Vote: I do not like it

Consider the subarray [0, i], and it maximum element to be MAX, we can notice that a[0] will become a[0]+MAX and it will now be the max element, in turn 2, a[1] will become a[1]+ (a[0]+MAX) and so on. So answer is (sum of (a[i]*(n-i)) + n*MAX. (for all i in the interval, n is the size of the subarray)

Note: I should definitely learn to use LaTex, sorry.

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

    Damn, so smart.

    Can you please advice me some tips on how to be good at such problems. I fear codeforces tbh. Even the A levels are too logical for me. Can you advice me something.

    Hey, for array={1,2,3}. According to your algorithm, how will the answer be {2,8,19}. For range [0,0] MAX is 1, so are[0]*(3-0)+3*1=3+3=6, but shouldn't it be 2. Sorry, maybe it's silly. But please help.

    Thanks

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

      Do 700 problems, I know codeforces is not that interview question like but everything helps to get better in these math riddle problems.

      → Reply