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

Please Help me solve this (Amazon OA)
Автор I_Hate_Physics, история, 2 года назад, По-английски

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

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

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

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.

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

    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

    → Ответить