Hello!
Traditionally AIM Tech organizes a big party for Petrozavodsk camp participants to have fun and get an opportunity to communicate with each other. Usually it comes along with a funny contest in unusual format. This year we decided to share the fun with all codeforces community!
This year we came up with a format requiring (probably) less time for preparing the contest. It is somewhat similar to an ordinary contest with a 3-hour duration. We already have some problem ideas, so it should be super easy to prepare the problems just one night before the competition. We hope everything will run smoothly!
The contest will start on Feb/03/2020 19:15 (Moscow time). It could be a bit rescheduled due to onsite delays.
It will be an unrated funny competition. Unlike usual ICPC-style contests, you'll be given an archive with several open test cases and answers for each problem. You'll have some sample test cases in the statement too, they'll be included in the archive. However, the solutions will be tested against both open and hidden tests. The open tests will be published as an encrypted zip-archive in this post. The password will be published just before the start of the contest.
The statements will be in English only because we are running out of time in preparation and have to prioritize things.
It's not 100-percent clear at the moment, but it seems the contest will be somewhat hard, so we recommend it for div. 1 participants. However, div. 2 participants are welcome as always, but we can't guarantee the contest will be a perfect match for them.
It's possible to participate both individually and in teams of maximum 3 persons.
Another point to mention is that the order of problems could be not the same as the order of their difficulties. But we'll try to do so. A bit.
The authors to blame are Kostroma, zemen, Golovanov399, mathbunnyru and ArtDitel.
As you may notice, it is just one night before the competition, so we should start preparing the problems. We hope that we'll manage not to do very stupid bugs in the tests. See you at the competition!
UPD It's still more than 4 hours before the contest, but the open tests are already prepared! You can download the archive using one of the two links: one two. The encrypted archive contains another archive containing the actual tests.
The password will be published here shortly before the start of the contest.
UPD2 We have to move contest 10 minutes forward, because we need to prepare the last problem :(
UPD3 Oops, the contest is about to start, but we still don't have correct solutions! Unfortunately, each authors' solution contains a bug (or even several bugs!). However, we decided not to cancel the competition. We give you the outputs of the model solutions on open tests in the archive. Guess all the bugs in our solutions and get OK for the code with exactly same bugs! Good luck and have fun!
The password to the archive will be published as a clarification in the contest interface.
UPD4 The password to the archive is oops_seems_that_nobody_tested_the_solutions
UPD5 The editorial is published, but it still does contain bugs, wait a bit while it is being debugged.
UPD6 Feel free to share your opinion in the comments! Were the solutions enough buggy? Was it enough hard, or we should've added a couple of hard problems? Do you want to solve such contests in future?
Why the unusual contest format? Are there not going to be problem statements?
We don't want to spoil the fun and tell in advance and tell everything about the contest.
means there will be statements.
Or rather that all statements that will be prepared will be in English
There will be statements, if we have enough time, you know
Clashes with topcoder srm 777
Unfortunately, this is the time of big party in Petrozavodsk camp, so we can't change the time of the competition.
Sometimes I don't understand our community. Informing about timing coincidence with TopCoder SRM 777 was quite important. It could possibly encourage the contestmakers to shift the start a little bit. Why solvemproblr's phrase was given so much negative feedback? (Currenly I see -51.) Shouldn't we downvote non-informative bulk, and encourage adequate communication?
Awesome!I hope I'll enjoy it
A second version of April fool
>inb4 angry Um_nik complaining about quality after the contest
Any constraint on team size?
Yes, the max team size is 3 people.
Added to the announcement, thanks!
Note that now you can download the encrypted archive with open tests.
It would be funnier if we get the problem statements before the contest ;)
Please don't ask impossible things, let's just hope the statements will be available at the start.
You know, I'm one of the authors, it's my first contest in a long time, and the first time I do actually prepare the contest as an author and we prepared the problems one night before the competition.
What could go wrong? :)
"The authors to blame are: Kostroma, zemen, Golovanov399 and mathbunnyru."
Why can't we blame ArtDitel? :D
Fixed, you are welcome to blame him too now.
Why me? I will just sit and drink beer during contest :(
But actually you can blame me for not preparing contest at all yesterday night :troll:
You'll be answering questions like "why the problems are so bad??" in the contest interface.
Hi Codeforces.
To be well prepared for the contest, together with Fly_37 and w0nsh we decided to make our version of Poorly Prepared Snowman.
Cheers from Petrozavodsk!!! <3
Comparing with our contest, this seems like a truly inspiring work of art.
Comparing with high-frequency trading, this seems like a truly inspiring work of art.
"UPD2 We have to move contest 10 minutes forward, because we need to prepare the last problem :("
Why not just start the contest and add the last problem during the contest?
Thank you, that's the path we'll choose.
Maybe they use those 10 minutes to prepare other problems too, who knows
GuessTheBugForces
5kB/s, 2.0MB now. oh man..
"We give you the outputs of the model solutions on open tests in the archive." Sorry, I am not able to find the outputs. I can see only test cases.
answers to open test cases are in '.a' files
.a files are outputs
If you aren't able to open the files try to delete .a part.
Imagine reading J's statement on a regular Codeforces/ICPC contest...
Good idea, will add this problem to next rated cf contest
It would be funny to give this problem printed on a piece of paper :)
It could be better if difficulty was like A>B>C>D>...
Sorry, we didn't have time to sort problems ¯_(ツ)_/¯
I like the format, but the problems are to hard, was not able to solve one.
Sorry about that, it wasn't that easy and fun to prepare the easy problems. We tried to emphasize that we recommend it for div. 1 participants.
After 1 hour:
UPD5 The contest was rated.
Great idea, thanks!
All statements in cf should be like Problem J
Why my poorly prepared solutions are not passing?
I want more.
How to solve B, even without bug? I used bitsets and got MLE. Then I wrote something ugly that reused old bitsets which got AC, was this intended?
gosh, I tried different buffer-size bitset, either TLE or MLE..
You can solve the problem with linear memory usage.
If you have $$$k$$$-bit words, the time complexity is $$$\mathcal{O}(E \frac{V}{k})$$$. But we can get the same complexity by first calculating for only the first $$$k$$$ vertices which vertices can reach them, then for only the second $$$k$$$ vertices and so on. This again takes $$$\mathcal{O}(E \sum_{i = 1}^{\frac{V}{k}} \frac{k}{k}) = \mathcal{O}(E \frac{V}{k})$$$ time.
You need to use long long instead of bitsets :))
Is this a serious reply or just a joke? If the former, can you explain how? Also, how does it take less memory than bitsets?
Actually you can check out the editorial now. Sometimes it's hard to stop joking, but I meant what is written in the mango_lassi's comment just above.
UPD I would say it was more like a hint than a joke, but after I posted it I just saw the comment with a solution
Saw it, thanks!
I get TLE with Longs... probably due to overhead from recursion (cause I basically just use memoized DFS). I could only pass by using bitsets and experimentally adjusting the bitset size to use per round... my sweet spot is somewhere around $$$2^{13} \sim 2^{14}$$$ bits.
It's true, solutions with recursion are too slow. The intended solution uses DP on the topological sort.
Hm, finding the topological sort beforehand to avoid the looped recursion doesn't seem to improve the performance much to me (still TLE with 64-bit long partitions, bitset partition performance similar). Maybe it's just Kotlin things. Ah well, at least it pushed me to learn topological sort
Actually we thought that this problem is very classical and all div.1 participants know how to solve it. Turns out we did a dramatic mistake.
What's the Djikstra bug?
we used std::priority_queue with default comparator instead of std::set
Another thing is that we don't consider vertices that have already been at the top of the heap — the standard trick when you write dijkstra in doubles, for example
Duh, that's so random. I spent more than an hour on this problem writing some MITM to tell me which paths correspond to some different values on 5th test and have not seen any logic there and would have never thought of this.
We gonna publish the editorial next year, stay tuned!
You should submit a wrong solution. This contest has a new codeforces round format, where authors make buggy solutions and you have to guess all the bugs. :)
Hope this helps, please feel free to ask.
Will we be able to submit after contest ended?
It should be possible, the problems will be added to the archive.
now available
What is the bug in F?
I think each if/else has been randomly swapped. I just brute-forced which swaps produce correct answers, and there was exactly one "correct" one.
Never thought I would ask this, but how to solve A?
We mixed up n and m and < and > :((
Well I got the first part, but the second could not possibly get, tried all 4 combinations of < and > and also cutting the matrix in weird parts. What do you mean mixed < and > ? Take test 3, answer is (6,3), which gives 2923880. That number is neither maximum or minimum in row or column!
If you mix up m and n, you get very different rows and columns :)
Tried that too, flipped it all around, neither 2839457 is maximum or minimum, 3851539 is maximum in current row but not anything in column, and 5796409 is maximum in both row and column and did not fit
Me writing correct A solution:Done. Me seeing that authors solution in some given test case outputs column that doesnt exist:Alright,im done with this problem, goodbye. Seriously, how authors "solution" managed to print: 1)nonexistent column in A 2)some random distance in Dijkstra(it was minimal sometimes, but my dijkstra always outputted correct minimum) in D 3)Some weird stuff in C(it looks like they created a segment tree for all cases and didnt create for each case,as was said in statements)
1) swap(n, m) 2) wrong order in priority queue
I think you should read the announcement once again :)
I read it, I knew solutions would be wrong, but not that wrong
What can I say? We tried to be wrong in the best way possible.
J was the best statement ever, make statements like this always
We did like the statement too!
Will the solutions of contestants be made public?
Buggy solutions for the problems with buggy author solutions — indeed, very useful to be published :)
what's the E bug? Besides, the correct formula is $$$1-p^n-(1-p)^n$$$ right?
We're not sure, but it seems to be called an overflow.
Wait a bit, we will publish the solutions :) Well, we hope.
But you just said "We gonna publish the editorial next year, stay tuned!"
Nope, that was my colleague Kostroma.
no jokes: We will publish them in several minutes, stay tuned.
This was a punch.
However, I don't like to give leaves without figs. The important thing is when the real editorial is published, not this currently buggy thing.
Funnily enough my ModInt implementation had that overflow bug, but not quite the same one. But thanks to this contest I found a way to prevent this issue for the next time some contest somewhere decides to use $$$1234567891$$$ or even $$$2147483647$$$ (INT_MAX) as the modulus
Contest is finished but still, authors are writing buggy statements in the comment section.
I don't like such contests and guessing what authors intended, but I must say this one was well prepared and problems seem interesting.
Also, why the miniature profile pic of Kostroma has so low quality?
Thanks for the kind words!
Since the quality of the contest was not that bad, I decided to change the profile picture. Does it look better now?
I don't know if you're selling hugs or protesting global warming in Winter but yeah, it looks better.
I thought you know a bit Russian :) You can check out two links: one two (the second one in Russian, but the text is applicable to Google Translate)
Oh, that's a serious thing, don't mind my previous comment. It was a joke about the quality of your pic again. I know the cyrrilic alphabet but can't see exact characters in your new pic...
In our country, there's nothing unusual about preparing contests the night before.
It's cool, because we were offered to write next SEERC, no need to change our workflow.
I didn't participate, but I read the problems and the editorial afterwards. A bit of unrated riddle-like programming is certainly a breath of fresh air and a fun thing to do once or so a year. Sure, the answers may be arbitrary and biased towards users with particular experiences rather than based on knowledge, but it is after-all unrated, and meant to just blow off some steam stresslessly.
I tried solving question D — Dijkstra, but I've failed test 5. It seems the solution that you posted for this test case is 4764268, but if you choose a path through the vertices 1->16->11->20, the cost is 2580639, which is smaller. Did I read the question incorrectly or is this a mistake? Thanks in advance.
Why is problem J so long?