The Midnight Code Cup qualification round has ended. Thanks to all participants for giving it your best!
Final rankings are here: https://ranker.codeforces.com/ranklist/602915
Problem statements and materials are available here.
As we only accepted outputs for scoring, we’d love to learn about your solution approaches – please share in the comments!
This round would not have been possible without:
- MikeMirzayanov and the Codeforces team — thanks for your support and the new scoreboard system!
- Problem setters for this round: Aksenov239, Gassa, qwerty787788, cdkrot, MaxBuzz, pvs, Solenoid555
- Testers and support: winger, isaf27, PavelKunyavskiy, naagi, tourist, NALP, timav, Taube, noxwell, nsychev
- Our amazing sponsors: Recraft.AI, JetBrains, Neon, Pinely and our newest sponsors — Jane Street and Amazon!
- Our org comittee: Sofia Tekhazheva, Karina Tinicheva and Lidia Perovskaya
Thank you all!
Easy top1!!!
How to solve C2? Tried asking LLM, but I don't find a way to make them understand the code and teach me. Is it expected that the code should be understand by a human?
I think the contest rules you agreed to during the registration prohibit the use of AI? So it should be.
https://codeforces.me/blog/entry/140226?#comment-1259529
I believe AI is allowed in the contest as long as the AI you used is not actually backed by a human.
Ah. I remember still seeing the default CodeForces rules on registration using the provided username-password.
You can introduce your own debugging instructions into the provided code, even if you don't understand it in general. Understanding the structure (function positions and invocations) is enough for that.
This way you can retrieve the list of those brute-forced "objects" that were considered "good" by the
checkfunction. Like this: https://pastebin.com/raw/pAbR5ZVhAnd then you can do "Guessforces". The answer is: these are trees of size n, colored in two colors, such that each subtree has |whiteCount — blackCount| <= 1.
Thanks!
I also tried asking AI to help me insert the debug code, but failed that. Looks like I should do it myself after having a pretty high-level understanding of the code.
I spent a bit thinking how are ABC-strings related to the trees so you don't have to.
Consider the string a traversal of a binary tree. A is left child, B is right child, C is a return to the parent. So AC or BC or AACBCC are cycle pathes that start from the root, go through different vertices and return you to the root. That's also why there are A+B = C in terms of number of occurrences.
It's indeed that cycle path, but A stands for a white vertex, and B stands for a black vertex.
We had people being able to understand what's going on during testing, so that was intended plan for you:). I quite like darnley approach above too though.
Essentially, when I was writing the Asm code I used similar built-in debug techniques to understand why it doesn't produce the answer I expect it should.
It's understandable by a human as well, I solved C1 and C2 by reading the asm code without ever running it (because I couldn't be bothered to install java). Maybe not the fastest way to do it.
Problem A testcase 1: How is 98.736+ points possible!?
they probably abused precision limit?
Yes, that's exactly what we (grinders) did. We thought it was funny that it worked.
Solution for C1 can be found on oeis, if you try to compute answers for 1 1 1, 2 2 2, 3 3 3, 4 4 4 input data and enter it as a sequence. Oeis link
Unfortunately, I was slow enough to finish my solution 5 minutes before the end of the contest, so answers for the last 120 points were computed just after the end. This 120 points could get us trip to the Finals....
The fun part about getting partial points:
Just run the first test case
How to make it faster?
Disable Debug output, and you can compute test case 2
Sometimes output can be 0, so try it and get test case #6
If one of the input numbers is 0, and the other two are equal, you can notice that the answer is 2 in small cases. And wow! it's also 2 for test case #8
For C2, you can get 120 points by:
Turning off debug output and just running 3 smallest tests locally
B1 and B2 are simple, find a way to make the solution traverse as many wrong subsets as possible (about 2^23) before finding the optimal solution:
B1:
B2 (not the optimal but almost):
But I don't understand how to make B3 larger than 2^12, can somebody share some tips?
The knapsack problem is quite well-studied, so you may find some pointers in research papers. One particular author to note is David Pisinger, and one of his papers — with a very obvious name — lists a finite number of generators of difficult tests with small weights. Then it's up to you how to search in this space, but if you are lucky enough with the choice, even exhaustive search may bring some improvements over 2^12.
P.S.: kudos to those who can find the real name of the algorithm behind B3.
I claimed that $$$w_i = v_i$$$ and $$$w_1 = \cdots = w_{n-1}$$$, found a decent test case with $$$9$$$ rows and small $$$W$$$ using simulated annealing, then I generalized it to more rows.
Before that, I tried simulated annealing with no additional constraints but it gave bad results, then I started adding constraints which seemed reasonable.
C1: Guessforces. By using custom invocation, you can see the result of (about) $$$A+B+C \le 6$$$.
Now you'll find what the task itself is, from above testcases.
$$$A,B,C$$$ is unordered.
I found the task itself, by observing the following TCs:
You have A red ball, B blue ball, and C green ball.
How many ways can you arrange all the balls in a row such that no adjacent balls are the same color?
The answer may be large, so output mod $$$2^{32}$$$.
$$$O(N^3)$$$ with enough machine power is ok to get full score.
I simply ask Gemini to solve it, lol.
That's frustrating and surprising really. I performed testing with chatgpt, dozens of iterations and it seemed conclusive chatgpt shouldn't work. Example: link.. There was some additional hardening to make it unlikely to ever happen.
However, I was also thinking that's not end of it if people find a way to game C1 by either guessforces or chatgpt or other techniques, because having C1 solved diligently gives a huge boost to solving C2 because most things are literally the same. I think solving C1 with chatgpt actually hurted people's ability to solve C2.
MidnightCodeCup Pick me as your wildcard entry, I promise I’m just the right amount of chaos
which team are you? :)
I can't wait for the OEIS CODE CUP world finals!!
Thank you for the great contest, this was my first time participating in such a heuristic-ish contest and I loved every second of it!
I spent most of my time on problem A trying to deal with the IK solver, and I think I spent too much time on trying to integrate a generic one for the 3-link arm and not enough on actually working on cost optimization. I used a simulated annealing approach with two strategies randomly chosen at every step:
And in the end I think I should've spent more time on looking at each test case more carefully to better fine-tune the strategies, especially on cases like test case 8.
We just did a greedy solution instead (pick the next target so that the cost of changing the angle is minimal) and it worked pretty good. Also reused the 2-link arm solution for 3-link arms, just checking 1024 angles for the first link and then solving the rest.
I think C1/C2 was interesting, but it was very unpleasant to have the VM in Kotlin with no prior notice of it. I don't have any Kotlin setup so I had to run it online which posed runtime and output restrictions. If it's not going to be an easily runnable language like Python, I don't see a reason not to notify people to set it up. I solved C2 about 3 minutes after the end so any slowdown definitely made a huge difference for us.
I know that it's done because Jetbrains is a sponsor, but it also sounds beneficial for them to have everyone set up a Kotlin environment. Now I will just have Kotlin nightmares instead :\
Big thumbs up for this; I have literally spent more than an hour to install all the necessary stuff (apparently I had an outdated Kotlin version or w/e and the code did not want to compile/build). Great task, but giving an example Kotlin and recommending to run it locally would be fair, imo.
The kotlin version of my local computer (a debian bookworm) is too old to run the code. After spending some time to find a way to upgrade it. I just came up that I can run the program in a docker.
After random searching on dockerhub, I finally found this to be working.
+100 on this; I thought solving C2 20 minutes after the end was bad but I see it could have been way worse... I'm also fairly sure it took me longer than that to run the provided Kotlin code.
This could have been a good opportunity to get people to try out Kotlin if done right; now I'll just have bad memories of it instead.
+1 I was running a lot of inputs in custom invocation until I noticed the pattern and figured out the problem but it was quite slow.
For me this was even funnier. I've read this part in the statement "the solution is written in assembly" and thought that the solution is literally written in assembly. So I've spent several minutes rereading the statement and redownloading zip archive trying to figure out why in the downloaded files there is only some Java-looking code (since I've never seen Kotlin before) and no ASM-looking code.
On ubuntu that's just
snap install kotlinbtw. And for windows/mac any LLM should give you a short instruction to get CLI version.I agree that installing it during the contest sucks. But tbh there is no real rule that you should use python/cpp, and using them just because everyone uses them will solidify them without any particular reason.
My complain about having VM in Kotlin is that it's just an extra layer of abstraction without any particular add-on to the problem. I am not sure it's really possible to distribute an ASM code to everyone so everyone can run it, but my problem is that I need to study this specific machine to verify if my ASM intuition works or not. (and, well, i spent a while decomposing some parts of it).
Also the single code file is not documented while for any ASM you can find information online. And LLM's are probably better with converting any ASM dialects than with custom emulator. There should be a better sweet spot, but I haven't done my research on that, maybe I'm wrong.
That is unfortunate and we apologize for the inconvenience. We will definitely provide better instructions next time.
We hope you’ll give Kotlin another chance though :)
Yeah, we are really sorry for this. We had an idea to ask you to do this, or suggest using play.kotlinlang.org, but last several days before the contest too many things were happening and it slipped from our minds :(.
pick team testuwuers (reirugan Friedrich Intellegent) as a wildcard! as a team of three (self-identified) anime girls, we will bring a very necessary demographic to the competition
hope there is a mirror for the finals!
No programming language restrictions, but need to setup a Kotlin environment and run/debug/understand a Kotlin program :(
That was really cool! Didn't know optimization contests could be fun for me too!
Thank you, I got some really good IPSC vibes from the contest.
It was also interesting to observe that we got quite an amount of points by producing a very small amount of code (C1), or none at all (B1, B2).
It is understandable that, given the vast number of qualified contestants (75), it is not a small expense, and we should not take it for granted that all the expenses will be covered.
But on the other hand, it is also disappointing that the main expense for contestants, flight tickets, are not covered (except top 3 teams and students), given the number of sponsors and previously mentioned that "aim to cover trip expenses for the finalists" in the rules and updates.
The restrictions on travel expenses are one issue, but it's still a bit difficult to understand why only two nights are covered when the event runs from the morning of one day to the afternoon of the next. Considering that participants might have to stay up all night, it seems a little tough for them, doesn't it? I do understand that accommodating 25 teams is quite a challenge.
On one hand, I actually feel relieved knowing that our team's flight tickets won't be covered after finding out that I would probably have to go to another country to apply for Serbian visa.
On the other hand, it feels a bit disappointed with how we've been communicated. I guess the organizers probably wanted to wait until the qualification concluded to estimate the cost they would need to cover (hence, the part "as many of the trip expenses for the finalists as possible"). Something like "we won't guarantee to cover all expenses for finalists" from the beginning would be more transparent.
For the folks who solved problem D in the finals, how did you approach it? We found the problem very interesting and weren’t able to make any use of LLMs to solve it (other than the first input).