kevinsogo's blog

HackerRank University CodeSprint 4
By kevinsogo, history, 7 years ago, In English

Hello Codeforces Community,

I am glad to share HackerRank's University Codesprint 4 starting on 23rd February 2018. The contest duration is 48 hours.

The winners of the contest will win up to 1000USD cash prizes. The top 100 will also win awesome hoodies. (The 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 ranklists for schools.

There will be 7 algorithmic challenges in this contest.

The problems were prepared by Alladdin, prateekg, niyaznigmatul, BishalG, anuj95, wanbo, svanidz1, kevinsogo, xennygrimmato, geek_geek, Wild_Hamster, shashank21j.

Good luck and Happy Coding!

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

»
7 years ago, # |
  Vote: I like it +47 Vote: I do not like it

What happened to the prizes from World Codesprint 12

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

    According to the admins, the prizes for WC 12 have started being processed, and people should be receiving them this week.

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

      It's been 1 week, I have neither received an email about the prize nor a response to my support request about prizes.

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

      Has anyone received an email from HR yet?

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

    +

    edit: OMG why such downvotes. How can you do this? This is outrageous, it's unfair! /s

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

I think codesprints should be 5h only (unless there are approximate problems). 48h favours to people that have more free time, also since each university is like a team, there is more time for the spread of solutions among members of the same university (or even country, I know cases about this).

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

    There are universities from all over the world, 5h only is unfair to those whose contest starts at 12am.

    At least make it 1 day long.

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

      yes, the current start time is not appropriate. Maybe atcoder usual time is not too late or early for most time zones?

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

"The winners will be required to give proof that they are currently enrolled in the university they represented during University CodeSprint" I also read that on the site and thought that it is worth asking: if I'm currently enrolled in a high school (not a university), there is no way I could officially take part in the contest (and, thus, be considered for prizes as well), right?

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

    Yes. If you are not in university, you will not be eligible for prizes, but you can still participate.

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

Wtf is going on with these weird "you need to implement function X an function Y" in statements which makes an impression that this is an "interactive" problem and then showing standard input and output? That's a significant difference.

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

    It's because you're given template C++ (but not C++14) codes which handle I/O for you.

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

      I didn't see any functions in my templates. I checked them but there was only a standard hello world or something. And I think that requiring coding persistent tree instead of typical one for the profit of not handling I/O is a pretty bad tradeoff.

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

        Template code for language C++ for the first task:

        Imgur

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

          Funny, for me it was "hello world" everywhere. But either way, firstly describing these functions and then describing input and output was confusing. I was already wondering where can I copy some persistent tree from in E because I thought this is whole point of existence of these functions.

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

There's something wrong with G's checker.You don't check whether the sum of columns and rows the participant's program chooses equals to the answer the participant's program gives. I can work out the answer and simply choose all the rows and columns to get it accepted.

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

    Does it really make a difference? I don't think anyone who solved an "expert" problem would get WA after fixing the checker.

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

"The winners will be required to give proof that they are currently enrolled in the university they represented during University CodeSprint."

If not all of the participants in top 100 are currently enrolled in university than will hoodies get passed to participants whose rank is above 100?

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

    Can someone confirm this? :P My rank on the student leaderboard is 102 and I found 2 people above me who are in one of the countries where prizes aren't allowed due to legal restrictions.

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

      I guess many of the top 100 won't be enrolled in any college currently.

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

Ehm, I might sound a bit rude, but problem C aka Two Kings is absolutely disgusting. Was that supposed to be funny or sth?

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

    I think it's what Halim tags in CP3 as "Time-Waster Problem" :/

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

    Well, the country is terrible with Two Kings :)

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

    It was the reason for me, to not join this contest. I did not want to waste my time on this.

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

Who else feels like crying after seeing a chess problem on HackerRank ?

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

It seems that the issues with G's checker haven't been fixed till now.Do you really want to leave the issue till the end of the contest? I'm sure some accepted submissions will fail after you fix the checker(my first submission as an example).

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

    lol what do you expect of hackerrank? there are bad checkers, lazy editorialists, and tedious problems.

    if they continue giving chess problems then HR will go bankrupt

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

In two king's problem i believe there is an issue with the checker. The sample output differs from the expected output, well i tried to submit either ways:first describing the positions of the black pieces and second i only printed the minimum no of black pieces and not the positions. Both the ways sample test case is showing wrong answer. Please help if anybody else was facing the same problem !

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

Finishing 101 feels like an absolute win :D

My hate to chess kings has grown.

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

feedback:

A. Trivial

B. The c++ template that you provide (that reads input) doesn't work, it gives Abort Called.

C. Probably many people hated this problem. Also it was confusing that according to the checker the correct answer of the sample case is only 3 2 (without the positions of the queens). However I think it was not that bad (maybe I'm biased because I like chess :) ), but at least we have to guess/prove that knights are not necessary.

D. standard suffix array problem.

E. standard (and easier than D), actually is a simple variant of spoj DQUERY

F. nice data structure problem. Few people solved it during the first day, so I think it was ok.

G. another standard problem (and easier than F), I've seen it in codechef, some icpc regional and I think that even on hackerrank!

Regarding scoring: Partial score is unfair, shitty optimizations get some additional points. It should be full points for full subtasks.

TL;DR In general, the round looks more like an educational round. IMHO so far, the best round on hackerrank was the first world code sprint, ...now the frequency of contests and quality is decreasing.

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

    Could you please elaborate on F? I managed to get the partial solution for F where n ≤ 4000, but couldn't move any further.

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

      Yes, please elaborate the approach for F (Magic Value) because the editorial is not available for that problem. The explanation in the editorial section is actually for the previous problem.

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

      I give some hints in the last part of my post https://aleigorithms.wordpress.com/2018/02/25/hackerrank-university-codesprint-4/

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

      I will try to explain my idea.The main intuition behind my idea was convex hulls or may be convex hull trick (I appreciate if someone can give some direct solution using either of them as blackbox). Skipping easier parts the key problem is max (k-i)b[k].for each subarray starting at index k. sum over such things.
      lets denote val[i]=(i-k)*b[i].
      So some key observations:
      1. if k1 < k2 and val[k1] >val[k2] then there is no point in considering k2 in further queries.
      2. And also above property is transitive.

      So now we maintain data regarding cross overs of adjacent essential points and update them according based on the data. And to be noted is each update must remove one element from keynote list.

      To the updates part a seg tree will work with range overwrite operation.

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

    Did Mo's algorithm pass for E? I had to go offline.

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

    D can also be solved using rolling overflow hashing.

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

Wow, the tasks were so poor I can't even... Only F was kinda interesting, but seriously, does anyone think that E could be original? I've seen that so many times. G was a failure as well, so standard I couldn't believe my eyes when I read that this is supposedly the hardest problem. Ugly C as well. But won 500$, so at least I earned something for the cost of wasted time :p.

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

    Can you give me insight on how to construct the bipartite graph in G(I don't really understand from their editorial) or another editorial that explains a similar problem ? Thanks !

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

      Let the set of vertices on the left represent row, and the set of vertices on the right represent column. If there is a cell (x, y) that is painted, connect x on the left with y on the right. What we need to find now is the minimum vertex cover of the constructed bipartile graph above.

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

        Oh yea, that seems so easy now. Thanks !

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

    For me both tasks were new, I know there is another similar on Internet , but still they were pretty easy. When I read 5th task, first I wrote Fenwick tree and then start solving task :D

    P.S. Will someone regrade last task ?

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

How to solve Unique Art?

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

    You can use MO's algorithm to solve that question.

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

      I used but got TLE!

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

        because you probably used a map, you need to convert numbers from -1e9,1e9 to 0,1e6 and use an array instead.

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

          Well, this mo should run in , how does it fit into the time limit? :D

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

        This is my solution using MO's.

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

    Refer to DQUERY solution using BIT here.
    For this question, ans= Number of distinct elements in range — Number of elements having L[A[i]](last occurence) within the range.

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

Shall we still expect to receive hoodies?

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

Have anyone received the hoodie yet?

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

    Nope :(

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

      Haven't even received information about hoodies from HourRank 26, which was 10 weeks ago.

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

    I have received it (to Lithuania).

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

      Did you receive any email from Hackerank after the end of contest?

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

        Yes, for claiming the hoodie. It was on 16 March.

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

I got 3rd rank, and I waited some message happily and excitedly (^_^).... and 3 months have passed (;_;). Can I get prize? (EDIT : This is my foolish mistake. Please ignore me.)

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

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

    That's interesting. I got second place and was contacted pretty quickly by a really responsive woman. Maybe that's the country that somehow makes the difference? Dunno.

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

      I recheck the my mailbox and found mail. I'm terribly sorry for hackerrank .... thanks swistakk

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

        I have got 65th place and still did not any e-mail or any answer about the champion hoodie. Can I get the hoodie? :)

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

Asking again

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

I just want to ask: does contestant with rank in top 100 in student scoreboard (but rank > 100 in overall scoreboard) win a T-shirt? I was in top 100, but got no new regarding my hoodie.

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

My rank is 85 in the student leaderboard and 102 overall. Can I expect to get a hoodie? I have not received any email yet.

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

I want to say that I received my hoodie today! Thanks for it!

→ Reply