ICFPC 2023: Music Concert
This year task was about placing band musicians on the stage to maximize the concert attendees score based on their music peference.
Final Results
There are no final scores yet, but we finished at 19th place in the frozen leaderboard (our final score was actually 121,325,153,271, so we won’t get higher than 18th place):
Overall Impression
Overall the contest was really good! Just a few minor observations:
- The task itself felt a bit repeatative - similar to 2 previous years, this was a static problem optimization, no VMs, programming languages or other surprises involved. I understand that it’s harder to do different style of problem than static one, but I am concerned that ICFPC now converged into this state.
- The description changes were fairly small and didn’t change the problem much. Pillars were predictable from the initial input, closeness factor addition was actually okay, and the addition of volume was a few lines change (not clear why range [0; 10] was chosen, while all the final answers would be 0 or 10)
Members
Similar to last year, we had the following members (but with an additional member from Boltzman Machine):
- Alex P.
- Dmitry P.
- Oleg G.
- Victor K.
- Vitaly A.
Languages used
- C++ (solver)
- Python (scripts)
- Javascript (UI)
Solution
We had 2 solutions, that performed pretty similar on a full subset of problems.
Border Solver
- Do a packed hexagonal grid around the border with N layers. (
N = 3for first batch and manually tuneN >= 5for the second batch where closeness matters) - Add Fake musicians to the list (they always score 0) so that total musicians match the total number of spots in layers.
- Use Hungarian algortithm to find optimal assignment of musicians to the spots
- Use greedy swapping algorithm to optimize for closeness
- Here are examples of typical arrangmenets it creates:
Stohastic Greedy Solver
- Find the position of musicians one by one using local gradient descent (no visibility into account, but don’t allow overlaps)
- There are certain rules and heuristics where next musician could be placed
- Finally run Hungarian and Swapping fine-tuning similar to previous approach
- Here are examples of typical arrangmenets it creates:
UI
We also built a convenient UI to analyze the problems:
Misc
We built a slack bot that was posting our score and position when things has changed. Here is the final run of it before the leaderboard got frozen:
Then we switched to different API to show only our score:
We also had some analytics built-in into UI to see force fields:
Some teams spent quite a few money on AWS bill:
Was cool to see different visualizations from other teams:
Collection of write ups
Here is the summary of other teams approaches:
- [1] All your sound are belong to us
- [3] is_topcoder_dead
- [4] manarimo
- [10] Frictionless Bananas
- [12] WILD BASHKORT MAGES
- [48] DNIWE
- [51] codingteam
- [69] AStormOfMinds
- [91] JKRT
Full leaderboard (frozen):
+------+------------------------------------------+----------------+
| Rank | Team | Score |
+------+------------------------------------------+----------------+
| 1 | All your sound are belong to us | 136841439993.0 |
| 2 | Unagi | 132037417965.0 |
| 3 | is_topcoder_dead | 131472977027.0 |
| 4 | manarimo | 130667797435.0 |
| 5 | Spica | 130083292906.0 |
| 6 | TBD | 129288211999.0 |
| 7 | ichyo | 128946544787.0 |
| 8 | mintokukai | 128567288553.0 |
| 9 | カフェテリアルネ | 126833067785.0 |
| 10 | Frictionless Bananas | 125945946885.0 |
| 11 | Pigimarl | 124531475872.0 |
| 12 | WILD BASHKORT MAGES | 124259024595.0 |
| 13 | tomerun | 123653805983.0 |
| 14 | siman | 122463014308.0 |
| 15 | chirijako | 122281387956.0 |
| 16 | DiamondPrincess | 121603840031.0 |
| 17 | senasur | 121583826776.0 |
| 18 | The Cat is #1!! | 121144850161.0 |
| 19 | Snakes, Monkeys, and Two Smoking Lambdas | 120362987393.0 |
| 20 | negainoido | 117795011118.0 |
| 21 | sonna*baka*na | 117273124063.0 |
| 22 | levsimonov | 116971447539.0 |
| 23 | nekokoneko | 116647469556.0 |
| 24 | CowDay | 116532714594.0 |
| 25 | pegovka | 116419749141.0 |
| 26 | 夏合宿 | 116316622646.0 |
| 27 | olegfedko | 115539186038.0 |
| 28 | ZebraInfusedHamsters | 115538071519.0 |
| 29 | ecto-sosuupoyo | 115524189964.0 |
| 30 | perpetuum_mobile | 114959691959.0 |
| 31 | fixstars | 114408198234.0 |
| 32 | theblindhen | 113848306896.0 |
| 33 | *uni* | 113662269395.0 |
| 34 | Gon The Fox in the shell | 113368023393.0 |
| 35 | Piggypack | 113351022352.0 |
| 36 | yorofuwa | 112744630030.0 |
| 37 | cashto | 112146799473.0 |
| 38 | *REDACTED* | 111899317570.0 |
| 39 | InvisibleImp | 111438784240.0 |
| 40 | Team Sampou | 109887337583.0 |
| 41 | iehn | 109405196534.0 |
| 42 | udfew | 108745540292.0 |
| 43 | tratata | 108537036617.0 |
| 44 | TyChyoPyos | 108299859097.0 |
| 45 | camel_case | 107618329559.0 |
| 46 | kretino | 104487127423.0 |
| 47 | functorfans | 100870307255.0 |
| 48 | DNIWE :: a | 99642168182.0 |
| 49 | omgicfpftw | 97813792752.0 |
| 50 | seλf recursive srs | 97640384787.0 |
| 51 | codingteam | 97433577912.0 |
| 52 | tumdum | 95490906638.0 |
| 53 | bottlekids | 93871429690.0 |
| 54 | Yurufuwa | 92276489622.0 |
| 55 | hayato | 91934500343.0 |
| 56 | xlerb | 90742175805.0 |
| 57 | sanityinc | 90432477859.0 |
| 58 | Turing Machinists | 89393999898.0 |
| 59 | jcazevedo | 88820734418.0 |
| 60 | sanma | 88539959231.0 |
| 61 | Dare Ludum | 88163042793.0 |
| 62 | killswitch | 87138011299.0 |
| 63 | Sunspear | 86015897151.0 |
| 64 | albatross | 83345413583.0 |
| 65 | koorogi | 82991029817.0 |
| 66 | poka | 82460130714.0 |
| 67 | powder | 81285319598.0 |
| 68 | YurkovAS | 78524268604.0 |
| 69 | AStormOfMinds | 75965006087.0 |
| 70 | igusarov | 74153487246.0 |
| 71 | yupiteru | 73899788408.0 |
| 72 | code-o-matic | 71715883304.0 |
| 73 | FIRQ | 71064569799.0 |
| 74 | AOKI Taichi | 68247569799.0 |
| 75 | uguu.org | 63575298140.0 |
| 76 | TeamDev | 60546756946.0 |
| 77 | Raging Mushrooms | 58773455544.0 |
| 78 | zeuxis | 58079145030.0 |
| 79 | R22b | 57326963622.0 |
| 80 | UA_paiv | 55850506349.0 |
| 81 | Thelamon | 55338485173.0 |
| 82 | LILiK | 53622016363.0 |
| 83 | Rick Zapor | 51938606381.0 |
| 84 | TSG | 51867049607.0 |
| 85 | maddenvvs | 50424815751.0 |
| 86 | taxidriver | 50404956173.0 |
| 87 | IKS | 45555895665.0 |
| 88 | Ms. Bubble's 🐶 | 44542553856.0 |
| 89 | Free Tacos! | 42966819105.0 |
| 90 | BlazinglyFastBerries | 40176962292.0 |
| 91 | JKRT | 39442480909.0 |
| 92 | Task Manager (Not Responding) | 39159797044.0 |
| 93 | nickgard | 38481998204.0 |
| 94 | cvnm | 37233675020.0 |
| 95 | Lambda Quakens | 36703229251.0 |
| 96 | papier | 33919553265.0 |
| 97 | '); CREATE TABLE fun(); -- | 32657667869.0 |
| 98 | mnuyav | 30695373362.0 |
| 99 | DalvP | 26888115605.0 |
| 100 | O Caml, My Caml | 26541787651.0 |
| 101 | Potusin | 25051465766.0 |
| 102 | Slow | 22718677458.0 |
| 103 | Travelling Types | 21280482497.0 |
| 104 | elM4gh3LocoEnCpp | 17539246689.0 |
| 105 | bir3 | 16808979449.0 |
| 106 | RGBTeam | 16608273323.0 |
| 107 | cyberecho | 16123393764.0 |
| 108 | shocr | 12823168790.0 |
| 109 | vip.delete 😅 | 10148648882.0 |
| 110 | Channable & Friends | 9514765032.0 |
| 111 | Team Meh | 8796006487.0 |
| 112 | win32asm | 8412786244.0 |
| 113 | tryitagain | 8305558011.0 |
| 114 | Respect_Oyama | 8181235395.0 |
| 115 | Imaginary Ones | 7776094212.0 |
| 116 | xyz600 | 6998280096.0 |
| 117 | xyz | 6688851642.0 |
| 118 | idkjava | 6479854143.0 |
| 119 | jakeswenson | 5700045326.0 |
| 120 | cdcnqr | 5227626725.0 |
| 121 | hiro116s | 5187276760.0 |
| 122 | kaizaburo | 4861465065.0 |
| 123 | jabber.ru | 4852968270.0 |
| 124 | a9ua1i0n | 4090916838.0 |
| 125 | balonit_bros | 3787789330.0 |
| 126 | seiyakyokai | 3745376721.0 |
| 127 | KMC | 3703694573.0 |
| 128 | zhelih | 3414223834.0 |
| 129 | tarstars | 3221595734.0 |
| 130 | ZebraInfsuedHamsters | 3148827022.0 |
| 131 | NoWar_kt | 3045938423.0 |
| 132 | Paisley Paradox | 2942256270.0 |
| 133 | nikitonsky | 2921616540.0 |
| 134 | mynameisdaniil | 2865080817.0 |
| 135 | zloyrusskiy | 2525809123.0 |
| 136 | xffox | 2340613145.0 |
| 137 | Team Junk Food | 2289632943.0 |
| 138 | prozacchiwawa | 2221089526.0 |
| 139 | Vladyslav Tokar | 2109487519.0 |
| 140 | lambdametal | 1553639214.0 |
| 141 | eval_ctx | 1504360303.0 |
| 142 | gybson_samara | 1403943105.0 |
| 143 | Dis Functional | 1373282970.0 |
| 144 | maximiliank | 1288506520.0 |
| 145 | kyoto-ni-modoritai-club | 1006741332.0 |
| 146 | Sp00kiel | 966656802.0 |
| 147 | qweeze | 845690568.0 |
| 148 | xiej | 754525054.0 |
| 149 | DaisySh | 363601828.0 |
| 150 | alex.prisadkov@gmail.com | 131984681.0 |
| 151 | hari64 | 75046964.0 |
| 152 | Bellanzio | 57964028.0 |
| 153 | null | 13394777.0 |
| 154 | el_susla | 11098680.0 |
| 155 | enbilop | 7375745.0 |
| 156 | kargo | 1593432.0 |
| 157 | ghostdunk | 1034339.0 |
| 158 | burningpony | 624291.0 |
| 159 | keles | 0.0 |
| 160 | sh_mug | 0.0 |
| 161 | LilMeyer | 0.0 |
| 162 | nhuthai08 | 0.0 |
| 163 | darnley | 0.0 |
+------+------------------------------------------+----------------+