allllekssssa's blog

By allllekssssa, history, 9 years ago, In English

Hello Codeforces community !

I am glad to announce HackerRank 101 Hack 28th editon. The contest will be held on 20th August 2015 at 16:30 UTC. You can sign up for the contest here. Top 10 winners on the leaderboard will receive a HackerRank T-Shirt.

Problems have been set by Nikola Mandic(nikola12345) and Aleksa Plavsic (allllekssssa). The contest will consist of 5 problems with variable scoring distribution. Contest are rated for all HackerRank users. This is our second competition, after Codeforce div 2 round. We think everyone will find something interesting and solvable. Please read all the tasks, some problems that hard for us can be easy for you.

The main charcters of the round are Mika and Zloba. We would like to show how much we appreciate them :)

We want to thank whole HackerRank team, especially to wanbo for testing contest and great advices about tasks and Shafaet for helping and excellent communication. We believe we will cooperate in future with these excellent people.

Also I want to thank my friend Errichto. He is always here to listen my ideas and suggest several options to improve it.

Good luck, we are waiting your comments and impressions about contest !

UPD: Score distribution : 30 — 50 — 80 — 100 — 120

The competition starts in an hour.

UPD2: The contest has ended.

Congratulation to winners :

1.anta

2.uwi

3.Egor

4.mexmans

5.I_love_Tanya_Romanova

Thanks for participating. We hope you enjoyed tasks. We wish to hear any comment, any suggestions for better contest next time.

UPD3: Editorial is published !

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

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

Good luck :D

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

Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).

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

The contest will be started soon, ready to go go go !!!

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

Grid Maze is the same as J. Jailberak from here

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

Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).

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

    Are you going to answer all these 16 incoming HR messages? :)

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

      Ah, those 16 messages. No, not really

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

        Sorry for that, I do not know it is not an original problem, the reason why I use that problem as the 5th are:

        1. The author was intended to use the 4th one as the last problem, but after testing, I think it was too easy, so I rejected problem 3rd, and move the 4th problem to the 3rd, 5th to the 4th. And tell the author to use another harder problem because the problem set doesn't contains any hard problem.

        2. For the current 101-5, I think it is a really good MCMF problem, because the construction is not too straightforward, and it need calculate the max cost with any valid flow. And some people will forget to add the constraint for the total flow, if that, station_1 and station_m's flow can be over the number of seats in the bus, and will get WA.

        3. When testing, I discussed with my best friend, he hasn't solved this problem in about one hour, even he is a medium level red in both CF and TC, and after I told him the solution, he thought it is an elegant problem and hasn't seen this kind of problem before, so I used it.

        Every time, I was watching the contest behind the computer and looked forward to see handles like Egor, winger, uwi, I_love_... etc. to show up in the leader board. If you passed, at least the test cases are correct with great probability. If you got WA even at the first submission, I will be very nervous.

        Really looking forward to see all of you more frequently in HackerRank.

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

Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).

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

Task C with ordered set.

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

Как решать последние 2 задачи? (заранее спасибо)

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

    Четвертая: мы начинаем из S, идём в P, возвращаемся на некоторое число клеток назад и идём наружим. Переберём точку стыка, пытаясь минимизировать ответ суммой расстояний от стыка до S, P и выхода. Задача достаточно известная (см. дерево Штейнера для трёх вершин).

»
9 years ago, # |
  Vote: I like it +29 Vote: I do not like it

I spent the whole contest debugging the last task, working with the assumption that my mincostflow template code is correct, since it got AC in 2 contests. T-shirt lost, lesson learned, bug count of templates reduced by 1. Good job on the test data.

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I knew the solution to the last problem using min cost max flow , but I got WA, after the contest I realized that WA was because of wrong implementation of min cost max flow which I copied from Stanford Univesity ACM , they are using dijkstra to find augmenting path with least cost in residual graph, how funny!

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

    I've been using this code and got AC in several problems. So your comment is kind of frightening ! :| Can you point the error out (& correction if possible)?

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

      Djikstra doesn't work with negative edge weights, so you have to use shortest path faster algorithm or something similar :).

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

        Or you can simply run Bellman-Ford at the beginning and keep the Dijkstra :)

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

    Maybe it is Dijkstra with Johnson's potentials? Then it should be OK

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

      I used the min cost max flow implementation of official solution instead, and got AC without changing graph construction.

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

      What are Johnson's potentials?

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

I want to write a few sentences about contest.

First I saw a lot of people on the contest. I think that 101 Hack never had more people. I saw big number of well known guys from cf and other sites. Thank you we made everything much better and interesting !

About tasks, we apologize for the similarities. We have never seen this tasks before (in time when some tasks was made, even I didn't start with programming). Certainly 5-6 people had seen this tasks before contest and nobody had seen it anywhere. We invited a lot of tasks and in case that someone saw it we would change it. Also lederboard and the running of the tournament shows that everything was pretty fair and good for Hack (not many really fast scores on the tasks, not too many coders with lower rating on the top...). Contests was good, maybe more then I expected (I talk about number of contenstans, number of good submissions, time needed to solve some problems...). If someone of this red coders with good base tasks wants to talks me and helps that situation doesn't repeat I'm here at all times of day and night :)

We do this only because we love it and we like to see many top guys to solving our tasks. We expected to see more guys from our country and more our friends, but maybe thet didn't saw contest or they didin't have time. If you want to share your opinions about contest with me, I really wish to hear it :)

In case I see a lot of coders on our further contests, then I will know we done good job !

Thanks again, let's make a better competitions together !

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

I am new on hackerrank and i want to ask how fast the rating is usually updated?
About contest i want to say that the problems were pretty nice and new for me.

»
9 years ago, # |
  Vote: I like it +25 Vote: I do not like it

I think if HackerRank 101Hack want to attract more top rating contestants, they should find more experienced tester like rng_58 or Zlobober.

In recent Hackerrank contests, after opening high score problems, I usually feel them are boring and have no willing to code them. The fact let me decrease the frequency of participating Hackerrank Contest.

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

    I don't want to talk about tester. Wanbo finished his job and share his great advices. About this, hacerrank team should decide.

    We saw more than usual top rating contestant on our competition, we hope that is little because we organized the contest :)

    dreamoon_love_AA you didn't solve our hardest task on div 2 contest, we suppose you didn't like it... We hope you will find something interesting and harder on further contest.

    P.S. Do you like any of our problems :D

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

      In fact, when I don't think a problem is enough interesting or I think I cannot code it in short time (in about 10 minutes), I may give up when I compete in Div.2 contest. But I think your contest in Codeforces Round #307 is farther better than the HackerRank contest this time(compared by interesting degree). Especially when I do problem 551C, I feel that problem is interesting for me.

      I talk about more my thought about the HackerRank Contest this time. For problem A and B, it's not so hard such that I have no memories about similar problem. But I think they are good problem as easy problems in contest.

      Problem C is too classical problem in algorithm competition and it's quite straightforward(in my opinion). When I did this problem in contest, I think if there is only one classical medium problem, it's still OK.

      For problem D, firstly, I misunderstand the meaning of this problem and completed a totally wrong code. After I know the real problem, I feel tired because it's still a classical problem(This kind of problem usually occurred in out school homework for who want to compete in ICPC each year.) This problem definitely is not easy for who see it in first time. But when I see it again and again, my feeling is tired.

      After completing previous four problem, as soon as I read the problem E, I know it's some kind of min-cost max-flow problem I had seen three times. And I found I don't have the codebook of min-cost max-flow and there were many people had completed all problems. So I determined to give up.

      If the last two problems is created before you seen any related problems. I think you are smart!

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

        Thanks for sharing your opinions. I really appreciate it :)

        For the fourth task I had some a little different idea, but I was talking with Errichto he suggested this option ( for me better ). We expected very good coders to solve it and we try to make final difference on the last problem.

        About problem E, at first I invented one easier and interesting problem : you have n, m, k ≤ 105 and each passenger will pay you exactly 1 coin for drive. How many coins you can earn at most? It's some greedy + set ( priority queue) and after that we thouhgt about version when you have some amount of coins ( not every time 1 coin). My friend solve it with flow and we thought it could be good for contest...

        Honestly I didn't solve any flow task before and I could not give a full assessment of how much it is worth ( for me that was enough hard).

        For my opinion the number of full scores, the number of contestants with four tasks... are good and we made difference between best coders and ohers, now poorer contestants.

        You don't worry about T-Shirt, I believe you have a million different, I am still waiting my Codechef t-shirts :(

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

          Your first idea for problem E also would be quite well-known for a lot of people — check Timus 1424, and that's not the only place where I saw it.

          From my point of view, numbers of people with 5 or 4 tasks aren't very bad, but it isn't OK when we have more people with exactly 5 tasks than with exactly 4 tasks. It shows that there was something wrong either with difficulty distribution or with participants level distribution :)

          And one more thing — I am curious why HackerRank decided to make 0/1 scoring (without partial points) for last tasks. I saw recent comment by shashank21j about a different contest — We do not encourage brute solutions — well, in last contest brute partial solutions were possible for all problems, why do you make difference between first and last problems? If that's the only reason — either allow partial solutions or make 0/1 scoring for all of them.

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

            You are library with tasks :)

            I'm behind our competition and ready to discuss every my and my friend decision. I think that everything was pretty correct and this contest was better then many other which I done. I am only give and put some task when I think they are worth enough for contests.

            About final standings, I really don't know. The number which solved problems is: 432-151-58-34-18. You can see that's good distributed. Personally I expected more good submissions on first two problems and 12-13 good submissions on the last problem. But I saw more good and experienced than usual.

            For partial scoring in the last two tasks. We made partial score, but hackerrank team decided that is better to put binary scoring (0/1).

            I like to discuss about this topic with so good programmers and you certainly help me and hackerrank to make better contests. But that is global topic, now we have smaller amout of div 1 contest on each site, and it's pretty hard to invent good- interesting-enough hard contest for all programmers.

            We are new in computer science and you can be sure we will be better and better as hackerrank sit ;)

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

    @dreamoon, I am totally agree with you that I am far far not competent for testing problems which will be hard enough or interesting enough for high rating coders, we have tester like sdya. and we hope more these kind of super experienced coders to join us, if any of them can join our HackerRank team, the quality of our contest will be boosted.

    Anyway, I am trying my best to test the problems, and I am eager to improve, please give us some time, we will show you better contests. We are growing, and will make things better and better. I do not want to make you disappointed again and again.

    Btw, can you please contribute some high quality problems to us? You are such a high rating competitive programmer, we expect some suggestions from you.

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

      The following words may not have direct relation to your comment.


      I think there are some realistic considerations for problem providers. Nowadays there are so many competition platform, what is the criterion for problem providers to choosing platform? I wonder how others choose it.

      For me, I think one important point is problem providers will hope that there are more people can see their problems. Then, as the same type of 2 hours programming contest, do you think which platform providers will choose?

      There are also many other point problem provider may consider such as competition type, the amount of work needing to prepare the contest(need to provide tutorial by self or not?), the fees, limit for problems(ex. the I/O of Topcoder SRM has many constraint), where the platform come from ...

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

        I don't have experience like you. I do some contests on CF/Codechef/ HackerRank/Topcoder, at most on CF and Codechef.

        I have a lot of problems (I have enough time to thinking about it and I love it). I organized contest on CF and it was cool. Why I don't prepare something now for CF or Codechef:

        Reason for CF — they have a lot of div 2 contests. I think it'is better to see new problemsetters with new ideas , than us. I am not sure we have now enough good problems for d1 contest.

        Reason for Codechef — they have a lot of non rated contests with low number of participants — so I won't see a lot of people on the contest. That is important.

        The third, and for me most important reason, I talked with HackerRank guys and they was interested for our tasks. We could organize contest in nice time and we had good communication during preparation. I think that we can help HackerRank to get more contests and users (perhaps this is ridiculous) and also I think that HackerRank can help us to become better setters and programmers.

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

          Reason for Codechef — they have a lot of non rated contests with low number of participants — so I won't see a lot of people on the contest. That is important.

          Those are 3rd party contests, you know? They don't have nearly anything to do with Codechef...

          I estimated the actual numbers, recently they're something like:

          CF — 6500 (div1+div2 round)
          TC — 700 to 1000 (night SRM to day SRM +- fuckup coefficient)
          CC — 1600 (Cook-Off)
          HR — 1400 (101 Hack)

          In light of TC, the numbers on HR nor CC aren't all that bad... the main problem would be difficulties. Here is one thing you can try: if this time, one problem was removed and some shifted down, then do it again (or twice, you'll have a stack of more problems at least) and try to make a problem that would give tourist trouble. Don't worry, it will be easier anyway, but maybe it'll be a challenge for some high rated people. And it should be non-googlable and seem quite non-standard, of course.

          You won't attract many good coders without posing a good challenge, and a large gap between the last 2 problems isn't a very good challenge anyway.

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

            Yes, I know about Codechef contests. I like his official contests, but they have standard setters and low number of contests. Also when I was interested for Codechef I saw that they have a lot of forms and so you apply for a job. I suppose you should wait a lot for answer (if you get answer). For me, communication and job with HackerRank are easier.

            I think that CF always do around 4500-5000 people ( 1/4 of registerd users don't submit anything). For example during 101 Hack 1800 saw problems and 500 didn't sumbit anything.

            I think that is very hard to invent good problems for combined round with 5 tasks. For me, the ideal number of good sumbissions on previous Hack would be : 800-350-100-40-10. We really don't expected low number of good solutions in the first two problems. They wasn't so hard and many coders solve it in 12-15 minutes. That is optimal time, but I don't know what happened with others.

            We will try to invent more good tasks for our further contest and I hope to see you on them ;)

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

              Hi allllekssssa, I am really sorry to know that you got so much delay in response. In last few months, I think communication has improved considerably. Can you please send me your email id so that I look into your message?