wanbo's blog

HackerRank 101Hack 42 is coming
By wanbo, history, 8 years ago, In English

Hello Codeforces community!

I am glad to announce that HackerRank 101 Hack 42 will be held on 18th Oct 2016 at 16:30 UTC. You can sign up for the contest here. Though what's priceless is solving interesting problems and the thrill of competition, prizes make the competition fierce. Top 10 performers will get a HackerRank T-shirt.

The contest will consist of 5 problems with variable scoring distribution. We have tried our best to prepare a nice problem set. Hopefully everyone will enjoy. Also, you'll be able to enjoy the detailed editorials written by the setter.

Good luck and have fun!

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (37)
| Write comment?
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Who is the setter this time around?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this correct for the earlier version of 4th problem ?

→ Reply
»
8 years ago, # |
  Vote: I like it +44 Vote: I do not like it

I solved E in O(n × log3(n)) and it passed TL. Problem statement for D was totally wrong for 70 minutes of contest. Strange contest.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Was there any notification that D's statement changed?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't see any notifications. Just was checking comments for every 5 minutes.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I've noticed "turned off" change into "toggle" after problem statement refresh.
      Then, after some time, the "(1)" appeared in notification icon at the top.

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I also got 100 in E with log^3, I thought it would get at most 50. I wonder what was the purpose of the second subtask if this passes everything.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain your log**3 approach ? Editorial isn't clear.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Say we want to solve the problem for indices from L to R. Denote with P the index of the largest element between those indices. Now for every interval [i;j] (L<=i<=P<=j<=R, i!=j), it is true that max[i..j] is on index P. So we want to count how many such intervals we have so that A[i]*A[j]<=P. And when we are done, we recursively solve the problem for intervals [L,P-1] and [P+1,R]. In order to count the number of those intervals [i,j], we can use the following slow approach: For every i from L to P, count how many numbers from P to R are less than or equal to A[P]/A[i]. Well, once we have fixed i, we can find the number of those j indices in log^2 (actually log is possible), it is a known task — http://www.spoj.com/problems/KQUERYO/ (my solution for this problem is really fast actually, see ranking, so this may have helped to pass the time limit here :D).

        Well, now the only thing we need to do is to see if the interval [L,P-1] is shorter than [P+1,R]. If it is, then fix i among [L,P-1] and count the proper indices j. If it is not, then fix j among [P+1,R] and count the proper indices i. And this is in total O(NlogN) divide and conquer, if we always choose the shorter interval.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks , I got it now . Btw , for the spoj problem did you do something other than merge-sort tree ?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Nope, just a merge sort tree with fast input and I simply allocated arrays for each node, instead of vectors and used hand-written binary search instead of lower_bound/upper_bound.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Is there any meaningful time difference between malloc(n * sizeof(int)) and vector<int>(n)?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                ← Rev. 2   Vote: I like it +5 Vote: I do not like it

                That wasn't a cool move, ffao, why did you code such a fast solution :D

                I guess it depends on what meaningful time difference means to you. I took my fastest solution (0.06s), changed the struct to the following piece of code and submitted a few times and it worked in 0.10-0.11s:

                struct tree_node {
    int n;
    vector < int > a;
    tree_node(): n(0) {}
    tree_node(int k) {
        n=k;
	a=vector < int > (n);
    }
};
                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I just had a mergesort tree written here and I wanted to test if it was correct, I had no idea it was fast :)

                  0.05 isn't a significant difference for most problems, but when solving problems with tight time limits I'll definitely keep this in mind!

                  → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you please share your code ?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, sure! The struct tree_node as well as the functions merge_them, build_tree, update_tree and query_tree are pretty much what I used for KQUERYO, I just copied them from there.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I meant for the hackerrank question :P

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                That was the code for the hackerrank question, I just pointed out what part I used to solve KQUERYO.

                → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I'm guessing they didn't want log^3 to pass, but didn't actually check if it passed or not. Separating solutions by one log is really hard anyway, I don't know why they still try.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe that's right. This came to my mind but it seemed like a bad attempt :D

        → Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

1) Will the round be rated?
2) What is "BIT" in "can solved offline using BIT" in E-problem's editorial?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    BIT is binary-indexed tree.

    I guess, it's rated, since "Ratings will be updated soon, please wait!" is written on contest page.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +15 Vote: I do not like it

      "Ratings will be updated soon, please wait!" could be just a robot's message :)

      → Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

In problem E, why does iterating over the smaller segment doesn't time out?

→ Reply
»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

About problem D, if you have a loop that takes k time and a loop that takes n/k time, then the complexity is O (n), not O (nk). I'm guessing the statement wasn't the only part of this problem that was rushed...

→ Reply
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

For E problem.I wrote N*log(N)*log(N) solution but it give TLE.Pls help find my mistake.I used ordered set and divide conquer. Here is my code.

→ Reply
»
8 years ago, # |
  Vote: I like it -38 Vote: I do not like it

I was initially using a sparse table in problem E, that took O(NlogN) memory, that caused MLE. However, all this time, HackerRank's judge showed me the verdict Wrong Answer.

After the contest, I used a segment tree, that takes O(N) memory, and guess what, my solution passed. Why doesn't HackerRank provide a verdict like MLE ? Is giving wrong answer the right way to deal with this? This made me really angry after the contest.

When one creates an online judge, the first thing one should deal with is small things like various verdicts. This is really stupid from HR.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    How do you know that it was MLE if Hackerrank showed you WA for all the cases? Could there be some bug in your sparse table code which resulted in WA?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it -20 Vote: I do not like it

      My code passed the first 10 test cases and got a score of 52 initially when I used a sparse table . The final verdict was WA

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How does this mean that your actual verdict wasn't WA?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it -16 Vote: I do not like it

          Please check for urself. Just declare an array of size 5 × 105 × 18 to any of ur AC code, and the next thing u will see is WA !

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            This code gets AC in the contest's first problem. I created a long long array of size 5*1e5*18, as you said and the code passed the test cases.

            → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    I also used sparse table (along with persistent segtree) but my code successfully passed, without any MLE!!

    AND i never heard of any segtree using O(n) memory.. i am curious does something really exist?

    → Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

In 4th problem, why the theory that no button should be pressed twice works?Proof!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Pushing a button twice is the same as not using it at all

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sorry, i meant if some bulb is switched off , why can't we press the button corresponding to it. I get what you meant, but i'm not able to understand this claim "If button i is pressed, then no button in the inclusive i-k,i+k range will be pressed".

      → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

I have an alternative (albeit harder to implement) approach for problem E:

We will be using D&C approach. Let's now consider a segment [l...r) ans fix m = (l + r) / 2. We will recurse for [l...m) and [m...r) and, after that, calculate the answer for and .

Now, let's suppose the maximum value lies on the right segment. Then, we could sort the left segment decreasingly by value A[i] and sort right segment decreasingly by value max[m...j] / A[j].

Now, we can impose the constraint A[i] * A[j] ≤ max[m...j] by an algorithm similar to merging sorted arrays, with the two pointer approach. Let's also not forget about the other constraint, created by out supposition: max[i...m) ≤ max[m...j]. This can be solved by keeping a data structure of your choice (I used BIT).

The other case is solved similarly, with some extra care for double-counting.

No arguing, the other solution is easier to understand and write. And it's a nice trick to remember.

Code is here. I had to parse input data in order to squeeze it within time limits. Sneaky and overcomplicated, but rather fun nonetheless.

→ Reply