-is-this-fft-'s blog

By -is-this-fft-, history, 7 months ago, In English

I wanted to create this blog because there will probably not be really much discussion of solutions in the award ceremony (currently in progress). Also people who aren't finalists themselves can't see that anyway.

I'm interested to hear approaches of the higher-scoring finalists. (We, TÜ Randomized Algorithms did not do anything interesting :D)

A bit on the negative side: this seemed to be not be a 4-hour contest at all. The problem was kinda complex, I felt that I spent all the contest swamped in implementation, not being able to implement even 1/10 of the ideas I had. Well, it's also partially our fault for coming to troll in the finals with a 2-person team :P.

Also, did anyone manage to use the visualizer?

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

7 months ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

We took 8th place, but results are really far from the best one, and I feel the same about "not a 4-hour contest."

B — 1,070,068
C — 972,941
D — 1,135,201
E — 739,855
F — 519,975
Total — 4,438,040.

Initially I had and idea to start from test E, which has very small field and a lot of arms. So the idea is that in such conditions arms should work very locally and occupy as less space as possible.

Pipeline of my solution is next: I put arms in some random positions, take them one by one, and completely fill each arm with tasks in some greedy order. And I visit points in the most naive way: going to the each one only by some shortest path, if it doesn't conflict with path of any of previous arms. And after visiting each assembly point I just retract the arm completely. Score function for greed ordering of tasks for current arm is $$$\left(estimatedLengthOfPath - \frac{score}{\alpha}\right)$$$. Running such solution hundreds of times with random $$$\alpha$$$ and initial order of positions I got final scores.

My teammate wrote a solution with some greedy but simultaneous moving of all the arms, but it gets lower scores.

7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

We are 32nd (team Eel) without any actual solution. We did B optimally as that was rather obvious and then got some minor really bad scores.

Absolutely agree with it not being a 4-hour contest, I actually came up with some decent ideas but couldn't get them to work in time. Getting even the simplest solution one can think of to work took so long. Not happy with the problem, but I guess some people still really nailed it looking at the top scores.

7 months ago, # |
  Vote: I like it +140 Vote: I do not like it

Contrary to the previous orators I very much enjoyed this year Finals. And the reason is exactly "it doesn't feel like a 4-hour contest" which really means "we don't have enough time to try all or even half of the ideas we have and fine-tune parameters". For all 5 previous HashCode contests I participated (3 Quals and 2 Finals) teams 2-20 in final scoreboard had very close solutions different only in some heuristics. And I maybe biased, but it felt like the teams above us just got more lucky and I don't think that what the scoreboard should measure. But this time it was hard to get non-zero points (and not all teams got them). You had to work faster, communicate better, make less bugs so you have more time to try more things. And scoreboard proves it — 1st place team has 1.5x more points than 10th, now it really feels like they did much better, not just got lucky. We are the only team with score in interval [5m; 6m], this is insane, right?

Here is our general approach, though I don't know many details:
1. Randomly assign arms to mounts [I feel like this is the worst part of solution, we tried to improve here in the end, but it seems that there are much more room]
2. The task manager scans time from left to right, when some arm becomes free (finishes previous task) the task manager tries to find most suitable next task.
-- 2.1. Try all the task and calculate estimate profit as score/sumLen
-- 2.2. For tasks with 20 biggest estimate calculate real time needed to finish the task and choose the best task to assign
-- 2.3. [?] I heard that we tried to cut lengthy tasks in pieces, but I don't know if it is used in final solution
3. Use BFS to find the fastest way to complete given task for given arm
-- 3.1. For every cell we maintain the last time it was used by any arm. We assume that we cannot use this cell earlier, but can use after it becomes free
-- 3.2. Each arm completely retracts after completing the task [because of the way we treat free cells it is bad to have arm laying after the task since we don't know when it will free the cells. Maybe we can add something like "I can free the cells if it is needed", but we didn't have time for this]

Rough timeline:
[0:00 — 0:02] Waiting for power outage to end [just kidding, but it wasn't fun when the lights went out 50 minutes before the start].
[0:00 — 0:20] Reading the statement, going "whaaaaa how to do like anything?"
[0:20 — 0:30] Looking at the datasets, trying to get some basic insights
[0:30 — 1:20] Um_nik is hardcoding B
[0:30 — 1:20] Merkurev and Polina are doing some visualizations
[0:30 — 1:40] KAN is writing input/output, checker, scorer
[1:20 — 1:45] We are discussing the general approach, splitting the solution in task_manager/arm_moving
[1:45 — 2:00] KAN+Merkurev are writing basic task manager
[1:45 — 2:30] Um_nik is writing basic arm moving code [I'm actually surprised to see that it took only 45 minutes, I felt like I was staring in the empty function for more than that because I couldn't understand how to do it right].
[2:30 — 2:40] somewhere around here we got our first points aside from B, still with bugs in BFS
[2:00 — 2:50] KAN continues to add some features to task manager like splitting tasks and better estimations
[3:00] Scoreboard is frozen, we just finished fixing some stupid bugs in basic solution, and we are on 3rd place o_O
[2:40 — 3:15] Um_nik is improving arm moving algorithm
[3:00 — 3:20] Merkurev is configuring the ecosystem to run solutions on all tests multiple times
[3:15 — 4:00] All of us trying to do different small improvements, most notably — improving initial arms placement

  • »
    7 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    [0:30 — 1:40] KAN is writing input/output, checker, scorer

    I am not as depressed by my performance anymore

7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Well, that was Speedforces or maybe Speedhashcode. There wasn't enough time to do anything smart. As I said in Telegram group, this was enough for 5M points:

  • Start arms in random mounts.
  • while(true): find earliest-available arm, find best task comparing by ratio score/total_distance_to_cover
  • To know which cells we can visit, for every cell remember the last turn when it was touched by anybody (same as Um_nik)
  • Always retract completely after getting to any part of a task.

I will try something better today in upsolving, you can watch the stream on https://www.twitch.tv/errichto or https://youtu.be/yI7-lOWUYrY.

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

    You're saying that this was sufficient to get 5M points. Why do you have only 3.7M, then?

  • »
    7 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    stream recap: I can't get anything better than 5.1M, this problem defeated me