Hey guys! December Clash at HackerEarth is taking place this Saturday. The contest lasts for twelve(!) hours, so almost everyone can find a time slot to participate.
There are five tasks, four of them are standard algorithmic problems with partial solutions allowed, while the last one is an approximation problem which will allow to determine the best participant.
I think that this format of competition is interesting for everybody because newcomers can do better than stronger competitors with a help of "12-hours dedication" strategy, while the strongest guys will enjoy fighting each other on the approximation problem.
The complete problemset is prepared by laoriu. It was very exciting to work over the contest with him. You may know this guy from preparing the Codeforces Round 277 (Div. 2). I did the testing part for this contest and would like to say that I wouldn't be able to solve all the problems without laoriu's help. So I find the problemset pretty challenging and strongly recommend you to participate! I believe that both math_lovers and implementation_lovers will find something interesting for them.
Hope to see you at the scoreboard ;)
Your HackerEarth link is incorrect
Fixed. Thanks a lot!
Is time penalty going to be used?
I don't see much point in making a 12-hour contest to accomodate for all time slots if you're going to penalize people based on what slot they choose.
There is a problem where you can get points in range [0, 1]. So ties are broken with a help of this problem, but not penalty time.
It looks like the contest did use time penalty as a tiebreaker... HackerEarth should really stop doing that.
Who's effected?
Does anyone have to be affected for it to be a bad idea?
I'll indulge you, though: if you want a case in which someone was affected, see http://www.hackerearth.com/brasil-national-programming-challenge/hof/ . Time penalty was the deciding factor for a 4-way tie in a 24-hour contest, in which timezones should never be the factor that decides who wins. (Note: I would probably still lose had I started at the beginning of the contest due to bad problem order, but I had to leave at 0:20 for an appointment).
If even after a tiebreaker there are people tied, let them tie.
Seems like approximation problem wasn't really approximation problem in your example :)
Anyway, removing penalty is a good point for long contests. I am not a HackerEarth developer, but will let admins know about your feedback. thanks.
"Thank god we have codeforces" == true. Remember that.
I took me 5-7 minutes to login with git and fill 39% of profile because of very slow page loading.
They've suggested to give them my TC log/pass (LinkedIn asked my E-mail pass, I gave them a fake, why hackerearth didn't asked me to do the same? just a joke :D). Actually, that was the first challenge, here is my solution:
One of their easiest tasks requires cin/cout speed-up and long longs, hopefully I got AC (site is designed as hiring platform, or smth else? I thought there should be job-interview tasks). I didn't know that ios_base::sync_with_stdio(0) is the first function that real-world programmer should learn after main(), I got +2 on their easiest task, I think now I'm doomed to work for food to the end of my life.
The first interesting problem I've coded has wrong testcase (I'm so glad to know it after the end of implementation process, but of course It's my fault that I didn't looked at the comments/editorials before even start reading the statement).
Also — you didn't gave me "First AC" badge, that hurts.
P.S. I have a constructive advice : change this smile in notification panel
to
because it's very cool to be honest
During contest time, are the submissions judged with pretest only, or full test?
You are provided with full feedback.
What is "CGPA/Percentage" and why do I have to fill it in in order to compete? (More generally: why do I have to fill in random forms when I just want to solve some programming problems? All other sites leave stuff optional...)
CGPA is cumulative grade point average. HackerEarth is also a hiring platform, so this information may be useful.
By the way, it seems that you are more eager to speak about little details/issues of whatever rather than solving some programming problems.
I think you mean HackerEarth. And yeah, Xellos is pedantic, and so, it is fun to read his comments :D
It should be optional but compulsory. That's just an example for bad UX.
Of course it could be done better. But my point is that in case one really cares, he can leave his feedback on a specific section of the website. However, this guy simply has a lack of attention to himself and nothing else.
> little details/issues of whatever
> why do I have to fill it in in order to compete?
In case you didn't get it: I AM UNABLE TO VIEW THE PROBLEMS BECAUSE OF THIS.
And I still don't get what it is.
In case you are still unable to view the problems I would suggest you some kind of special olympics.
"Still" unable to view the problems? After you told me absolutely nothing at all? Yeah, fuck you too.
UPD: It was all a total waste of time, considering I just found out I have to pack up and leave quickly. Awesome.
UPD2: Or not.
Why don't you just enter random number? :p
Anyways, CGPA = your average score of courses in high school / university.
Mhm, I googled that 10 is supposedly the best, so I entered 10. Because whoever cares about that.
High school / university? Why does it mix two completely unrelated systems?
Hi Xellos,
This field has been removed for this contest and for all future contest.
Thanks for your feedback.
Hmm, nice.
I entered 0 there, now i am afraid that it decreased my chances for getting a work very much:D
A suggestion for scoring of problem 5:
First, I'll explain what's wrong with the current situtation:
So, I would suggest a different scoring for future contests:
As for me, this problem should break the ties between top contestants, which are expected to solve all standard binary problems :) So it does not matter what is the difference between them: either 1e-5 points or 90 points. Since only top3 get the goodies and other do it for fun, current system seems ok for me. However, your suggestion will also do this job, and probably may make it better for some contestants out of the top of the scoreboard. I will tell admins about it.
Thanks a lot!
For P5, my code was literally "print 0" and it got 84.xxx points :D
Also, what is the solution for P3? I have a sqrt decomposition + treaps idea which I was unable to code correctly(some pointer problems in the treap struct)
And I get another tshirt. whoo /o\
For P3, first you must use the following transformation:
ai = a1 + (i - 1) * K - ai
After this transformation, the cost to convert ai...aj into arithmetic sequence is equal to the cost of making all elements equal. Thus the problem reduces to finding median & calculating sums, which can be solved using persistent Segment tree.
Yes, my transformation is similar. I figured out how to do the median + sums with treaps, but since I was unable to code treaps, I used a different simpler structure(couple of multisets) but wasn't able to debug that in time as well. Anyway, congos on 2nd place :)
Thanks for the nice problems, laoriu
What is complexity of this solution?
log2 per query?
I used non-persistent segment tree and binary search — it gives log3 per query — still squeezes in TL.
My solution is log per query.
Directly applying persistent Segment tree will yield log2 solution, then, you will need to tweak a bit. :)
Yay, I'm in top 3!
Is the intended solution for P2 generating function + Lucas theorem? I struggle for many hours to find 'purely' combinatorics solution, but could not..
Intended solution for P2 does not require using of generation functions. To cut long story short:
We are interested in number of sequences of length d + c such that a1 + a2 + ... + ad = ad + 1 + ad + 2 + ... = ad + c where 1 < = ai < = N If we apply bi = N - ai + 1 for d < i < = d + c and bi = ai for 1 < = i < = d, then there is a bijection between these sequences(so the overall number of both is equal) and we can count number of sequences bi. It turns that sum of bi equals c * (N + 1). So the problem is reduced to counting the number of sequences of length d + c, 1 < = bi < = N and sum of all elements is (N + 1) * c, which can be solved by pure combinatorics :)
I liked the problems, thank you, laoriu!
I also liked the problems, as far as the time I had to compete went.