Hello Codeforces Community!

Happy New Year to all!

I invite you all to join HackerRank's HourRank 25 on January 2, 2018, at 20:30 IST.

There will be three tasks in the round and one hour for you to solve them. The contest will be rated and the top ten contestants will receive HackerRank T-shirts!

The problems are prepared by me and tested by niyaznigmatul. Thanks to kevinsogo for help in setting up this contest.

I hope you’ll enjoy the problems.

Good luck and Happy Coding!

Again same question http://codeforces.com/blog/entry/56314?#comment-400599.

Does Hackerrank exclude this people from winners' list and add first people with rank bigger than 10?

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

.

My hard passed after fixing stupid bug 1 minute after the contest ended :(

Let

l[i] be the smallest such thata[i] ≥a[k] for alll[i] ≤k<i,r[i] be the largest such thata[i] >a[k], for alli<k≤r[i]. I guess . Can one show me a proof or it is wrong?I found it myself.

Denote

f(n) is the maximal sum for an array of lengthn. 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).I calculated this recurrence and found that it looks like . But do you have any ideas how to proof it?

f(n) is the maximal number of operations in the process "merge small to large subtree" on the binary tree of sizen.Can someone discuss their approaches for The Strange Function ?

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

Can you give some more details. Also, it would be really kind, if you can attach the code.

How is the total length of all complete segments O(n log n) ?

That's incorrect, yes. Best I can do is O(n log^2 (max(a))

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 isO(N^{2}) 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:

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

My First Contest of 2018. Missed my First gold Badge by 10 ranks.

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`

.haha, I made a wrong submission for that problem for not initializing f[0]=1 .

Can you tell the badgewise rank distribution please?

ClickSource

For Problem C,I assumed that the place j where F(i,j) is maximal for each 1<=i<=n is non-decreasing with the increasement of i and wrote a divide-and-conquer solution for it.However,it turned out it received Wrong Answer on a few testcases. Can anyone tell me why it's not correct?

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

Well,it's just my first sense after seeing the problem and I found it maybe reasonable,so I implemented it. And now I'm curious about on what kind of tests can it produce wrong answer.

Try this2

-2 -2

Thank you!

And another question,if all ai is positive,will the conclusion hold?

Nope

try this3

2 2 1

Now F(1,2)=4 , F(1,3)=3.

Here I want to point out is that gcd is a decreasing function and the other one is increasing (in positive case).Hence we cannot make any comment on behaviour on the final function.

Thanks a lot！

Big win for Serbia :)

Congratulation ivan100sic !

Thanks! :)

Can someone explain the third problem? I do not understand it from the editorial.

First of all consider

gcd(a_{l},a_{l + 1}, ...,a_{t}). For fixedl, this canonlytake different values (forgcdto decrease, it must be atleast half of the previous value, as it must properly divide the previousgcd). Also for each such valueg, there is a range [a_{g},b_{g}] such that the gcd is same (and equal tog)onlyfor these values.Fix a

land take ag. Let its range be [a,b]. Now you need to maximizef(t) =a_{l}+ ... +a_{t}-max(a_{l}, ...,a_{t}). Write this ash_{l}(t) -pref[l- 1] whereh_{l}(t) =pref[t] -max(a_{l}, ...,a_{t}), wherepref[i] =a_{1}+ ... +a_{i}. Since for givenl,git is sufficient to maximizeh_{l}(t) over [a,b], we will maintain this in a segment tree.Now suppose you have worked from

ntilll+ 1, and have values ofh_{l + 1}(t) in the segtree. How do you update this toh_{l}?pref[t]'s do not change. Considera[l]. Themax(a_{l}, ...a_{t}) part will be updated (toa[l]) for alljsuch that there isno other elementgreater thana[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 inh_{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,gpairs in by binary search, and queryinggcdover range. The complexity is thus (something like, point out if I miss terms) .I had the solution for the 2nd problem but did not know how to do modulo division!

Three things are eternal:

How long does it take to update ratings on hackerrank? zzzz...

And I thought codeforces' rating update was slow...

@HackerRank , do you realise that among the platforms AtCoder, CF, CC, CSA, HR , yours is the slowest to update ratings ? !!

HackerEarth: Hold my Beer.

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

O(n!)

O(n^n)

O(1) (but a constant factor of 2^100000000000000000000)

Maybe they are excluding cheaters, LOL