afaik, they send the equivalent in money to the non-eligible countries

I found it myself.

Denote f(n) is the maximal sum for an array of length n. Consider the last largest element, one can easily see: f(n) = max(f(x) + f(y) + min(x + 1, y + 1)|x + y = n - 1).

Let's call "complete" segment a segment which gcd value would change if we would add number to the left of it or to the right of it. Total length of all complete segments is O(n log n), so we would just solve problem for each one of them

Additionally for each element let's find maximal subarray where it is maximum.

Now for each complete segment we would look at each element, look at intersection of complete segment and maximal subarray and we would need to find consecutive elements to the left of it within this intersection and also to the right of it. This is done using segment tree

There are quite a few possible approaches on this one :)

Besides things already described here, I can add one more idea: "I see that N is very small for some unknown reason, most likely naive solution can get AC". Indeed, it took quite some time to make it work, but my solution from the contest is O(N²) brute.

Also, at first I was lazy to code something similar to model solution and decided to code alternative one instead — let's fix left endpoint, consider all segments with this left endpoint and particular value of GCD and pick a position with largest prefix sum as a right endpoint. Midway I realized that it is wrong :) But it turns out tests are allowing this one to pass as well — you can check solution from the contest by natsugiri, which almost exactly matches my idea: code. The issue is: maximizing prefix sum doesn't always lead to maximizing (prefix sum minus max element) because it is possible to increase prefix sum a little bit while increasing max element much more. Here is a test for it:

9
10 10 10 10 10 -30 20 -10 30

Correct answer is 400 for taking [1,5], not 300 for taking [1,9].

My first contest of 2018, took me an hour ~20 minutes to realize I was using a[i] * fi[v/2] instead of (a[i] * fi[v/2])%md.

Can you tell the badgewise rank distribution please?

How do say its non decreasing. It is a combination of a decreasing function and another random function

Thanks! :)

First of all consider gcd(a_l, a_l + 1, ..., a_t). For fixed l, this can only take different values (for gcd to decrease, it must be atleast half of the previous value, as it must properly divide the previous gcd). Also for each such value g, there is a range [a_g, b_g] such that the gcd is same (and equal to g) only for these values.

Fix a l and take a g. Let its range be [a, b]. Now you need to maximize f(t) = a_l + ... + a_t - max(a_l, ..., a_t). Write this as h_l(t) - pref[l - 1] where h_l(t) = pref[t] - max(a_l, ..., a_t), where pref[i] = a₁ + ... + a_i. Since for given l, g it is sufficient to maximize h_l(t) over [a, b], we will maintain this in a segment tree.

Now suppose you have worked from n till l + 1, and have values of h_l + 1(t) in the segtree. How do you update this to h_l?

pref[t]'s do not change. Consider a[l]. The max(a_l, ... a_t) part will be updated (to a[l]) for all j such that there is no other element greater than a[l] between [l, j]. All the others remain unchanged.

Keep a stack, which stores elements in increasing order (popping elements if they are lesser than the current number), and for each element, stores the range, over which they are max. Also keep a segment tree which stores h_l, and can support range update (addition), and range query(maximum)

For example, for [4, 7, 5, 6], from the end, you first have 6, which is max from [4..4]. Then you get 5, which is less than 6, and is max from [3..3], so you stack looks like (top to end) [5, 6]. Next we get 7, which is greater than 5. So you pop 5, and since it was max from [3..3], you add (because the max is subtracted in h_l) 5 to the range, and subtract the new max, 7. Then you get 6, and you also pop it, and do the same. The range for 7 becomes [2..4]. Finally you just add 4, with range [1..1].

All this is done with a stack. Updates are done in segment tree, and you can enumerate all valid l, g pairs in by binary search, and querying gcd over range. The complexity is thus (something like, point out if I miss terms) .

HackerEarth: Hold my Beer.

Just curious, what is the complexity to update the ratings? O(n²)?

Maybe they are excluding cheaters, LOL