Rubanenko's blog

December Clash

By Rubanenko, 9 years ago, translation, In English

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 ;)

Rubanenko

Reminder!!!

UPD

As usually, top three contestants will receive HackerEarth T-shirts!

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

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

Your HackerEarth link is incorrect

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

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.

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

    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.

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

      It looks like the contest did use time penalty as a tiebreaker... HackerEarth should really stop doing that.

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

        Who's effected?

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

          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.

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

            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.

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

"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: 

CHANGE temp TO pass
CHANGE pass TO "qwer" 
SUBMIT pass TO hackerearth 
CHANGE pass TO temp

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

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

During contest time, are the submissions judged with pretest only, or full test?

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

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...)

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

    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.

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

      I think you mean HackerEarth. And yeah, Xellos is pedantic, and so, it is fun to read his comments :D

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

      It should be optional but compulsory. That's just an example for bad UX.

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

        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.

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

      > 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.

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

        In case you are still unable to view the problems I would suggest you some kind of special olympics.

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

          "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.

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

        Why don't you just enter random number? :p

        Anyways, CGPA = your average score of courses in high school / university.

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

          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?

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

            Hi Xellos,

            This field has been removed for this contest and for all future contest.

            Thanks for your feedback.

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

    I entered 0 there, now i am afraid that it decreased my chances for getting a work very much:D

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

A suggestion for scoring of problem 5:

First, I'll explain what's wrong with the current situtation:

  • As you can see, all the scores are too close to each other. And even some stupid greedy get you to > 80.
  • The subtasks in other problems have at least 10 point. So, in order to have some meaningful advantage from P5, I now need to optimize my solution to at least 95, which I have no idea is doable for me or not.

So, I would suggest a different scoring for future contests:

  • The scoring in statement should only be used to compare different solutions. It should not have any affect on the final scoring (the scores on Hall of Fame).
  • Scoring on Hall of Fame should be something like: 1st got 100, 2nd got 90, 3rd got 80... Then from 10th onwards, only get 10.
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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!

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

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\

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

    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.

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

      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

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

      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.

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

        My solution is log per query.

        Directly applying persistent Segment tree will yield log2 solution, then, you will need to tweak a bit. :)

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

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..

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

    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 :)

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

I liked the problems, thank you, laoriu!

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

I also liked the problems, as far as the time I had to compete went.

→ Reply