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

Автор qoo2p5, 7 лет назад, По-английски

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
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Again same question http://mirror.codeforces.com/blog/entry/56314?#comment-400599.
Does Hackerrank exclude this people from winners' list and add first people with rank bigger than 10?

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

.

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
7 лет назад, # |
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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 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).

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I calculated this recurrence and found that it looks like . But do you have any ideas how to proof it?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +18 Проголосовать: не нравится

        f(n) is the maximal number of operations in the process "merge small to large subtree" on the binary tree of size n.

»
7 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Can someone discuss their approaches for The Strange Function ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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 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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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].

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

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you tell the badgewise rank distribution please?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Click
»
7 лет назад, # |
  Проголосовать: нравится 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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 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.

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Big win for Serbia :)

Congratulation ivan100sic !

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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) .

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I had the solution for the 2nd problem but did not know how to do modulo division!

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

Three things are eternal:

  1. The universe
  2. while(1);
  3. Ratings will be updated soon, please wait!
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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