belowthebelt's blog

MayHem 2015
By belowthebelt, 9 years ago, In English

Hello, everyone!

I want to invite you to participate in May Medium Contest at HackerEarth — which is called May Hem. The Contest is scheduled on 30th May. The duration of the contest is 2 hours. It's a play on a word that denotes chaos — hopefully, in a good way for this contest.

So, go for it, give it your best shot! There are amazing prizes to be won!

Link to the contest: http://hck.re/sUY9S1

sentinel45 is author and editorialist of this problemset, while lamphanviet is the tester for this contest.

Top 5 of leaderboard will also receive prizes:

$50 Amazon gift card + HackerEarth T-shirt
$30 Amazon gift card + HackerEarth T-shirt
$20 Amazon gift card + HackerEarth T-shirt
HackerEarth T-shirt
HackerEarth T-shirt

Good luck, everyone! :)

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

Comments Comments (4)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think that I hacked some of the tests for the second problem and I got full score:

Solution for 88 points: http://ideone.com/cnRd5p

Solution for 100 points: http://ideone.com/mAceb4

The only difference is in line 65:

88 points:

for(cnt=1;cnt<=n;cnt++,idx1=next(idx1),idx2=next(idx2))

100 points:

for(cnt=1;cnt<=min(n,1000);cnt++,idx1=next(idx1),idx2=next(idx2))

Anybody else who did the same? xD

BTW, how to solve the first and the second problem. For the second, I can find the maximum number of inversions fast but I don't know how to find the index fast.

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

    You can read other solutions now.

    For first problem, I used binary search to move to how many wavy numbers do not exceed N?, and this new task can be solved with pretty standard DP, where we build number digit by digit and store all required information as parameters of DP (current position, last digit, current direction, is our number already less than N).

    For second problem, I wrote down initial array two times and then counted inversions for all subarrays of size N (sliding window works well). Comparing two substrings fast is a very well-known problem with a lot of possible solutions — my choise was hashing.

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

      I ran over your solutions and I understood them, thank you for the additional explanation :) And congratulations for the place you took! :)

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

        Thanks :)

        Starting time of a contest was very uncomfortable today. I had a hard choice between writing a maxflow on GCJ and switching to HE contest; looking at standings now, I think that choice I made was right — with horrible performance I still managed to beat much stronger contestants, and was close to winning a contest — only because I started eariler. And I wasn't going to qualify for onsite at GCJ anyway, even in case I passed to the next round :)

        I think that in future HE admins should set contest time in such a way that overlapping with other big contests is avoided. In this case it will attract more strong contestants. Usually it isn't hard to find a slot for 2h-long contest.

        Anyway, I can't miss a contest named after Norwegian black metal band. Or after American music festival, I am not sure...

        → Reply