PROBLEM LINK:
Author: Snigdha Chandan
Tester: Hiroto Sekido
Editorialist: Kevin Atienza
DIFFICULTY:
CHALLENGE
[under construction]
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s Solution to be posted Soon.
Tester
Ok, I’ll be the first to write something here)
What was your approaches? My first goal was to make solution at least pass, so I just bfs-ed a tree while trying to pick valid places for every vertex (by checking all possible cells till i’ll find valid placement). It gives something like 0.000-0.002 on pretests, but at least it creates a valid configuration) Later I improved this solution by forbidding cells which are very close to already used, and by trying to avoid evil cells as much as possible. It gives improvement to something like 0.01-0.015) And one can also try some local optimizations to make it run better.
I didn’t spend much time on this problem (it was obvious that most of other contestants are too lazy to write it at all, so there were no need to create some good solution to reach top10), and my only good idea was to focus on small graphs, because it seems to be easier to get a lot of points on them. So for large graphs I was using my naive solver, and for smaller ones (with n<=95) I tried to generate random valid configuration few thousand times by just using random edges:) Then picked best one, and tried to improve it by few thousand iterations of some local optimizations. It gives ~0.1 on pretests, and my final score is 0.175 - 7th out of 14 contestants.
1 Like
Here’s my solution for challenge problem(125329.95pts) .
http://www.codechef.com/viewsolution/6526530
First, I built a simple BFS-tree to make my solution pass (namespace BuildTree). Here, I divided the board into similar squares so that the points will be distributed almost uniformly. Then I randomly generated the position several times in order to avoid evil coordinates as much as possible.
Next, I appended some functions to improve four parameters X, Y, Z and Q (namespace Improve). For every pair of intersecting segments, I try to swap the positions of one point of first segment and one point of second segment (ImproveZ). For every pair of points that affects X or Y, I move the points along the line which passes through these two points farther or closer each other (ImproveX, ImproveY). For points located in evil coordinates, I move them to better coordinate nearby this, if possible (ImproveQ).
Finally, as lebron has just mentioned, I used one more local optimization algorithm: I thought that out of given four parameters X, Y, Z, Q, the key parameter was Y (others reached almost optimal). So I tried to get maximum Y in my solution. I used very simple algorithm to achieve this goal. I modeled this problem as following:
Every unconnected pair of points repels each other, and edges between points have elastic force to fit its length to given constraints. I simulated the movement of every point which receives the force mentioned above. I calculated every point’s receiving force and then slightly moved all points to its direction. I repeated this step as many times as possible (You can see the implementation of this algorithm in namespace Simulate). As I thought, this algorithm worked well enough (improved approximately 20000pts in my solution).
I often participate in Long Challenge Contest especially interested in the challenge problem. I think that the most distinguished trait of this contest is just challenging.
Only 14 of all contestants were accepted in challenge problem of March15 – I hope more of participants make exciting competitions in the future.
The main point of solving challenge problem is a new idea and improving that. A lot of submissions for adjusting parameters are not a determinant.
For this, I think that the number of submissions can be limited to less value.
I wish that all of us actively take part in discussions to make Long Challenge more attractive.
6 Likes
@kutengine: I also think that solving the challenge problem should not be about optimizing parameters, but strategy. A lower limit for the total number of submissions would be very good. And for me the challenge problem is also the most exciting part of Codechef long contests 
2 Likes
I also used force-driven layout on my local test files, in Python (like grandalf does), but unfortunately it was too slow to pass the time limit (with more than 80 nodes). I didn’t have time to implement it in C, though. Maybe it could have passed then.
2 Likes
@kutengine and @mugurelionut: What should be the ideal limit on number of submissions on challenge problem? Please suggest !!
2 Likes
@dpraveen: I think that reducing the number of submissions from unlimited to 500 in Oct. 2013 was a good step forward. In my opinion reducing the number of submissions even further, to 250, for instance, would be a very good next step. It’s not easy to say what would be the best limit for the number of submissions, but half of what it is now (i.e. 500/2=250) would be pretty good, in my opinion.
1 Like
@dpraveen: I think that mugurelionut’s opinion is very good. Limiting the number of submissions even to 100 doesn’t affect solving problems(both general and challenge), in my opinion.
2 Likes