I_love_Tanya_Romanova's blog

May Clash 2015
By I_love_Tanya_Romanova, 9 years ago, In English

Hello everyone!

I want to invite you to participate in May Clash at HackerEarth. Contest is scheduled on May, 23. Contest duration was increased comparing to previous editions — now it lasts for 24 hours, to make it even easier for you to find some time at least to try it :)

There will be six tasks in a problemset. Five of them are classic algorithmic problems with partial solutions allowed — you get points for every test that your solution passed. And the last task is an approximate problem — your score for this task depends on how good your solution is comparing to current best solution.

PrinceOfPersia is author of this problemset. Check his blog to get a taste of problems authored by him — he was a writer of recent Codeforces Round 299 (Div. 1), and also prepared few interesting contests in CF gym.

I was working on this contest as a tester. I would like to say that I find this problemset interesting, I hope that some problems will be not too hard for beginners (don't give up and show your best with partial scoring) and some other tasks are challenging enough to attract more experienced contestants. It was nice experience to work with PrinceOfPersia on preparing problemset. He really impressed my by the speed with which he is generating ideas :) Also I want to thank to MDCCXXIX for technical help and doing his best on fixing all issues and improving HackerEarth platform.

If you are still not sure about participation in this contest — I want to add one more thing,

Top5 of leaderboard will also receive some nice prizes:

  1. $80 Amazon gift card + HackerEarth T-shirt
  2. $60 Amazon gift card + HackerEarth T-shirt
  3. $40 Amazon gift card + HackerEarth T-shirt
  4. HackerEarth T-shirt
  5. HackerEarth T-shirt

I guess some of top contestans will be busy because of ACM ICPC World Finals — it only increases your chances for a prizes :)

Good luck to everybody — I hope to see you at the scoreboard :)

UPD. First announcement said that contest is scheduled on May, 16. Due to unavoidable reasons it has been moved on May, 23 now.

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

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

I'm gonna register at hackerearth just for this contest
EDIT: seems like i have already registered :DDD

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

Necessary rules' clarification: Is time a factor? More precisely, if there are too many ties among the top places, can time become a factor? I'm sure you know what I mean.

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

The contest started almost 7 hours ago, but it only has 5 standard algorithmic problems. What happened to the 6th task, the approximate/challenge one?

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

    We are very sorry. Due to some unavoidable reasons we didn't add approximate question in this round but pattern of questions remain the same for next clash contests.

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

      You should have announced this before the start of the contest. Top five places have been already taken by the ones who started to solve problems at the very beginning.

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

        I agreed. I apologies for it. This post is written by I_love_Tanya_Romanova and for some reasons he was not able to update this post.

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

          It is very strange type of contest, result depend on time zone of solver. More reasonable is to ignore time penalty or count time only from moment of opening first problem of contest.

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

Couldn't log in using social login.

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

    Thanks for reporting the issue. Issue has been fixed.

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

The problems for this contest were written by FatalEagle (1, 2, 5) and shef_2318 (3, 4).

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

And the last task is an approximate problem

I have just registered in HackerEarth so I am not familliar with the site. Can somebody please tell me where I can find the sixth task?

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

Can someone, please, explain the solution to Array Divider?

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

    .

    UPD: fixed small typo, thanks to rmn

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

      Wow, really cool solution. So in the end we should just find the partition which minimizes the sum of squares, and then put it into this formula to get the result.
      The funny thing is, when I first read the problem statement, I somehow misunderstood it and implemented the solution which tries to minimize s12 + ... + sk2. Now it turns out that all I had to do is print not ans, but k * ans - total_sum * total_sum :)

      PS. Shouldn't there be in the third equation?

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

    My solution was DP. Sum of (Si-Sj)^2 for all i<=j is equal to:

    (k-1)*(S1^2+S2^2+...+Sk^2)-2*S1*S2-2*S1*S3-...-2*S1*Sk-2*S2*S3-2*S2*S4-......

    We can see that if we start from the i-th position of the array and split it into j blocks with sums P1,P2,...,Pj, then the current (not neccessarrily the minimum) X-value (given in the statement) for the array starting at the i-th position will be:

    (k-1)*(P1^2+P2^2+...Pj^2)-2*P1*P2-.....

    which is:

    (k-1)*(P1^2+P2^2+...+Pj^2)-2*P1*(P2+P3+...+Pj)-2*P2*P3-2*P2*P4-...

    Let's take a look at the X-value starting at the index when we split the first (of those j, not k) position, that is the position where we stop with sum P1 and start with P2. Let that position be m. The value is:

    (k-1)*(P2^2+...+Pj^2)-2*P2*P3-2*P2*P4-...

    So we can represent the X-value for the array starting at position i, that should be split into j blocks as (k-1)*P1^2-2*P1*(Sum of the elements to the right)+(X-value for the array starting at position m+1 and needs to be splitted into j-1 blocks).

    I know that my solution isn't perfextly explained, but I hope that my code will help you to understand it. Can you please tell me how to solve the second problem if you have solved it since I can't come up with something better than O(N^2).

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

I am really sorry for the issues with this contest.

On May 20-23 I was in a hospital, and I had no possibility to watch over contest preparation. However, on May, 19 there were no major signs for me that something should go so wrong — so, honestly, I didn't even thought that it will be so screwed up. When I finally got an opportunity to check contest standing&discussion last night, it was a shocking bad surprise for me.

I hope that there will be no similar issues in future, and upcoming contests will leave only a positive impressions :)

zxqfl already said names of problem setters (with no PrinceOfPersia in this list), so it is does not looks like that by telling that not an intended problemset was used I will unveil some inside information. Still I think that problemset by PrinceOfPersia, which I was testing and for which I prepared drafts of editorials, is a nice one, and I hope to see it used for some other contest in future :)

I believe that all this story will be a good lesson for me and all other people involved.

→ Reply