Qualification Round has ended, but no blog on Codeforces yet. What happened to my Codeforces?
Main page: https://hashcode.withgoogle.com/
Judge system: https://hashcodejudge.withgoogle.com/
Our points: 10 / 176877 / 15824126 / 11808094 / 21465945, total score 49275052, 55th place.
How did you solve all the subtasks? I'm most interested in C and D.
Very nice score, congratulations. We managed to get 49003090.
In C, we greedily built the solution, one car at a time. For each car, we always selected the ride that we were able to start the earliest, given the car's actual position and the distance to start of the ride.
In D, we initially tried the same as for C, but we also counted the wait time. It was better when we improved all cars at the same time — that is we processed the rides in increasing order of their starting time, and we always selected the car that was able to start the journey the earliest, if any. We gave small bonus to rides that ended in X = 9999. The score on this one was the worst compared to the theoretical maximum on the input (of the three tasks), so I think we lost it there.
In E, I guess you had the optimal solution using bipartite matching. In our submission, we actually didn't have time to fix the rides for which the bonus was not achievable, and that costed us around 200000 points.
The following greedy algorithm got 49,200,122 with the same code for all subtasks:
At the beginning each car has coordinates (0,0) and last_free_time=0
At each step among all the rides and all cars we choose such a pair (car, ride) that will give positive number of points and has minimal start time, after we choose a ride, we update chosen car's position and last_free_time. We choose such a pair while we can, i.e. while there are pairs (ride, car) that give positive number of points.
Basically the idea is that we can get a lot of money if every car is idle for as little time as possible, and strangely this idea gives quiet a lot of points, but sadly tiny tweaks to the way the best pair is chosen don't give any improvements.
So we had some algorithms that generate initial schedule, which are not that relevant, and then we try random optimizations of 2 types: 1. Take a car, clear its schedule and then greedily assign new schedule to it from not completed rides 2. Take a ride that is currently not completed and try to insert it in schedules of all cars at all positions (if some rides after insertion become impossible we just delete them from schedule)
That was enough for 2nd place
Heh, it is kinda funny that on such competitions thousands of people always come up with some sophisticated ideas and in the end you read description of 2nd place algorithm and you are like "wtf were the other n-2 teams doing?" :P. Seems that https://en.wikipedia.org/wiki/KISS_principle is the key (but of course, based on a good idea, usually local search with sensible rules is the way to go).
For reference, our scores on tests are: 10 176877 15823629 12292545 21465945 Total is 49759006
@Egor First really cool solution! I'm amazed it worked so well! I was thinking along the line of just starting with a random state and trying to randomly select a car and trying to reschedule it in a greedy way, but I was afraid I might get a bunch of bad result that a greedy solution might overcome when considering only one ride at a time per car.
a question to you: I didn't really understand the second optimization that good, how did you choose at the end who to schedule the ride too? and what rides did you delete? Also, how much did the second optimization actually helped? wondering how much my original thought could have potentially archived without the second optimization step.
(and if you can post your solution, it could be awesome :D)
I find Swistakk's comment above quite funny, considering an algorithm that got the 1st place to my team.
The following short code (130 lines) would get the 3rd place:
https://ideone.com/wzBByv (feel free to use this code)
This is what we had after 2-3 hours of the contest. In a loop we greedily add a single ride for every car, always minimizing the wasted time: time from now (when a car has just finished a previous ride) to the moment when the car will start a new ride with a passenger.
The super-optimization is line 107 that came from analyzing test D (and it affects only this test):
if(when_would_finish <= T * 0.98) wasted += far[i] / 15;Without it, we would get a mediocre score. There are a few long rides that have destinations far away from any start of a ride, so a car going there must waste a lot of time going back — unless the process is almost over (time close to T), because then there will be no extra waste time. So we add some extra penalty based on the length from the destination to the closest start of some other ride. We won the contest thanks to this, basically.
Scores of the solution above and our final solution, divided by 106:
0.176877, 15.7991, 12.272, 21.4639 (total 49 711 877)
0.176877, 15.8190, 12.314, 21.4659 (total 49 776 211)
Some other thoughts: 1) Compared to standard TSP, here it's quite hard to improve an already chosen schedule, so we didn't bother with that. Even in our final solution we never reschedule a ride. 2) We computed the theoretically maximal score in every test and quickly realized that even a basic greedy solution gets close to that in tests B and E, so it was obvious we should focus on analyzing C and D. FYI, test C has uniformly random starts and destinations and all intervals [0, T], maybe allowing for some flows or similar, while test D was more special, with starts in one area and some few destinations far away from that.
Niceeee!!!! I was looking for a way to penalize the long rides, so I added a factor of the ride length to the ride "score" (well, +-). It did give me some great result overall, but still not a massive jump like yours (68th place).
I used the most simple algorithm I could think of. I was afraid of getting myself into an optimization situation where you get a final solution and look for a way to make it better, so I just left the idea.
I sorted the rides by their start time, added all the cars to a min-queue by the time they end their current ride, and then at each step added the closest ride to the driver, and added it back to the queue. If no such ride exists, I just left the car outside. When the queue was empty — it was completed :D
I positively penalized rides that I could start with a bonus — with the bonus value. if a ride could be started in step 40 and the bonus is 2, it will be stated as "can start at 38".
and then I added the negative factor of the ride length. (a bit messy, but can be found here https://github.com/GameXtra/Google-Hash-Code-2018)
Anyway, nice thinking looking for the closest ride after this drive!
Oh, and it's worth noticing that the starting bonus in tests C and D were close to 0, so it didn't matter at all. Just FYI.
Yup, but I felt like this wouldn't hurt them either, so it could become a more general solution :D
BTW, going over your code I noticed you didn't go by any timeline, and greedily just tried to enter the next ride for each car at each iteration. It got me wondering, wouldn't that archive lesser result than going by the time? (putting it in a min-queue or so on)? I was sure this was a significant part of why my solution worked, but after looking into your solution it occurred to me that I might have been wrong to think so.
I've tried priority queue at some point and it didn't improve my scores. It's important to try many things (like: in what order we do something) in optimization problems, but sometimes it's hard to understand why some way is better or worse than the other.
So I propose to start a list of finalists My team with pashka andrewzta and PavelKunyavskiy are invited and we already booked our tickets/place to live
We (Omogen Heap) won't be going this year unfortunately, mainly because it collides with the Baltic Olympiad in Informatics.
My team with mahnerak, harhrayr, Tiko is called SickTear. We placed 21st last year in the finals.