malcolm's blog

June 101 Hack on HackerRank
By malcolm, 9 years ago, In English

Hey, guys!

I'm excited to invite you to participate in 101 Hack June 2016! The contest will start at 16.30 UTC, June 20.

I'm the problemsetter of this round. You may have seen my tasks on previous HackerRank contests or may have participated in Codeforces Round 319 (Div. 1) or Codeforces Round 319 (Div. 2).

There will be five tasks and two hours for you to solve them. Top-10 contestants on the leaderboard will receive awesome HackerRank T-shirts! (I'm really jealous, since I don't have one)

I'd like to thank wanbo for his invaluable help and testing all the problems, danilka.pro for testing one of the problems and his cool proof of author's solution, Zlobober for his help in estimation of one of the tasks difficulty, and sankear, he did nice job sitting in the bar with me and discussing the problems.

I hope you will enjoy the tasks. Please read all of the problem statements during contest, as it may be essential for your final place.

Good luck!

UPD. The contest has ended. Special congratulations to Lewin: the only contestant who solved the last task!

Top-10:

1). Lewin

2). I_love_Tanya_Romanova

3). Errichto

4). tourist

5). Temirulan

6). Kostroma

7). Deemo

8). riadwaw

9). uwi

10). mgch

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

Comments Comments (66)
| Write comment?
»
9 years ago, # |
  Vote: I like it +145 Vote: I do not like it

Sitting in a bar and talking about problems... I thought it's only a dream, sometimes shown in Hollywood movies.

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

    Wtf? Isn't that like a completely typical thing :P? We already ate burgers and talked about problems, I guess it wouldn't have made much difference if that had been bar :P. Also don't tell me you haven't discussed about ACMs and algo problems at some alco parties :P.

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

The problem set is in very high quality, I like it very much. And it is relatively a little harder than previous contests.

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

Guys, the contest starts in one hour. Don't miss it!

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

The site is down -__- :/

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

LOL an epoch time bug post-contest xD

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

It's a pity that in last problem both cubic and quadratic solutions give the same number of points

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

    You've got too great cubic solution, mine received only 27.50 points. BTW, good problems, but I've seen something similar to D in some Petrozavodsk training camp.

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

    Yeah, that was a pity to see cubic solutions getting ~50 pt. Author's cubic solution is much slower and gets ~25 pt, as expected.

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

      Well, setting n<= 5000 for quadratic solution would probably help, 1000^3/6 is not undoable :)

      Thanks for good problemset

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

How to solve the third problem?

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

    You may find the solution in the "editorial" tab on HackerRank.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it +19 Vote: I do not like it

      By the way, did you came up only with a solution which finds the k-th element but not the whole array, or intentionally make this problem slightly easier?

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

        How do you find the whole array!?

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

        I have no idea, how to find the whole array. Could you briefly describe your solution?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 3   Vote: I like it +29 Vote: I do not like it

          At first find for every segment [li;ri] the sequence of segments [li, ri], [lj0, rj0], [lj1, rj1], ..., [ljk, rjk] such that i < j0 < j1 < ... < jk, and ljk is minimal possible. This can be done by segment tree by processing the segments in reverse order (we need only the value of ljk).

          Then for each position pos find the minimal such ljk for all [li, ri] containing pos. Then process apos in the order of increasing apos, the position of it will be the first free positon after such ljk.

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

            I must misunderstand what you mean..

            Say you have initial array 10 11 12 0 1 with the segments 2 4 and 0 2.

            Then from what I understand, for any position in the array, we find ljk = 0? But then we'd conclude that value 0 goes to position 0, then value 1 goes to position 1, but really it will go to position 3.

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

              It seems you are right, and my solution is a bullshit =) The tests were not strong enough :)

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

https://www.hackerrank.com/contests/101hack38/challenges/sorted-subsegments can anybody suggest an alternate approach to solve this problem?? the one described in editorial was like magic to me.. any intuitive approach by anyone please??

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

It was also a pity that in the third problem brute force in java (sort each sub-segment) got > 72 pts...

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

    In c++ it only gave 20 pts, Why is that?

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

    That can't be true!

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

    Agreed. Naive solutions using built-in sorts should NOT be worth > 90% credit. That was ridiculous and one of the major defects of this contest.

    Furthermore, the very same naive solution in C++ only gave 20 points compared to java's 72. That's also a very, very interesting outcome. What are the underlying implementation differences between the builtin sort functions of the two languages, and are those differences (if any) accountable for the massive runtime difference? If not, is there some other factor that I'm not seeing here (other than I/O which I believe is a trivial factor given the low input constraints)?

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

    Another naive solution that gives high score of 67.10

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

      It's not naive — it's incorrect one :/

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

Nice editorial of third problem. Thanks! But isn't the complexity O(Q·(log(N))2) instead of O(N·(log(N))2) ?

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

One thing that I really don't like about hacker rank is that only 480 people had correct solution and yet my rank is 779.

That makes me not care about hacker rank rating . They always have a different and nice kind of problem set but these little things, I don't like them.
On the other hand it allows some people who know a concept to good extent might get some edge over other , there won't be a binary game , but this is often mis-used.

IMO constraints must be set such that only solutions with very good knowledge gets some points.

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

    Well,

    It's all about testing. They can add the number of test cases to solve per run. This way even to get a partial score, your solution would have to be correct.

    Also they can exclude some edge cases if they want to provide partial score for not covering all the cases.

    Anyway — the partial score system is more fair in my opinion. You do your best on all the problems and if you have a small bug or you miss one case, you can still get decent credits.

    It also allows you to develop a better strategy to get a higher rank. You can decide whether you will try to spend more time on solving some problem completely or maybe it is better, to write a brute force and move on to the next task.

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

      I'd say that the partial score system actually isn't very fair, in some cases.

      Try submitting a program that only prints 1 to the last problem, "Byteland Itinerary". Because you pass a few test cases with that, you get 4 whole points.

      For example...

      Consider person A, who solved the first two questions very quickly but doesn't know how to solve the rest. Person A gets 50 points and is very much ahead of other 50 point people because he solved them more quickly.

      Person B takes forever to solve the first two, gets 50 points, and then submits a print 1 program to the last problem, netting a total of 54 points, and beating person A.

      Person B doesn't deserve to be ahead of person A. This is where HackerRank's partial credit grading system fails.

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

        Well,

        They could add T — the number of test cases to solve.

        Then they could add 10 small tests with different answers and printing 1 wouldn't score anything — as I said it is all about testing.

        They have a big potential of preparing such a set of tests which will give different scores for different approaches. It is not the problem of partial scoring, but testing.

        Anybody who has an idea which will get positive score on any task should get the higher position than somebody who has no idea at all. The fact how easy will it be, to get that partial score depends only on the tests.

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

          Good points.

          I think the best way to rectify the issue I mentioned earlier is to only allow judge submissions if and only if the sample tests pass successfully (hackerrank's run tests button). Also, the sample tests should not be included for grading towards actual points.

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

            That's not a solution, one can simply write a couple more if/else statements to pass the sample. Adding some number of test cases as mentioned above is the only way I can think of.

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

        In a partial scoring system, the best solution according me is to have subtasks and not marks per test case. For example a person solving a smaller subtask should get full marks for that subtask if they solve it completely otherwise 0. This individual mark per test case actually rewards you for wrong solutions.A smaller subtask, ensures that a person has atleast solved the problem 100% for those particular constraints.

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

      The most unfair thing IMO about partial scoring is that the range of possible points a solution can get is continuous. This means that some optimisations like reducing constant factor of solution can make some tests of higher subtask pass, and award more points for almost the same solution.

      For more complicated problems/codes, it then becomes a matter of chance which subtasks marginally pass/fail for which user. You can already see the wide variety of naive/wrong solutions for sorted-subsegments which got >=45 points. Different users might get a large variety of scores, with only a few users with partial solutions getting equal scores, and it beats the purpose of time-based penalty. This could be observed in this contest's ranklist as well.

      This can be avoided by awarding subtask-based points (like is done in Codechef Long).

      Also, i don't see any point in awarding even a small number of points for a very naive brute solution for the difficult tasks.

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

      I didn't do contest, but I prepared several rounds for HackerRank and have good experience with all this 'problems'.

      My opinion partial scoring is better option and contest is more interesting. One thing which irritate me that nobody writes subtasks in the text (constraints + amount of score ). I am always trying to do it and think it is more fair. I saw comment that little optimisation gives more points, I think that is good, everyone has full feedback and can write such code !

      One bad thing is that HackerRank doesn't have classical option for subtasks ( all testcases in subtask must pass for non-zero score) like Codechef. Normally we can put more examples in one testcase , but it is not always possible.

      I am writting 2-3 solutions for my tasks and try to make optimal score for each, but sometimes it takes 5-6 hours, or even the whole day! I understand when someone can not do it on such way, also again it is possible to have mistakes like this Java sort...

      About forum, I don't like that! I can not allow disscussing about tasks on that way. For me much better option is asking question to organizators and allow forum after contest finsh — or checking comments before posting it on forum by admin or setter.

      I like quality of HR tasks in last months, for me that contests are the most interesting and often I am happy after my performance there, but for sure there are several things which guys from HR must do if they want community like CF :)

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +66 Vote: I do not like it

And it was also a pity that organizers were giving hints to some contestants during the contest:

https://www.hackerrank.com/contests/101hack38/challenges/points-on-a-line/forum/comments/145470

I don't understand such a behavior. If you wanted everyone to pass the first problem, you could have asked to print 1 for example.

Otherwise it is unfair for other contestants who didn't think of reading discussions during the contest.

Edit: That comment is just explaining the solution... https://www.hackerrank.com/contests/101hack38/challenges/points-on-a-line/forum/comments/145418

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

    Because there are hundreds of very beginners in our platform, they do not have any experience in problem solving, we hope we can guide them to get their first AC. This is only permitted for the 1st challenge.

    If just output 1, very beginners will also feel so stupid. Hope you can understand, there are hundreds of people still not passed even at the ends of the contest, and they will email to us complain about it. So we changed our strategy that we need to help them during the contest for the first challenge.

    Everyone will be excited by their first AC, maybe because of these, several years days, they will be red coders. :) Someone with weak mind will may leave because of too many WAs even they are convicted that their solution is correct.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +46 Vote: I do not like it
      ... there are hundreds of people still not passed even at the ends of the contest, and they will email to us complain about it.

      So the lesson is: if you are lazy as fuck to improve, then complain about being lazy as fuck and get a free AC. Maybe that's the reason why there's a bunch of indian competitive programmers but only a few have decent skills.

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

        Chill, dude.

        BTW I think you're going to need some burn heal.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 3   Vote: I like it +6 Vote: I do not like it

          I'm just saying that if you are lazy to improve, accept your position and don't complain. But asking for hints during a contest is just stupid.

          And if you feel offended for what I said about the indians, then read wanbo's comment. If there are hundreds of guys not able to solve an easy problem and only worried about getting an AC during contest, what can you expect from them in the future? Nothing, because they probably just don't even care about competitive programming and do contests only to improve her resumes or to pass a job interview.

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

          This hand looks as mine after yesterday crash from bike. I fell down while I was driving up the hill :D

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

      So it is official — in case I'll struggle with solving first problem next time, I can ask you about solution right during a contest? :)

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

        yes, and we will allow gray coders to help you solve.

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

          This is like giving somebody a lollypop just because they cry foul about failing in the exam. That lollypop has to be earned only in the case of passing the exam and let everybody else know there is no other way around it.

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

      I wish I knew this before Hourrank 9.

      It took me 45 minutes to solve the first task as I couldn't proof the simple greedy solution. On the other hand the second task took me 5 minutes.

      Next time I will be smarter and just use the discussions tab :)

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it +6 Vote: I do not like it

      More seriously.

      I think that you can add a notice to the problem that this is a competitive programming contest. It is not practice problem and doesn't mean to be an easy challenge. Please do not send us any email if you don't get accepted during the contest. After the contest there will be a published editorial and you will have the opportunity to check the solution and test cases. Don't be upset, don't give up, try hard and maybe next time you will succeed — or something like that. To make sure that you don't upset beginning contestants and to show that you think of them and would like them to improve.

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

      In contests with prizes I'm going to start from the second problem. After some time I will go back to the first problem. I'll go to comments and hope to maybe even find a ready solution (code). I'm allowed to do it, right?

      Also, are you planning to provide solutions for second problems in the future?

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

        You guys are really overreacting on this. The first problem of this contest was too simple, only newbies would struggle to solve this. wanbo said that they will only help newbies by giving hints, if a problem is not that simple they would not give any hints.

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

          You don't participate in any contests and know better?

          Why was it too simple? Do you think that it should be harder? So why would they provide a solution in the comments?

          In some contest eventually the first question will be harder than organizers expected. But yeah, we are allowed do talk about a solution in the comments.

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

          Oh no, no one is overreacting.

          You see, this is the problem with HackerRank. Nobody knows what are the rules when participating. And worse, the rules keep changing from time to time (sometimes because of a glitch but whatever) and the changes are NEVER mentioned anywhere.

          No I will NOT memorize what are the time limits for C/C++ or Java. No I DO NOT know that penalty for 101 Hack is the sum of all submissions but for HourRank is the last time of submission. Don't you think it is more convenient for everyone if it is mentioned EXPLICITY in the contest dashboard? Hell it is even difficult to know if a contest is rated or not. Seriously, how hard can it be to make all these information easier for contestants to access?

          Regarding providing solution to the first problem, no matter what the rules are, I can respect them even if I do not like them. But the rules should be FAIR AND YOU SHOULD EXPLICITLY MENTION THEM BEFORE THE CONTEST. If you are going to provide hints/solution for the first problem in discussion, that's fine(though I think its lame). But please DO NOT discriminate whether the contestant is gray or red and DO NOT invent your own rules DURING the contest.

          I know my comments may sound a bit harsh but that's just my 2 cents and please don't get me wrong. I am also a problem-setter in HackerRank, it is a great platform and I appreciate the work you guys do. But it can be a lot better with some minor modifications. My apologies if my words hurt anyone.

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

            To be honest, infomation on whether contest rated is on "contest" page

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

              This is precisely my point. There is information regarding the time limit for all languages somewhere too. But none of these are easily accessible right? To see whether a contest is rated, you have to go to the "contest" page, click on the contest and then it will expand to show if its rated or not. Sounds too convenient for me.

              In my opinion, it is better to add every information like whether its rated or not, how are ties broken and other contest rules somewhere in the contest dashboard. And if they really want to provide beginners with hints and/or solution, its better to post them by creating a "Hints" sub-section in the problem page instead of using discussion forum. I guess everybody would be happy then :)

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

Solutions where a person sorts the whole array and returns the answer gets 41 points. Solutions in which a person just sorts the array in between the maximum index and minimum index of queries gives 78 points. What is the difference between a person who implements segment tree and gets 80 points and a person with a naive/incorrect solution gets 78 points.I mean hackerrank is just losing it's sheen because of this. People with incorrect solutions getting 78 points is literraly is unfair over the system. Please do introspect and see it in the eyes of a deserving candidate who feels unfair that others incorrect solution passes and his correct solution takes time.

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

Nlog(N)*log(N) solution (binary search + lazy segment tree) giving TLE for some test cases for problem "sorted subsegments".

is lazy not sufficient for this problem?

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

    While doing binary search..sort the array and only take those values which are in array..

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

      oh yes that clever optimization :) thanks it made my solution 2 times fast!

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

I've just noticed, that time scoring in 101 Hack and HourRank differs:
HourRank: largest time of best submission of last problem
101 Hack: sum of times of best submissions of all problems
But don't see any decription in scoring rules, is it correect?

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

    It is correct !

    I think the first decision for HourRank was same penalty as 101 Hack, but it was mistake on the first round and it wasn't changed after it :D

    It should be mentioned somewhere, but after 40 rounds I think everyone knows rules :)

    → Reply