Shafaet's blog

HackerRank University Codesprint!
By Shafaet, history, 8 years ago, In English

Hello Codeforces Community, I am glad to share HackerRank University Codesprint starting on 10th November 2016. The contest duration is 24 * 3 =72 hours.

The winners of the contest will win up to 2000USD cash prizes. Also, there is opportunity to win T-shirts and Amazon Gift cards. (Winners will be required to give proof that they are currently enrolled in the university they represented during University CodeSprint.)

The contest will be rated. If two person gets the same score, the person who reached the score first will be ranked higher. There will be a separate ranklist for schools.

There will be 7 normal algorithmic challenges and 1 approximate challenge in this contest. Many of the problems will have smaller subtasks, so I highly recommend you to read all the problems.

The problems are prepared by svanidz1, malcolm, ma5termind, nabila_ahmed, allllekssssa, forthright48 and Mehdi. Thanks to wanbo, danilka.pro, tunyash for testing the challenges.

Scores of the problems:

  • 5 [70% score for the 1st subtask]
  • 15 [50% score in the subtask]
  • 30 [30% score in the subtask]
  • 50 [25% and 50% score in two subtasks]
  • 70 [Approximate problem]
  • 80 [40% and 70% score in two subtasks]
  • 80 [20% and 50% score in two subtasks]
  • 100 [Binary score, must pass all the test cases to get positive score]

Editorials will be live soon after the contest ends.

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

»
8 years ago, # |
  Vote: I like it -73 Vote: I do not like it

As always when I am setter I really like to write comment :)

I think that not only students should participe on the round, for me tasks are valuable and should be seen by many other contestants. Also I do not expect round as some of previous CodeSprints where we will have a low number of good solutions for last three problems and first full score after one day :)

There is a lot of subtasks there is a lot chance for receiving points, it would be very bad if you don't try each task !

One approximate task, it is interesting feature, it will make contest even more competetive than before.

About my task, you will decide whether you like or not :) I think that last three problems which I have invented (this is the first of that three) are my best and hardest tasks. Simply, for me, I achieve one higher and for me better step in solving and preparing problems.

Good luck to everyone, but my university will win :P

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

Are PhD students eligible for prizes? or you have to be an undergraduate?

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

    Yes, PhD students are eligible for prizes.

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

Are highschool students eligible to win prizes?

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

    It's a university codesprint, high-school students can't win prizes, but you are welcome to participate.

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

Guys. Please. Do not change. The rules. At the middle of a game.

Now last problem have binary scoring. Now your last submission time is using as a tie-break. Problemsetter of last problem said that he will change the test cases, because I told him my old solution with complexity N^2 passed.

I'm not in top 3(I could be in this way), but people who are in top 3, they tought they will be still on that places. You can't want that wait for three days on your computer. When something done, people won't go back to change it.

AC is AC. Wrong rules are wrong rules.

There's a really nice quote. "Don't try to change the past, learn from them." But why HR doesn't learn from them? In every contest it start as cumulative or last time tie-break but what happens next? It changes in middle of contest :))

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

    There was some mistakes from us, I am sorry about that.

    1. The last problem was supposed to have binary scoring (mentioned in the statement from the beginning). But somehow it wasn't marked as binary in server. We fixed it as soon as we saw it, there was no change in rules.

    2. Again the tiebreaker was supposed to be "last time", it was announced that way in landing page and cf blog, but again we made the mistake of not marking it properly. It is also fixed.

    I understand why you are upset, I apologize for the mistakes.

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

      Yeah people apologize. But you can't fix the broke in their heart...

      BTW, nevermind man, shit happens sometimes. It happens 1% times on CF and it happens 7473732773% times on HR. We can not do anything to fix it.

      EDIT: There're in the rules. It's nonsense sentence. People will follow the scoreboard or rules? What if you won't change the scoreboard and change the rules because so many people will be effected? What if tie-breaker will change but not binary scorin? Maybe you forgot the change the statement not the scoring? It was in the rules.

      Think you're in a war. And killed your enemies. But you realised it's not even unsuitable for war. What you gonna say? "Ooops sorry, it's not allowed :))"?

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

        No offense, but you contributed to this "7473732773% times" on HR too:

        Link

        I solved this problem by inadequate solution and I am solving like in average 2 problems for each contest with such inadequate solutions. I am going to make post about my inadequate solutions for each round soon.

        Here is my pseudocode solution for this problem:


        S=0
double dy = 10000000./n;
double dx = (maxx-minx)/dy;
for (double i = minx+dx/2; i <= maxx; i+= dx)
   S += area of triangles on the line x=i //for example for sample case for i=3 area will be equal to 3, for i=2 area=4
print (maxx-minx)*S/dy

        Full code

        I don't know, why tests are so weak, so it gets 100% score.

        If you want to make HR better, start with yourself.

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

    For sure, it is bad that there is things like this on the contest... I agree everything should be ready and well preapred before round.

    But for the first two things I can not tell they are so so bad. Binary scoring is mentioned in the text of problem and it is also mentioned on the blog, so there is no reason to believe you will receive some points for it at the end without all passed testcases. It was changed as soon as we noticed mistake. The same story about tie-break, everything is written in the rules and you should believe to the rules ( honestly I saw it very fast but I didn't read rules because I am not participant :P ) . Generally I think tie-break and current place on the standings are not so importnat for solving tasks on the contest -anyway you will try to solve it as fast as you can.

    For the last thing I agree AC is AC. I didn't notice that someone with AC got WA and something was changed in the test data. In case there was mistake it is really bad !

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

      "The same story about tie-break, everything is written in the rules and you should believe to the rules"

      It was fun :P

      It's not happening for the first time, and one time they didn't change the scoring system to people not get affected.

      But yeah, we have to believe in rules :)

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

        To understand me, I am not lawyer of HR, at least until they are not paying me for that :D

        I really think everybody should believe to the rules and tc can not be changed during the round, only if there is some bug with correctness and it won't affect a lot of on results (for example beginning of the contest and 2-3 guys got WA, and you change data fast). Everything other is not good, but still I don't see something was changed on this contest :D

        P.S. I hope you will get full score until the end of the round :) Also I would like to hear your opinion about all tasks or about contest at the end of round, normally it doesn't have to be good if you don't like it :D

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

          Problems are good but because of those, round isn't good. For example you said "binary scoring also mentioned in blog". On CF? A Hackerrank round? Isn't it nonsense? :(

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

            It was mentioned in problem statement too (constraints section).

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

              I fuck's sake please stop saying this. The statement can also wrong, actually most of times. You want to be right but you can't just say we mentioned it. Maybe problemsetter mentioned it then admins decided to binary scoring sucks and cancel it? It happened one of my problem so I thought like that.

              But I understand you "It's mentioned". It's okey but not enough. Try to do everything fine in next time. Don't think there's no problem in this comtest.

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

                listen, i never said we didnt made mistakes, i apologized for that and thats the only thing i can do. Still you kept complaining rudely. Mistakes can happen, we tried to do the best we can, still if you dont like it, i am again sorry. now please carry on with your life, it's not the end of the world.

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

                  I understand the mistake part. I understand you apologize. They can happen and we can not do anything to fix them after some point. Just try to better next time whoever doing these things.

                  The main part is you try to be right. I can understand an "I'm sorry.". But if you defend the contest with "We mentioned it in statement" it's logical but doesn't mean there's no wrong. I just want you to accept your fault. If you're sorry then it's okay. But if you think there's no bug in contest, there's a problem.

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

                  "" For example you said "binary scoring also mentioned in blog". On CF? A Hackerrank round? Isn't it nonsense? :(""

                  I didn't defend the contest, i just defended this, in my comment I said it's mentioned in the statement, not in the blog. (That doesn't mean the contest had no bug though, the mistake shouldn't have happened.)

                  Anyway, I think we reached the end of this discussion now. Thank you and good night, hopefully this won't happen again.

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

            Binary scoring is also mentioned in the statement :P So there is well written about it.

            These blogs are good thing, beacuase people have option to discuss tasks at one place and share opinions...

            I respect each opinion and at least I can try to make all things in my domain good as I think they were till now.

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

Let me ask some stupid question. I'm a master student. Why the scoreboard shows me as an alumnus? and how to correct it?

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

Approach for " Unique Divide and Conquer " ?

Didn't get the editorial .

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

    Editorials are available now, check.

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

      By "get" he meant "Didn't understand the editorial".

      And yeah I was also quite confused by it at first, I just read it another time this morning (my timezone) and understand it now.

      I'm of course not quite sure which part you didn't understand so please do clarify if I'm not touching on the important parts. I assume you understand that f(n) = n*some_value(n) where some_value are all the possible partitions less than n/2 etc.

      The gist of the rest is that the DP that follows is a calculation of ALL the possible ways to partition the n nodes into different sized subtrees, they do this by iterating over the subtree which has the smallest size and then using dp[n-i] which was already calculated earlier to get all the possible partitions of the rest.

      In the end they then use the formula but just for the subtrees with size bigger than n/2 to remove all the partitions that have subtrees with size bigger than n/2.

      I hope that helps you understand the editorial and then you can read it again and hopefully get it? If you have any more questions feel free to ask.

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

Really nice problemset! Thanks for the last problem. It was the best problem I have solved in a while.

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

    Happy to hear some positivity despite the issues. Thanks a lot.

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

How can I see others solution in Hackerrank? Unfortunately I didn't found any option to communicate with one moderator. Specially i wanna see the solution of Problem Walking the Longest Path (Approximation Problem). Thanks in Advance.

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

    You can now go to submissions and download solutions.

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

    Here is my code

    Here is idea: try to start our path from one of 100 vertices with the lowest degree. Then we try to go in two sides from this vertex by dfs(trying to go to the vertex with the lowest degree). We take the longest path from 100 paths.

    After that we will try to make our path longer by adding vertices. Imagine we have edge x1-x2 in our path. We can add another vertex y to our path, if edges x1-y and y-x2 exist in our graph.

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

    I got full score just by starting dfs from vertex 1 and going to the neighbour with the least unvisited neighbors. code

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

Just curious, why does it take so long for rating change on hackerrank when on codeforces ratings change in only 2 or 3 hours?

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

When you're stalking tourist's code for the last problem and find this :

brexit[v] = order.size();

xD

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

In the last problem, if the author was going with the solution, why not make the constraints smaller, as which is not very nice.

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

I wonder how I can receive the bitcoins?And can the T-shirts be sent to places in China?

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

I will post my solution for the last problem here, as I have read the editorial out of curiosity and I think it is overcomplicated.

First, note that every query (a, b, c, d) can be split into (at most 16) queries of type (1, a, 1, b). You should practice how to do that on paper.

Now, a query of type (1, a, 1, b) could be easily solved on the Euler tour linearization of the tree (the one where you insert value[node] at position beg[node] and erase it at position end[node] in the linearization). Now, in order to solve a query, you could keep two frequency arrays and dynamically compute the result as you insert / erase values from your "data structure". That would have complexity O(beg[a] + beg[b]).

Now, you can use a favorable sorting of the queries to compute the queries in total time O(q * sqrt(N)) (people call that "Mo's Algorithm"). No HLD and overcomplicated stuff like that.

If you think I need to explain it more thouroughly, please feel free to ask.

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

Please explain two-pointer approach here. https://www.hackerrank.com/contests/university-codesprint/challenges/hackerland-radio-transmitters/editorial

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

    Sorry in case I miss something, but for me this looks very easy.

    Sort array of coordinates ( possible by counting sort to achieve O(n) complexity). Than you have one poiner for place where you will put transmitter and one for the furthers point for the right house. After it you will first move left pointer to become right and calculate that distance, after it you will move initialy right more right and repeat process. I didn't code it, but I can write code if it is not clear.

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

      Why is this correct?

      Assume array is sorted.

      Instead of code, can you be more clear in intuition behind or proof.

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

        Always is optimal to put transmitter as right as possible. In case we put it one cell left (on x-1 instead on x) we covered the same important points from the left side and one point lower from the right(maybe hous maybe not). So our task is something like find the furthest important point(house) on distance <=k on the right put transmitter, from that point find first important point on distance bigger than k on the right and repeat process for that point.

        I really don't understand what is not correct, this is really easy greedy. Maybe you think that is not only possible strategy, you can also do the same thing from the last point to the first and than younare doing zhe same thing only on the left side.

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

          I did using binary search because I understand that when k is fixed, what is k in yours?

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

          I am sorry, I forgot the problem.

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

            K is distance where transmitter can send signal. Same k as in statement. Maybe you thought about some other task :D

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

For this problem BOB and BEN, How come the answer for 2 trees with nodes 4 and 2 respectively is the first player. I know k is insignificant in the question.

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

    First player destroys tree with 4 nodes. Second player destroys one node from 2 and then first player finishes.

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

In problem BOB and BEN, why we go from a valid tree of size to n to a valid tree of size n — 1, For example, n = 8, k = 3 if you delete node 6, it is not a tree of size 7 of given type.

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

Who are the top 100 university students to win prizes?

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

Why downvotes, I had a genuine doubt.

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

has anyone received any email regarding prizes? I haven't received an email for the previous competition too (NCR Codesprint)

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

Did anyone receive the bitcoins or the T-shirt confirmation mail?

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

    I didt recieve my hoodie and tshirts from HR contests(it's ok, they said they cant send them to Russia). But i also didt recieve bitcoins for the World Codesprint April(April 2016), bitcoins for the NCR Codesprint(5-7 November 2016) and thsirt for the Booking.com Codesprint(August 2016)

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

I received a #codelikeagirl t-shirt today :D well, thanks, I'll try

→ Reply