Hello everyone!
I want to invite you to participate in June Clash at HackerEarth. Contest is scheduled on June, 20. Contest duration is 24 hours, so there should be some comfortable time for every timezone :)
There will be five tasks in a problemset. Four of them are standard 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.
shef_2318 is author of this problemset. He already prepared January Lunchtime 2015 and a few interesting problems for CodeChef Long contests, and also he was both author of April Clash and co-author of May Clash.
I was working on this contest as a tester. As usual, 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. I was glad to work with shef_2318 again :) Also I want to thank to MDCCXXIX for technical help and doing his best on fixing all issues and improving HackerEarth platform.
There will be quite a lot of different contests over the weekend, and besides interesting problems, I have another reason for you to participate in this one:
Top5 of leaderboard will also receive some nice prizes:
- $100 Amazon gift card + HackerEarth T-shirt
- $80 Amazon gift card + HackerEarth T-shirt
- $50 Amazon gift card + HackerEarth T-shirt
- HackerEarth T-shirt
- HackerEarth T-shirt
I hope everything will run smoothly this time. Good luck to everybody — I hope to see you at the scoreboard :)
Hello everyone!
I want to invite you to participate in June Clash at HackerEarth. Contest is scheduled on June, 20. Contest duration is 24 hours, so there should be some comfortable time for every timezone :)
There will be five tasks in a problemset. Four of them are standard 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.
shef_2318 is author of this problemset. He already prepared January Lunchtime 2015 and a few interesting problems for CodeChef Long contests, and also he was both author of April Clash and co-author of May Clash.
I was working on this contest as a tester. As usual, 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. I was glad to work with shef_2318 again :) Also I want to thank to MDCCXXIX for technical help and doing his best on fixing all issues and improving HackerEarth platform.
There will be quite a lot of different contests over the weekend, and besides interesting problems, I have another reason for you to participate in this one:
Top5 of leaderboard will also receive some nice prizes:
- $100 Amazon gift card + HackerEarth T-shirt
- $80 Amazon gift card + HackerEarth T-shirt
- $50 Amazon gift card + HackerEarth T-shirt
- HackerEarth T-shirt
- HackerEarth T-shirt
I hope everything will run smoothly this time. Good luck to everybody — I hope to see you at the scoreboard :)
Upd. Contest has ended :) Thanks to everyone for participating :) Congratulations to winners:
1) kutengine
2) FatalEagle
3) anta
4) SoMin Mun
5) Kmcode
Could you schedule it on Sunday? As you might know, there is the IPSC on Saturday.
What are some ideas that can be applied to the approximation problem? I tried a lot but nothing get high points
You may check codes of other contestants now. Also I hope that some of them will later write brief explanations for us :)
I believe that most of relatively easy (and at the same time working not so bad) ideas are related to local optimizations. I haven't read recent codes by top contestants yet :) But at first glance it seems so.
While testing a problem, I tried a following very simple approach: generate some random approximation and run a hill climbing by doing flips of a single cell (picked randomly). Even with an unoptimized code and without any additional heuristics it scores below 15k points — so it would be probably enough to get #7 in a contest without any additional effort.
Thanks to everyone fore participating :) It's nice to see a lot of high rated coders in standings. Also thanks for a lot of action at the top of the standings in last few hours (and even last few minutes), it was interesting to watch it.
I hope you managed to understand statement of Good points :)
Short editorials for standard tasks and codes by author and tester have been added now. They will be extended with some more details later; I hope that some sort of editorial for approximate task will be also ready a bit later.
Feel free to ask any questions and discuss problems.
Where are the editorial? I couldn't find it.
UPD: No need to answer; I've found it now.
Thank you for such a nice contest . I have a request please make editorials according to your own solution. It helps the understanding process. In editorial of DigIT you used 3-D dp of position remainder flag while in solution it is 4 -D dp. of which i have no clue what state represents
Thanks for pointing it out. That part comes from an old draft; now I have fixed it.
Missing parameter is used for storing sum of digits.
Thank you so much for a quality contest, guys. The participation was great, also the problems were pretty interesting, as well. The moment when I managed to understand the idea behind Good points was amazing. Tricked us all! :D
@I_love_Tanya_Romanova: I've forwarded your comments/feedback regarding to comments to the Dev team, by the way. I'm sure that it will be taken care of in future contests. :)
I liked the approximation problem, despite having very little time to work on it [I only started participating in the contest very late, at 12:30 AM in my time zone; and at 4 AM I was too tired and went to bed, only to wake up several hours after the contest ended :)].
I am curious if the tests were generated in such a way that the best possible answer for every test was 0 (i.e. if they were generated by turning into zeroes some entries of a valid "visibility" matrix).
In any case, it would have been nice to have more information about the test case generation process. I had some approaches which were scoring much better on my local tests, but much worse on the official ones.
It's a bit unusual not to see you in the top, but thanks for the participation anyway :)
Test data for this problem is divided into 2 groups. The first half consists of tests that have best possible answer 0(but if I'm not mistaken participants got 0 only on tests 1 and 3). They were generated from valid matrices indeed. The second half was generated from "spoiled" valid matrices — some small(by absolute value) random numbers were added to positive numbers, so these tests are very likely not to have the best answer 0.
We have discussed providing information about test generation but decided not to put it.