Shafaet's blog

By Shafaet, 8 years ago, In English

Hello CodeForces Community!

I am glad to share that HackerRank's CodeStorm (CodeSprint on Algorithmic Programming Challenges) is scheduled on 29-October-2015 at 16:00 UTC. Contest duration is 24 hours.

Go ahead and register now to show off your coding chops, and win amazing prizes like GoPro HERO4 camera, Bose Speakers, FitBit Charge, HackerRank hoodies and t-shirts. All participants who completely solve one challenge will get $100 of AWS credits.

Also, you'll get an opportunity to connect for a career opportunity with CodeStorm contest sponsors — like ErosDigital, Indeed Prime, Slice, Steelhouse, Sightline Systems, SWATT etc. Contest site will be continually updated to reflect upcoming sponsors.

The problems were created by malcolm, svanidz1, Timur_Sitdikov and Shafaet. Thanks to wanbo and allllekssssa for testing the problems.

The contest will be rated. If two person gets same score, the person who reached the score first will be ranked higher.

Editorials will be live soon after the contest ends, I invite everyone from experts to beginners to participate and solve challenges. I hope everyone will enjoy the contest.

Update: The max scores of the problems will be 15-30-50-70-90-90-125. The problems will have partial scoring unless we mention about binary-scoring explicitly in problem-statement.

Update: Some users got automated emails after the contest about prizes. Everyone with rank 11 to 100 will surely get the tshirt as mentioned here, we are investigating why that email went out.

GL&HF

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

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Tiebreaker is person to reach the score first.

So,

  1. time does not matter at all (and the answer to this question won't just suddenly change after the contest)?

  2. will there be some kind of partial scoring; if so, what kind and on which problems (in particular: on the hardest one)?

  3. will there be a problem with non-binary scoring per test?

(questions 2. and 3. can be summed up and "will there be a lot of ties?")

UPD: I feel silly for not asking 0. will the problems have sufficient difficulty for a 24-hour contest?

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

    Yes time matters, it will be the tiebreaker.

    There will be partial scoring (probably in most of the problems). If some of the problems are binary, we will mention it in the problem statement. I know we didn't mention it clearly in some contests in past, but that won't happen it in this contest. I will update the post with details about score of each problems before the contest. So to sum up, there won't be lots of ties.

    Any suggestion is most welcome :).

    (Btw, I edited the line you mentioned to make it more clear)

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

      In some recent contests, there were cases of hardest problems without partial scoring. That makes partial scoring on the rest of the problems useless, since the top of the scoreboard is what actually matters. And when there are ties at the top, it's about timezones or free time that day.

      The optimal solution is really introducing a challenge problem.

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

        Also partial scoring challenges should have at least good number of strong test cases. Otherwise sometimes it happens wrong solution get full points or 70% points.

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

          Why can't you do subtasks system(similar to ioi system) to prevent it?

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

            I really don't know that. When I was preparing 101 Hack and HourRank, I had big problems to make fair and correct scoring. Even I like binary score more than partial.

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

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

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

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

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

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

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

Please keep partial scoring for last 4 challenges.

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

is so difficult to post the exact time using http://www.timeanddate.com/?

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

@Shafaet/Organizers — Sorry if I sound ignorant, but can you explain how are RATED contests different from UN-RATED at HackerRANK? I understand the meaning, but on what basis you decide which ones will be rated. I am good at python, but see that your contest named "Pythonist 3" is not rated, why?

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

    First HackerRank now has several RATED competitions prepared by one author:

    -101 Hack

    -HourRank

    -Week of Code

    We have this contests 3-4 times in the month. Now you have CodeStorm- 24h long. Duration of contests are different, so everybody can find something interesting and good. I think that contests are pretty good (I was doing and watching task in last 3-4 months, before I didn't know a lot of about HackerRank). Now, I like at most CF problems(they have hacks, many users, platform is good...), but after it for me the best platform is HackerRank, after than CodeChef... SRM has good tasks, but platform (topcoder arena) is very bad and I lost 2-3 years of my life during one contest.

    Why other contests aren't rated. HackerRank has several better coders than me, probably than you. If they think the tasks aren't enough good for rating you must respect it. I saw several good and interesting task on that contests, but also I saw some unclear with strange solutions. Some companies organize contest for job, so they want harder level than usual round, or maybe they need more similar challenges (something important for them). The last type of contests like Java, Python... That can not be for rating. Many users don't know Java and Python, so results aren't real and correct for whole platform. You should get rating for solving programming challenges, not for the knowledge of a language. The main thing — rated contests must have something for every kind of programmers ( from newbie to legendary grandmaster).

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

    Good question.

    If a contest is language specific, company specific, restricted to regions or a new non-standard format like magic-lines contest, than the contests are not rated. Usually global contests with standard algorithm problems are rated.

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

I hope all the problems will be new, not like in the last contest.

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

    I tested one problem and it was new and nice for me. I beleive that our tastes don't differ much :) I saw many tasks of this authors till now and they were good. I can not participe official on this contest, but I am planning to do other tasks this afternoon.

    Our hopes are the same :)

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

    I really hope you will like the problems :). Please let us know what you think after the contest too.

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

      Questions are interesting. This is my first contest at hackerrank. I solved 1st, 2nd and 3rd completely. Stuck on 4th. Wont even attempt 5th, 6th and 7th as they are beyond my level currently :( Will editorial be given immediately after contest ends or after 2-3 days?

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

        Thanks. Editorials will be available instantly.

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

Does it matter that a participant start the contest late i.e. will my time start when i enter the contest or everyone's time will start right when the contest started ??

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

    It DOES matter, so start early. I know you may say some timezone will get advantage, but we don't have better option at this moment. If we start the time when someone enter the contest, cheaters will take advantage.

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

Were 19 full scores after 10 hours part of your plan?

The problems are quite interesting IMO, but this would've done better as a... 5-hour contest, for example. I don't have much of a motivation to submit my solutions at this point.

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

    Sorry, but I think no man on the world who can start with 24h-contest 10 hours later and beat some of top 20 guys on leaderboard.

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

      You're missing my point. I'm saying there are too many full scores. (28 now btw)

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

        Than I can not understand why you don't have motivation to submit code.

        I am not organizator of contest, so I can not tell you what is expected number of full scores. I think the tasks are enough hard to make difference between the best competitiors.

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

          My motivation isn't an objective factor of contest balanced-ness. It's the second least important part of my OP (after the banepost), don't bother with it.

          Continued by PM.

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

could you add a picture of the HackerRank t-shirts to your blog?

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

Anyone can give me an idea how to solve "A Game of Reduction" ?

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

    If you have the final list L, you can find the winner using grundy value, right? Now notice that grundy value for any integer between 1 to N is very low, the numbers reach single digit very quickly.

    So after getting the list L1, calculate xor of grundy values of every numbers, let the number be sxor. Now bob have to chose sum numbers whose xor of grundy values is also sxor, because sxor^sxor=0. If you know how many times a particular grundy value occurs before N, you can calculate it using simple dp. So the solution is precalculation+dynamic programming. Please see the editorial for the code.

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

    Calculate Sprague-Grundy function for each number from 1 to 1000000. Then calculate number of non-empty subsets with xor equal to xor of Sprague-Grundy values for given numbers. Observation: SG values won't exceed 3.

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

      SG vaule won't exceed 6 not 3. I hope you like this problem. For me it was very interesting.

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

        And 3 is a better bound than 6, which can be found just by finding them all and checking.

        Also with just 0,1,2,3 manually doing the cases was easier for me than dp (only a few cases).

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

          There were 2 cases for me: xor == 0 and xor != 0.

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

            I had additional cases with number of nimbers left (Alice didn't take all of them) from 1,2,3.

            This seems necessary, but it looks like your code also includes this? I see more than 2 cases.

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

              Nope. Xor != 0 cases pretty similar. One "for" for these cases.

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

                This code?

                I see 2 "if"s in each call to get() and 3 if's in the Xor>0 case. Am I missing something? Maybe not the latest code?

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

                  I meant that I don't distinguish cases 1, 2, 3. I don't have to write "if" for each of them

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

                  Ah okay, same with me. I just have 3 cases — all zero, one nonzero, and >one nonzero.

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

        Well, my solution considered values up to 3, not 6. I got full score. P.S. Nice problem :)

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

          Yes it is 3. I was testing that problem and I know that I get same grundy numbers as Shafaet, but I didn't print maximum value. Obvious it can't be more than number of digits.

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

I got the following message (rank 68):

"Prizes were awarded to the top 10. So close, yet so far. You could have made it if you had done better at Emma's Notebook."

Does this mean that I don't get a t-shirt?

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

    Rank 87 got the same message.

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

    Don't know who sent you the message, rank 11 — 100 will get Tshirts.

    upd: may be the message means you are not getting top-10 prizes.

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

    I love part about Emma's Notebook most of all :)

    They also suggested a problem Library Fine for me in order to improve my skills, that's so cute :)

»
8 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

Problem 7 (Little Alexey's Tree) could be solved on O(n log n), don't understand how author could miss it (solution almost the same as in editorial). Number of vertices should be at least 10^5 to avoid n^2 solutions (and there were a lot of them).

And imho it is strange to add antihash tests, but accept quadratic solutions

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

    The testers couldn't pass any n^2 solution. Can you please show me any n^2 solution that passed?

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

      Let's start a comment chain with increasing scores for O(n^2) solutions. I'll start with 62.5 points here

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

    Hi, I'm the author of this problem.

    Of course, we knew that there's a solution on O(N × log(N)). We intentionally allowed all the subquadratic solutions to pass.

    If any quadratic solution passed, that's fully my fault, I'm deeply sorry about that. Could you give me a link with any such solution getting AC?

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

    I understand the O(NlogN^3) solution from the editorial, but cannot come up with a O(NlogN) solution. Can anyone give me a hint ?

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

      Comparing two power-of-two linked strings could be done in log n operations (like in lca). Then count dfs-dynamics simple bottom to up, count best child-string for each vertex, using the same dynamics for children. State of this dynamics is length of best string and power-of-two links to prefixes of this string and its hashes. Result of this calculation could be interpreted as correct state despite of some oriented edges forbidden (actually forbidden half of edges, all from down to up). Then goes the most tricky part, count it from up to bottom, in each moment you have some state for the initial dynamics, where some new edges added and some edges become forbidden. In single moment still will be invariant that for every edge exactly one of its orientation will be forbidden. For every vertex A and each of its child B we will recalculate state of dynamics and forbid edge from A to B, then push dfs to B. In B we will add edge B->A, calculate answer for B, then do the same for B and its children. When dfs comes to some vertex X, state of dynamics is correct, because for all vertices except ancestors of X edges oriented from up to down (it is what exactly we need to calculate result for X).

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

        Thanks for your attention, but it's seems really hard to understand. Did you use divide and conquer like in the editorial ?

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

          No, instead of this I have two dfs.

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

      Could you please share a link to the editorial?

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

        Each problem has it's editorial in HackerRank

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

rank 11, dammit.

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

It's been about two months since the contest has ended and I haven't received the t-shirt yet.