I_love_Tanya_Romanova's blog

Invitation to February Clash 2016

By I_love_Tanya_Romanova, 9 years ago, In English

Hello everyone!

I want to invite you to participate in February Clash at HackerEarth. Contest is scheduled on February, 20. 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.

shef_2318 is author of this problemset. If you want to get an idea what to expect — you may check his previous contests at HackerEarth, CodeChef and HackerRank. Even if you don't need it in order to participate in Clash — I would advice you to take a look at them someday, because there are quite a few really interesting problems there.

I was working on this contest as a tester. I believe it is going to be an interesting one, as usual :) I hope that several problems 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 also worked on this contest as translator — you will be provided with problem statements in English and Russian. Also I want to thank belowthebelt for providing technical help and doing his best on fixing all issues and improving HackerEarth platform.

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, congratulations to winners:

1) eatmore

2) mugurelionut

3) Carsten Eilks

4) RomaWhite

5) Egor

All editorials have been published.

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

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

The contest has started. Good luck, everyone. 23 more hours to go. :)

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

The judging system, at least on the challenge problem, is broken. I've submitted dozens of times and only two of those submits have been evaluated.

UPD: Downvotes won't fix it.

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

    Bump; the problem persists and I'm not the only one affected by it (as it seems from the other comments).

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

Just another bugreport: sometimes C++ submissions are compiled using old g++, causing compliation errors.

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

    Hey Aleksandr,

    We need few details about the issue you are facing. Which version of g++ did you use to compile your program locally? Can u PM me your username? We will resolve the issues and update the scores.

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

      You may check my submissions too (I've send the same code several times and sometimes was getting CE) See for example submission id 3438775. It's in c++98 mode for some reason

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

      I was also getting random Memory limit exceedings, See for example 3436852 — resubmission got OK

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

How to solve this problem in February Clash : https://www.hackerearth.com/february-clash-16/algorithm/sequences-everywhere/ Can anyone help me out with this problem ? This is my solution : https://www.hackerearth.com/february-clash-16/algorithm/sequences-everywhere/submission/3440968/

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

    Editorial for this problem has been published already, plus you may check solutions by other contestants.

    Brief idea of solution — you can count how many sequences will have second element equal to X — and value of X isn't going to be large, so you can try all of them.

    In your solution you made an assumption that length of sequence solely depends on remainder modulo 12. It is close to being correct, and it actually makes a lot of sense — if number isn't divisible by 12, it is not divisible by either 2, 3 or 4 (and you can figure out on which of them by considering remainder modulo 12). However, consider sequences for number 60: 7 2, and for number 420: 8 3 2. Both 60 and 420 are divisible by 12, but only one of them is divisible by 7, and that leads to having sequences with different lenghts (while remainder modulo 12 is same for both numbers).

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

      Thanks a lot for giving me a test case where my solution is going wrong... The contest questions are really good :D

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

Contest has ended! Thanks for everyone for participation.

It was sad to see that something goes wrong with judge; I hope it will be fixed till the next contest. Still a lot of skilled contestants showed their best :) It was interesting to watch how leader changed several times, and how standings in top5 were changing even in last 30 minutes of contest.

All solutions by contestants should be available already; for 4 problems solutions by tester and editorials are going to be added in next few minutes. For Light it up they'll be added a bit later, today in the evening.

Feel free to share your thoughts about problemset and contest in general and to suggest any improvements.

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

I don't see setters' solutions below editorials.

  • "Light it up" was an amazing problem. One of the most interesting ones I solved recently.
  • "Game of divisors" was very strange. I wrote the recursive solution with memoization and then saw the "pattern". I wasn't satisfied after getting AC but whatever. Though the proof in the editorial is nice and simple. After seeing the editorial I would call this problem "I'm not even mad, that's amazing".
  • "Sequences everywhere" — good medium problem.
  • "Just shortest distance" — very good easy problem.
  • "Square" couldn't be new and original. I've never implemented it but I encountered and thought about it. Did anybody use the randomized linear algorithm described here or here? Does it work for this problem? What about collinear points?
→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it +13 Vote: I do not like it

    My solution for "Square"

    from scipy.optimize import minimize

def f(a):
  # Returns answer if square is rotated on alpha
  # Everything is standard

start = 0
while (start <= pi):
	try:
		ans = minimize(f, [start], bounds=[(0, pi)])
		res = min(res, f(ans.x[0]))
	except:
                #wierdo, ignore
		pass
	start += 0.08

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

      I had something like this, except I found the convex hull and if it was small enough, I tried much, much smaller steps in the angle (around 10 - 7). And used C++, of course :D

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

      Did this solution pass? I tried a similar solution but could not get more than 66 points.

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

        Yep, it did

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

          That's interesting- I have an almost identical solution but still can't pass all the cases. I'll be grateful if you can help me figure out what's happening. Code

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

It was a nice problem set. After reading the (currently) posted editorials, I would say that most of my solutions are based on the same ideas (except that I actually used the bit masks approach for "Game of divisors" and it fit well within the time limit, because not all bit masks are reachable from the starting configuration — I really didn't want to think about the problem more than was needed :) ).

I read Errichto's comment about how "Light it up" was an amazing problem. For me it really wasn't. My solution is probably not the intended one, but it passes all the test cases and I'd be curious to find out cases where it might fail. So here it goes: for each of the two points on top of a building, construct a set with the lateral sides fully visible from that point (so, for the point on the left side of a building i, this set consists of the left side of building i, plus some right sides of buildings j located to the left of i, which are fully visible). Then, the question becomes: choose a minimum number of sets which cover all the 2*N lateral sides of the N buildings. Here I simply used greedy: always pick the set which covers the largest number of yet uncovered sides. My plan was, in case this greedy didn't pass all the test cases, to use techniques which I normally use for the approximation problem (e.g. randomize the order of the picked sets a bit, add some kind of score which considers more than just the number of yet uncovered sides, use multiple runs, etc.). But the simple greedy approach just worked.

For the approximation problem, the core of my solution was a greedy algorithm. I maintained for each ring the number of shifts which are still "compatible" with the current placement of rings so far. Then, when choosing the next ring to add to the solution, I would choose one from a set of candidates, which minimized the total number of new shifts it "kills". The set of candidates usually consisted of the rings with the smallest number of compatible shifts (or a random selection of them if they were too many). If they were too few, I had a mode in which I also added more candidates (in increasing order of the number of compatible shifts, up to a limit). The reason for considering rings with small number of "compatible" shifts to add at each step is that if I don't try to add them now, I might not get the chance later (i.e. they might lose even more of their compatible shifts and become fully incompatible).

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

    For "Light it up:, instead of greedy, we can compute the minimum vertex cover of a bipartite graph for the last step. For each left side of building, we only need to consider putting a light on the top left corner of that building or the top right corner of another building to the left of it (although there may be many top right corners that work, we should consider only the leftmost one because the set of left sides it covers is a superset of all the other possible candidates). And similar logic follows for the right side of buildings, with special exceptions for the leftmost and rightmost buildings.

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

      Hm... I actually thought about it (i.e. pairing a left side with the furthest right corner from which is it fully visible and pairing a right side with the furthest left corner from which it is fully visible), but it seems to me that the sets of visible sides are not supersets of each other. Let's take 4 buildings:

      • B0: [1,2], height = 10
      • B1: [3,4], height = 9
      • B2: [5,6], height = 1
      • B3: [large number, large number+1], height = 1

      The left side of B3 is visible from both the right corners of B0 and B1 (if not, just move B3 further to the right until it is fully visible from both). So B0 is the leftmost right corner from which the left side of B3 is fully visible. But the right corner of B0 doesn't see the left side of B2, while the right corner of B1 does.

      For this example the final answer might not change if you pair left corner of B3 with right corner of B0 or B1, but I'm wondering if it there are examples where it matters.

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

        Editorial has been published. That idea with picking furthest point is fine, that's a part of intended solution (described in editoral), and it is not hard to prove that it gives AC not simply because tests are weak :) Long story short: in your example you'll always have to put a light either at right corner of B0 or at left corner of B1 (because there will be no other way to illuminate B1-L), and chosing right corner of B0 is always not worse than chosing left corner of B1 — B1-L will illuminate only B0-R and B1-L, while B0 will illuminate B0-R, B1-L and maybe something else. So if you'll find B0-R as part of your greedy strategy — you are simply saying "oh, I'll have to put a light there anyway".

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

    I had so many (mostly wrong) approaches and ideas for "Light it up", it was awesome for me. And I like my greedy solution. I proved its correctness so I can write down a proof, if anybody wants.

    I choose the highest building (any of highest ones in case of ties). Let i denote its index. If the right side of i-1 is not lit then I put a light in the left top corner of i. Similarly, if the left side of i+1 is not lit then I put a light in the right top corner of i+1. Then I run recursively for [start, i-1] and [i+1, end].

    Note that maybe not all walls are lit at the end. Before printing the answer I must iterate over all 2n walls and count not-lit ones. It turns out that each of them must have a separate light. So I add the number of them to the answer. My code.

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

      My solution uses the same idea, but it guarantees that at the end all the walls are lit, so the last step isn't necessary.

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

      How to prove it?

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

    My solution of the approximation works like this: at each iteration, it takes a random rotation of a random ring not in the current solution and adds it to the current solution if at most one other ring is removed as a result. To break out of local minima, the following technique is used: if the solution is not improved for a certain number of iterations, a random ring is added to it, even if this requires to remove multiple other rings from it. Before this, a copy of the solution is made. Later, if the new solution can't be improved to become at least as good as the old one, the old solution is restored.

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

Hello Everyone, We have re-judged all the solutions and updated the leaderboard. Please check it now. Regarding c++98 compilation issue, We are on it. The next contest experience will be much smoother. :)

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

    Unrelated to the rejudge, but... why is it not possible to see the score obtained by the challenge/approximation problem submissions after the contest ended? Now I can only see the status of the submission on each test case (Accepted, TLE, etc.), but not the score it obtained on each test case, which is actually the most useful information. And there's also no global score of the submission displayed anymore (e.g. 100, 98.79, 80.76, etc.).

    I wanted to look at the submissions of the other contestants and see on which test cases they did better than my solution, but:

    1) I can't tell which one is their best submission (since no global score is displayed anymore)

    2) I can't see the score per test case (since it's not being displayed)

    Note that this is true also for my own submissions, for which I could see a global score and a score per test case during the contest (but not after it).

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

      Hmm. I will forward your suggestion. It is possible to display scores. I will discuss it with my team and add it as soon as possible to the web interface. We might have missed out on it.

      The product is evolving every day and suggestions from the community are most welcome.

      I will post an update as soon as we are done.

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

Oh, by the way, slightly off-topic, but if anyone has ideas to set up an Easy or a Clash contest, they can PM me. :)

→ Reply