I_love_Tanya_Romanova's blog

Invitation to March Clash 2016

By I_love_Tanya_Romanova, 9 years ago, In English

Hello everyone!

I want to invite you to participate in March Clash at HackerEarth. Contest is scheduled on March, 26. Contest duration is 24 hours, so there should be some comfortable time for every timezone :)

There will be six tasks in a problemset. Five 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.

PrinceOfPersia is author of this problemset. You may check some of his previous contests to ensure that he's always providing contestants with interesting tasks :)

I was working on this contest as a tester, and I enjoyed solving given problems a lot :) I hope that several tasks will be not too hard for beginners (don't give up and show your best with partial scoring — even very naive solution may give you some decent points; and 24 hours should be enough for you to read all problems and find some tasks which you can solve) while some tasks are challenging enough to make this contest interesting for more experienced contestants. Even if you think that classic part of problemset is easy — go on, try to beat other contestants on approximate problem :) shef_2318 worked on this contest as translator — you will be provided with problem statements in English and Russian. Also I want to thank belowthebelt for handling all technical aspects of contest preparation.

As usual, here is one more reason for you to participate in this contest:

Top5 of leaderboard will also receive some nice prizes:

  1. $100 Amazon gift card + HackerEarth T-shirt
  2. $80 Amazon gift card + HackerEarth T-shirt
  3. $50 Amazon gift card + HackerEarth T-shirt
  4. HackerEarth T-shirt
  5. HackerEarth T-shirt

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) Carsten Eilks

2) ffao

3) LayCurse

4) pavel.savchenkov

5) mugurelionut

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

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

Comments Comments (20)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

One hour to go for the contest. Good luck. :)

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

Did you consider to include sample explanations? That would help to make P4 more tolerable.

In the approximate problem, I think HackerEarth could have saved some considerable server spamming on my part if the generation method for the test cases was disclosed.

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

    I agree. Please don't use approximate problems where the test case generation method is not disclosed. It makes it almost impossible to test our solutions locally. This problem in particular had a large space of inputs and we were supposed to simply guess how the test cases were generated from such a large pool of possibilities? In particular, some approaches which worked really well on my local test cases made almost no difference or scored worse on the official test cases. In some of the recent Hackerearth contests this issue did not show up anymore, so I thought it was finally solved, but now it's back again. I guess it all depends on the experience of the problem setter, but I think the tester should also push for disclosing the test case generation method.

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

Can anyone explain the solution to P2 (The Great KL)?

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

    Sqrt decomposition.

    • For big groups  > sqrt(N).

    Use standard algorithm (2 DFSs) for finding perimeter of a tree in O(N).

    • For small groups  < sqrt(N)

    Choose a root, compute levels and ladders, Then check the distance of each pair in so the total complexity would be , where ni is the size of this group. (You can also use Tarjan LCA to avoid extra log)

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

      Ah nice, I thought it was going to be some complicated algorithm. So the solution runs in .

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

        In fact when we use the threshold for big/small to be it is which is better. But still when we use Tarjan for LCA it is plain .

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

      Not necessary. Consider this: We have a tree and some vertices are red and others are blue. We know the two endpoints of a longest path between any two red vertices. We paint a blue vertex with red color and we want to update this longest path.

      Lemma: One of pathes between these three vertices (endpoints of previous longest path and new vertex) is a longest path now.

      Converting the original problem to this trick is easy.

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

    NlogN solution.
    For each color keep track of the 2 farthest nodes and whenever u find a node whose distance to one of the 2 farthest nodes of that color is more than the distance between those 2 nodes , update the farthest pair of nodes for that color.
    Code

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

    I solved it with centroid decomposition.

    There are two cases:

    1. If the diameter pass through the centroid, then we only need the deepest node of every color in each of the branchs

    2. Otherwise, calculate recursively for each of the subtrees that are hanging on the centroid

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

Can anyone explain the solution of 3. problem?

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

    Suppose that we fix some subset of f's, say fs1, fs2, ..., fsk, and we want to choose some permutation p such that all a[i] + p[i] belongs to {s1, s2, ..., sk}.

    In other words p[i] can be equal j iff .

    It is a matching problem, between the domain of p and its counterdomain. Say D = {0, 1, ..., n - 1} and C = {0, 1, ..., n - 1}, and the edge between i and j exists iff p[i] can be equal to j.

    Now let us go back to the original problem. We sort f, say fs1 ≤ fs2 ≤ ... and for k = 1, 2, ... we check if we can find a permutation p for the subset {fs1, fs2, ..., fsk}. If so then the answer to the original problem is fsk.

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

    Binary Search on answer
    We want to check an answer <= 'X' is possible or not.
    Lets make a bipartite graphs with 'N' nodes from [0 , n — 1] on each side.
    Now the weight of edge from i on left side to j on right side will be f[i + a[j]]. if this weight is less than 'X' then add this edge to list of edges.
    Now find maximum bipartite matching.
    If matching == 'N' then return true else return false.
    Code

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

Solution to P4 (the great cyrus) ?

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

    Consider that we had to remove edges instead of Nodes. In that case it is a standard problem of finding the min-cut which is equal to the Max-Flow.
    Now we need to remove nodes instead of edges , so we keep 2 copies of each node say V1 and V2. Now for every edge (U -> V) in input , add edges in our graph from U2 to V1 and since its undirected , edge from V2 to U1 as well , give it weight infinity. And then for all nodes from 1 to N , add an edge from V1 to V2 with weight = the cost of removing that node. And then just find the maxflow from A1 to B2. Code

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

      Dude, slow down. The main idea was inside the min-cut part. What should be the cost to remove an edge?

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

        I used ai * X + bi where X is a big number. However I got only 91.2 points :(

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

How I could know my approximation problem results in upsolving? Found bug five minutes after the end of the contest, and want to know how much it cost for me.

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

    +1. It seems that once the contest ends, the scores for the approximation problem are not shown anymore (neither for old submissions, nor for new ones). You only get if the solution was Accepted on each test case or not, but not the score which measures the quality of the solution on each test case (which is the most important thing).

    @organizers: Can you please fix this issue with the approximation problem? It's really annoying (both for upsolving and for looking at the best submissions of the other competitors).

    → Reply