I_love_Tanya_Romanova's blog

Invitation to HackerEarth MayCircuits Contest
By I_love_Tanya_Romanova, 9 years ago, In English

Hello everyone!

I would like to invite you to participate in another HackerEarth contest. This time it is HackerEarth May Circuits. It's a long contest that will start on May, 21, 21:00 IST (check your timezone). Contest will run for 8 days.

The problemset consists of 7 traditional algorithmic tasks and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Check contest page for more details about in-contest schedule and rules.

I'm a tester of a problemset you'll have to work on — thanks to xennygrimmato, pkacprzak, himanshujaju, shef_2318 and Sumeet.Varma for preparing these tasks.

The contest will be rated. Exact format of a contest is still under development, so expect to see a lot of changes in future — but this time rules are same as in previous edition (here is an announcement).

Tasks should not be very hard for top-level contestants, and I expect them to get full score on classic part of a problemset. However, even if you solved everything — you'll still have to do your best on approximate problem :)

As usually, there will be some nice prizes for those who'll reach top spots, here are prizes for top5 (in case you haven't open contest page) :

  1. $100 Amazon gift card + HE t-shirt.
  2. $75 Amazon gift card + HE t-shirt.
  3. $50 Amazon gift card + HE t-shirt.
  4. HE t-shirt.
  5. HE t-shirt.

Upd. Contest has ended :) Thanks to everyone for participating :) Congratulations to winners:

1) Carsten Eilks

2) simonlindholm

3) riadwaw

4) uwi

5) shdut

All solutions are available, also for all classic problems editorials and solutions by setter and tester have been published.

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

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

Could you (or organizers) please highlight these changes?

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

    I only told you not to be surprised if there will be any changes, I didn't say that there are actually some changes ;)

    Jokes apart, on more "official" note, this month rules are going to be same as last month, all those possible changes/improvements are still in discuss. I'll update that part of announcement in case it is so misleading.

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

150 minutes to start of contest. GL & HF. :)

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

From instructions page:

There are 2 Approximate, 6 Algorithm problems in this challenge.

From schedule (main contest page):

Day-0 : Problem-1, Problem-2, Approximate
Day-2 : Problem-3, Problem-4
Day-4 : Problem-5, Problem-6
Day-6 : Problem-7

Which is correct?

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

Reminder — last problem has been published already, but you still have almost two days to beat everybody and reach top spot :)

P.S. And that last problem even has been rejudged already, short time ago tests has been updated and some of the constraints were changed, we are sorry for any inconvenience caused.

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

How to solve " Make n00b_land Great Again! "? Can anyone please share your solution?

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

    I solved it using parallel binary search. Similar to METEORS on SPOJ. See here.

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

    You can see others solution on the leaderboard. You'll have to unlock the editorial of the problem first.

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

    Create segment tree that stores for each vertex function f = a * x + b, such that if you put x = depth of vertex it's correct answer(you need to add on segment (of vertices in dfs time in order) and to get value in one point) and, make the tree persistent and then binary search

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

For the monkey problem, can someone explain what does the constraint 'integer divisible by the number of all possible different moves' means?

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

    It means divisible by the number of directed edges in graph. (i.e number of edges multiplied by 2)

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

Nice job dividing top5 from other by number of problems

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

    Thanks to pkacprzak for preparing that problem :)

    Would you like to describe ideas which you used in approximate problem?

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

      Well,

      I used the fact that usually it's possible to set 4 spheres to touch each other(except for the case when one in small)

      First I put 3 spheres as a triangle and maintain list of all such triangles, add add others spheres one by one(ordered descending either by radius if mine is small or by cost otherwise), trying to add it to some triangle witch was added most early. If it's not possible to place this 4 touching each other or there's some intersection — ignore and try other triangle.

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

Contest has ended, thanks to everyone for participation!

I'll post all materials a bit later, sorry for delay. Currently you have several editorials and some of codes by setter and/or tester available, plus codes of all contestants.

I feel sorry for problem "Ways of Seeing" which turned out to be the same as one of the problems from GCJ 2015 Round 2. We discovered it only when problem has been published — setter didn't participate in that contest, and I didn't solve that problem then, and didn't remember it when we were discussing ideas for a contest.

Also problem "Make n00b_land Great Again!" looks quite similar to a problem from recent May World CodeSprint. When that CodeSprint occured, we already had this problem added to a contest, and we decided to not substitute it in remaining 1.5 days, as it was still significantly different from HackerRank problem, plus for both problems there are several unique alternative solutions.

A few lines about solutions in case you are curious, as detailed editorials aren't published yet:

Make n00b_land Great Again! — one of possible solutions is doing parallel binary search and using a pair of segment trees/Fenwick trees over dfs traversal of a tree to store information and make updates.

Ways of Seeing — mincut between boxes marked with 0 and boxes marked with 1, can be found using maxflow.

City Rebuild — sort edges by weight, merge components with adding a new vertex in exactly this order.

Monkey and Ball Game — edge is good if and only if it is a bridge in our graph.

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

    I did not see the min cut solution for 'Ways of Seeing' and know very little about it. I wrote a simple solution and it worked.

    I grouped all the paintings that share at least one zero box. Counted the minimum of interesting paintings if I assign -1 or 1 to the whole group. Added the value to the answer. Also the paintings that already have -1 and 1 are added to the answer.

    I do not have complete proof of why the solution works. Now I am curious whether it worked because it is correct or because of inadequate test cases. Below is my code

    http://pastebin.com/HKf6WQBd

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

      Small note: as you are sharing your code via pastebin anyway, it would be much more comfortable to have all code there, not only some chunk, which can't be copy-pasted and compiled/tested/stress-tested etc. :)

      Your code works because tests turn out to be really weak. Now I feel ashamed, for second time in a row because of the same task — I've tested some other less trivial things while completely missing the fact that in most of networks mincut between two vertices will be simply cutting everything around one of the endpoints (that should be intuitively natural — when we go further from vertex, our set of paths becomes "wider") — and that's basically what your solution does. Luckily it doesn't affect prizes distribution in any way — winners submitted intended correct solution with flow.

      A test for you:

      1
5 4
1 0 0 -1
1 1 0 0 0
1 1 1 0 0
0 0 1 1 1
0 0 0 1 1

      And thank you for teaching me a good lesson.

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

        Thanks for checking this out and the explanation. I think this will be a good starting point for me to start learning the network flow.

        Please don't sweat it too hard. People who see the similarities between the GCJ problem and your problem are most likely the people who knows how to solve it in the first place.

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

    I can barely see similarities between 'Make n00b_land Great Again!' and problems from the May CodeSprint, but there is a problem from two years ago with exactly same update queries. The values to be reported and solutions are very different though, so it's fine IMO.

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

    For ways of seeing problem, I was referring to the C++ code in the editorial. I am curious to know why are the edges from source/sink to boxes are of size 1000 and edges from boxes to paintings are of size 100?

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

For the problem City Rebuild some contestants (like riadwaw) submitted solutions which seems O(N). I too tried a solution using a bfs which fails on certain cases(every fifth case to be precise, would love to here from I_love_Tanya_Romanova if he intended those cases to fail certain solutions :)). I would be grateful if someone could explain the correct procedure to solve the question in O(N).Thanks a lot.

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

    My solution (it is probably similar to riadwaw's one :) ):

    For each vertex v if it's not already a list, replace it with additional vertex u and add free (with cost 1) edge between u and v (so now it's now a list).

    Each path now goes through original edges + up to 2 1-edges that doesn't change maximum.

    I'm wondering why they've chosen such constraints (esp 9e3, not even 1e4) considering their solution is nlogn

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

      We decided to chose such low constraints, because we had to prepare a custom checker for this problem and we didn't want to have it complicated — it runs in O(n^2) time now. Moreover, we wanted the problem to be easier than Monkey and ball game problem, so we decided that lower constraints are fine. In addition, figuring out the intended solution, and implementing it even in O(nlogn) or very fast O(n^2) is not trivial, so this is the main goal in the problem.

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

    If you are curious how test cases were generated, then in tests:

    • 1, 6, 11, ... the tree is a spanning tree of a single cycle
    • 2, 7, 12, ... the tree is a spanning tree of a lollipop graph
    • 3, 8, 13, ... the tree is a spanning tree of a barbell graph
    • 4, 9, 14, ... the tree is a spanning tree of a start graph
    • 5, 10, 15, ... the tree is a spanning tree of a randomly generated graph using this function

    Speaking of the most efficient method to solve this problem, the idea is exactly the same as the procedure to create a full branching tree from any tree described in this section 2 of this paper and also in this PDF presentation

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

Hi,

I just noticed that I took part in that contest, whilst I didn't. Who should I report it to?

→ Reply