### I_love_Tanya_Romanova's blog

By I_love_Tanya_Romanova, 5 years ago, ,

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:

2) azukun

• +50

•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +8 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:)
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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 acdist[r+dx[i]][c+dy[i]]>dist[r][c]+1 vs dist[r+dx[i]][c+dy[i]]==INFAny idea?Thanks! (and thanks for the nice contest as well) :)
•  » » » 5 years ago, # ^ |   +17 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...