I_love_Tanya_Romanova's blog

By I_love_Tanya_Romanova, 4 years ago, In English,

Hello everyone!

I want to invite you to participate in April Clash at HackerEarth. Contest is scheduled on this Saturday. It lasts for 12 hours, so almost everyone can find some time at least to try it :)

There will be five tasks in a problemset. Four 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. Check January Lunchtime 2015 or problem Little Party from April Challenge 2015 if you want to try some of his tasks as part of preparation for upcoming contest :)

Once again, I was working on this contest as a tester. Time runs fast when you are preparing for ACM ICPC World Finals; it feels like I announced March Clash just few days ago, and now it is time for April Clash already. I would like to say that I find this problemset interesting, I hope that some problems will be not too hard for beginners (don't give up and show your best with partial scoring) and some other tasks are challenging enough to attract more experienced contestants. It was nice to work with shef_2318 on preparing problemset, we discussed a lot of problems while preparing a contest — both related to it and not related at all :) Also I want to thank to chandan111 for technical help and doing his best on fixing all issues and improving HackerEarth platform.

For additional motivation, I have to remind you that top 3 winners will receive HackerEarth T-shirt. (I already got mine for one of previous contests :) )

Good luck to everybody — I hope to see you at the scoreboard :)

(Update)

The contest has ended! Thanks to everyone for participating:)

Congratulations to winners:

1) mugurelionut

2) azukun

3) I_love_Hoang_Yen

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

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Once again, thanks to everyone for participating :)

Congratulations to mugurelionut for winning HackerEarth Clash 2nd time in a row!

Solutions for algorithmic tasks by author and tester have been added to a system and should be visible already; brief editorials have been also added.

Feel free to ask any questions and discuss a contest.

I would be glad to read your ideas for approximate problem — while preparing this contest, we had doubts that given task may turn out to be too hard for partial solving, even if simplest naive solution takes ~15-20 minutes to write (and we even changed constraints to make knights distribution sparse enough to let it pass without any problems); looking at standings, it seems that we were right, and it is better to look for some easier task next time.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    What would be simplest naive solution?

    I tried swapping knights one by one, using simple bfs to find paths between 2 knights. It passed most tests except one. (Then my laptop battery was running out, I was panic and submitted dozens of times without passing :D)

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Well, this was expected to be simplest naive solution :) Move one knight in some direction, find path from second knight to original position of first knight, find path from current position of first knight to old position of second knight.

      This solution is expected to fit into TL without big problems. Something like this one works in ~3 seconds.

      And i guess best we can expect in 12h contest is some modifications/otimizations of given solution. All of them sound natural and obvious, but you are limited by relatively high constraints and 4 seconds of time. One can write greedy instead of pure bfs, if there are some problems with TL (do moves in a greedy way until you will be relatively close to tartet place, and only after that run bfs on small part of a board); easy heuristic for improving your score is matching knights to minimize total distance instead of swapping some random pairs. One can't simply write mincost matching or KM-algorithm here, because of high constraints. Using smart distance measure (like actual length of path in moves, not just some manhattan or euclidean distance) will give you better results, but in this case it is harder to avoid those BFS (and it will take a huge chunk of given time). One of the most naive (but fast&easy to code) matching heuristics is used in code which I shared, but it already improves score a lot:)

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Hi! That was basically my approach as well. Unfortunately it tle'd and I ended up 6-th place. Now, while upsolving, I've changed one line in my bfs and got ac.. but don't really understand what the difference is (line 57):

        tle vs ac

        dist[r+dx[i]][c+dy[i]]>dist[r][c]+1 vs dist[r+dx[i]][c+dy[i]]==INF

        Any idea?

        Thanks! (and thanks for the nice contest as well) :)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      That was really sad to watch you desperately trying to pass this test. In this test N = 100, M = 666. Your solution placed correctly 665 pairs. So close...

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    For me the biggest challenge with the approximation problem was to get my solution Accepted on all the tests :) First of all, I should say that I think the constraints for the placement of the knights were not satisfied. The statement says that white knights are at positions (i,j) with j <= N/2 and black knights at positions (i,j) with j>N/2. I initially had a solution which tried to slightly take advantage of this, but kept failing. I added some asserts and noticed that the coordinates didn't match the condition from the problem statement. After that I switched to considering that the knights could be placed anywhere on the board (maybe even mixed among themselves) and I was able to get my first Accepted solution.

    Now, about the idea: I repeatedly chose two knights (a white one and a black one) and swapped them.

    I will discuss first about the swapping strategy. I ran a BFS from the white knight and allowed it to pass only through empty cells or cells with other white knights (passing through a cell with another white knight meant that, actually, the other knight would continue the journey towards the destination). I also made sure that the path contained at least one empty cell (to be able to make some moves — this may not be very important except in some very special cases). Then I chose a neighbor of the black knight with the lowest BFS distance and made moves until a white knight reached that neighbor. Note that this means that now the original position of the white knight is empty. I then ran BFS from the black knight and moved it along the shortest path to the original position of the white knight (allowing it to pass through empty cells or cells occupied by other black knights). Finally, I finalized the moves of the white knights — I moved one white knight to the initial position of the black knight (now empty) and all the other knights whose movements were "stuck" because this white knight didn't go all the way in the first pass. Using a full BFS lead to TLE on 6-7 test cases, so I used a heuristic. Whenever the distance of a cell was "too far" from the target, I wouldn't add that cell to the BFS queue. I defined "too far" if the number of moves to the cell + the Manhattan distance from the cell to the target was larger than the Manhattan distance from the source to the target plus some slack. This made things sufficiently fast to pass all tests.

    Regarding the strategy for picking a pair of white and black knights to swap, I actually tried several, as long as time permitted. The first one simply iterated through the matrix in row-major order and picked the first white and the first black knights (with an extra condition that they shouldn't be "very close", since I was getting WA on a test case without this). If time permitted, I tried other strategies — iterating in order of decreasing rows — increasing columns, decreasing rows — increasing columns, picking pairs of knights randomly, etc.

    My score during the contest was 51150, but there, in the swapping strategy, when moving the white knight towards the black knight I picked some random neighbor of the black knight instead of the one with the shortest BFS distance. I was planning to change this at some point, but in the end I forgot about it :) I remembered about it some time after the contest, made the change to pick the neighbor with the smallest BFS distance and resubmitted for practice — the new score was 50298, which is about 1.6% better than my winning score during the contest. I'm glad this silly oversight didn't cost me the victory, since the runner-up was pretty close.

    I'm certain much smarter approached could have been tried at this problem — at the very least some min cost — perfect matching algorithm could have been used for pairing white and black knights for swapping. If min-cost perfect matching were too slow, then perhaps something close to it but faster could have been used. I would have liked to try something like this, but didn't have enough time. I was visiting some relatives during the first 6 hours of the contest and then, somewhere between the 9h and 10h mark I received a visit myself. So I didn't have too much time to try very smart solutions for pairing knights. So I chose a greedy-based pairing. Nevertheless, I think that what was important for this problem was to completely separate the pairing strategy from the swapping strategy. This way, after getting an initial solution accepted, I could update them independently (e.g. like trying multiple pairing strategies within the time limit).

    Finally, I would like to mention again that the reason for which I participate in these Hackerearth monthly "clashes" is the fact that they have an approximation problem — I really like challenge/approximation problems :) This month's problem was more difficult even to get Accepted than last month, but I still enjoyed it quite a lot (even if it was a bit stressful, with my first Accepted solution being, if I remember well, less than 1h before the end of the contest).

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

      After reading your comment I've immediately checked the test generator. And you are right: in tests the first coordinate is equal or less than N/2 for white knights and the second is greater than N/2 for black, but not the second coordinate. I'm deeply sorry for this mistake in the problem statement. I really hope it won't happen in the future.

      Your solution and logic is very similar to what we had expected. It's a pity that you didn't have enough time to experiment and to try different approaches, it seems that these results could have been noticeably improved.

      Anyway congratulations on the second victory in a row — it wasn't easy due to different circumstances, but you've managed to do it. And I apologize again for this problem.

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

    I had less than an hour to spend on approximate problem and seeing that there is just one passing submission and few people trying hard to get any score was intimidating. So my only goal was to code a passing solution. Approach was to move all black knights one turn in random direction, then for each white knight check if there are reachable initial black knight positions and move to the nearest one using BFS, then do the same for black knights, if some knights weren't in correct positions after that, repeat BFS for them. Tests were gracious enough so that my solution always worked, 7.5s out of 8s time limit worst case though, so I consider myself lucky :)

    If I recall correctly this was the first time when approximate problem used non-linear scoring function, allowing all tests have more or less same weight in the total score, so kudos for that and it always should be done like this.

    All in all, it was a great contest with diverse and fun problem set (Frames is my favourite). Thanks to everyone involved.

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

      I also liked Frames best :) (out of the standard algorithmic problems)

      And I also liked the scoring for the approximation problem, which allowed each test case to have more or less equal weight — this is very good. But I have a question to the author of the approximation problem: what was the exact scoring function used ? :)

      I didn't fully understand what the scoring function was, just that fewer moves are better :)

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

        I assumed that number of moves depends on N and M approximately as linear function and it turned out to be true. So the scoring function was something like: score = moves / N / M * const. Initially I planned to make it quadratic(to increase the difference between the scores), but it led to some problems.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Next time we'll try to mention details of scoring function in a problem statement, to make it clear :)

        We actually tried to make test cases with relatively equal cost — as you pointed out after March Clash, with unbalanced scoring like simply total number of moves, contestants will focus on solving big cases only. Nice to see that it worked well this time.

        Also it seems that for such pretty complicated tasks as this one turned out to be — partial scoring will be a good idea. By partial scoring here I mean giving 0 points for failed cases, instead of overall WA; maybe with some additional penalties, so solving 19/20 will not give you 95% of full score, but I don't like sad stories 0 points for 19/20 and 665/666 on last one, when this 19/20 performance requires writing more code than any of 4 other tasks.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I have made wrong submission on problem A, and after that I recieved the following e-mail:

Does anyone really thinks, that such message motivates?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks a lot for the feedback. We will disable these emails when the contest is running.

    Thanks again!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can i find the editorial ?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can admins confirm that I'll be asked for address? Since I won T-shirt before, I'm afraid that my old address (which is already changed) will be used.