Errichto's blog

January Clash '16 on HackerEarth
By Errichto, 9 years ago, In English

Good morning everybody.

January Clash '16 will start tomorrow (check your time zone). Duration is 24 hours and submitting time doesn't matter so you can join whenever you want.

Note the unusual starting time (compared to previous Clashes). We moved it a bit because of colliding with Facebook Hacker Cup.

You will be given 5 algorithmic problems and one approximate (optimization) one. All problems will have partial scoring (points for each test passed) and easier subtasks. Thus, everybody should find something for themselves. Getting full points on all 5 problems should be hard for everyone. Remember to solve as many subtasks as possible if you want to get to the top.

Problems were prepared by Lewin. He is an author of numerous contests, including many SRM's on TopCoder (link) so you don't have to worry about the quality of the problem set. I am a tester and an editorialist.

Problems are interesting and so do smaller subtasks. Don't expect them to be very easy though — some of them are far from being straightforward. Anyway, solve them first if you don't see a 100-points-solution.

There are prizes — t-shirts and Amazon gift cards. And the eternal glory of course.

Enjoy a contest.

WINNERS

Congratulations:

  1. Egor
  2. Kostroma
  3. HellKitsune
  4. anta
  5. akashdeep
  6. ishraq

I want to congratulate anta for solving the hardest problem and Egor for almost solving it — but well, he won anyway. Kostroma had the best score in an approximate problem and HellKitsune was very close to that.

What was your approach to an approximate problem?

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

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

GL & HF

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

Bump. This is starting in about half an hour.

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

4 hours left and only one person has solved all 5 standard problems, though he is not on the lead. How will it end?

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

Seems like I'm missing well known technic to compute function over all permutations in Retract. Can someone enlighten me?

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

    You have a sum that's like (-1)^(sign of permutation) * a_(1,p_1) * .. * a_(n,p_n) over all permutations p. You can compute this using a determinant.

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

      Yes, I am stupid :) Thanks

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

      That problem was in October Clash :D

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

      @Egor, I didn't realize it too as a tester. Lewin had to tell me that I'm looking at a formula for determinant.

      @Xellos, exactly the same problem?

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

        Not exactly, but Lewin's comment summarises the solution of it.

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

By the way, it would be nice if Java would be upgraded to Java 8

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

Editorials are ready but we must wait a bit for a system to refresh. By the way, it was very interesting to watch the leaderboard in the final hours. EDIT — you can see editorials.

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

I am wondering how this O(n) code got 100 points for problem remains. It would easily TLE for a case where x = 1,y = 10^9 and n = 10^9 .

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

what is wrong with my solution from "Rebuild" (2nd problem) :- solution

→ Reply