### qoo2p5's blog

By qoo2p5, 4 years ago,

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!

• +67

 » 4 years ago, # |   +21 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?
•  » » 4 years ago, # ^ |   0 afaik, they send the equivalent in money to the non-eligible countries
 » 4 years ago, # | ← Rev. 2 →   -6 .
 » 4 years ago, # |   +14 My hard passed after fixing stupid bug 1 minute after the contest ended :(
 » 4 years ago, # | ← Rev. 4 →   +15 Let l[i] be the smallest such that a[i] ≥ a[k] for all l[i] ≤ k < i, r[i] be the largest such that a[i] > a[k], for all i < k ≤ r[i]. I guess . Can one show me a proof or it is wrong?
•  » » 4 years ago, # ^ |   0 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).
•  » » » 4 years ago, # ^ |   0 I calculated this recurrence and found that it looks like . But do you have any ideas how to proof it?
•  » » » » 4 years ago, # ^ |   +18 f(n) is the maximal number of operations in the process "merge small to large subtree" on the binary tree of size n.
 » 4 years ago, # |   +19 Can someone discuss their approaches for The Strange Function ?
•  » » 4 years ago, # ^ |   +5 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 themAdditionally 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
•  » » » 4 years ago, # ^ |   0 Can you give some more details. Also, it would be really kind, if you can attach the code.
•  » » » 4 years ago, # ^ |   0 How is the total length of all complete segments O(n log n) ?
•  » » » » 4 years ago, # ^ |   0 That's incorrect, yes. Best I can do is O(n log^2 (max(a))
•  » » 4 years ago, # ^ |   +8 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(N2) 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].
 » 4 years ago, # | ← Rev. 3 →   +4 My First Contest of 2018. Missed my First gold Badge by 10 ranks.
•  » » 4 years ago, # ^ |   +2 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.
•  » » » 4 years ago, # ^ |   0 haha, I made a wrong submission for that problem for not initializing f[0]=1 .
•  » » 4 years ago, # ^ |   0 Can you tell the badgewise rank distribution please?
•  » » » 4 years ago, # ^ |   +3 ClickWhen you perform well in a rated contest, not only you increase your rating but you will be awarded a medal. Top 25% users in any rated contest will get one of gold, silver and bronze medals. Medal distribution is as follows: Gold - 4% Silver - 8% Bronze - 13% These medals will be available & visible in your profile. Source
 » 4 years ago, # |   0 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?
•  » » 4 years ago, # ^ |   +8 How do say its non decreasing. It is a combination of a decreasing function and another random function
•  » » » 4 years ago, # ^ |   0 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.
•  » » » » 4 years ago, # ^ |   +8 Try this2 -2 -2
•  » » » » » 4 years ago, # ^ |   0 Thank you!
•  » » » » » » 4 years ago, # ^ |   0 And another question,if all ai is positive,will the conclusion hold?
•  » » » » » » » 4 years ago, # ^ |   0 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.
•  » » » » » » » » 4 years ago, # ^ |   0 Thanks a lot！
 » 4 years ago, # |   +13 Big win for Serbia :) Congratulation ivan100sic !
•  » » 4 years ago, # ^ |   +16 Thanks! :)
 » 4 years ago, # |   0 Can someone explain the third problem? I do not understand it from the editorial.
•  » » 4 years ago, # ^ |   +8 First of all consider gcd(al, al + 1, ..., at). 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 [ag, bg] 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) = al + ... + at - max(al, ..., at). Write this as hl(t) - pref[l - 1] where hl(t) = pref[t] - max(al, ..., at), where pref[i] = a1 + ... + ai. Since for given l, g it is sufficient to maximize hl(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 hl + 1(t) in the segtree. How do you update this to hl?pref[t]'s do not change. Consider a[l]. The max(al, ... at) 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 hl, 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 hl) 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) .
 » 4 years ago, # |   +4 I had the solution for the 2nd problem but did not know how to do modulo division!
 » 4 years ago, # | ← Rev. 2 →   +21 Three things are eternal: The universe while(1); Ratings will be updated soon, please wait!
 » 4 years ago, # |   0 How long does it take to update ratings on hackerrank? zzzz...And I thought codeforces' rating update was slow...
 » 4 years ago, # | ← Rev. 2 →   0 @HackerRank , do you realise that among the platforms AtCoder, CF, CC, CSA, HR , yours is the slowest to update ratings ? !!
•  » » 4 years ago, # ^ |   +26 HackerEarth: Hold my Beer.
•  » » 4 years ago, # ^ |   0 Just curious, what is the complexity to update the ratings? O(n²)?
•  » » » 4 years ago, # ^ |   0 O(n!)
•  » » » 4 years ago, # ^ |   0 O(n^n)
•  » » » » 4 years ago, # ^ |   0 O(1) (but a constant factor of 2^100000000000000000000)
•  » » 4 years ago, # ^ |   0 Maybe they are excluding cheaters, LOL