Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### Kostroma's blog

By Kostroma, 3 weeks ago, ,

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?

• +424

 » 3 weeks ago, # |   0 Why the unusual contest format? Are there not going to be problem statements?
•  » » 3 weeks ago, # ^ |   +18 We don't want to spoil the fun and tell in advance and tell everything about the contest. The statements will be in English only because we are running out of time in preparation and have to prioritize things.
•  » » » 3 weeks ago, # ^ |   0 means there will be statements.
•  » » » » 3 weeks ago, # ^ |   +46 Or rather that all statements that will be prepared will be in English
•  » » 3 weeks ago, # ^ |   +173 There will be statements, if we have enough time, you know
 » 3 weeks ago, # |   +100 Clashes with topcoder srm 777
•  » » 3 weeks ago, # ^ |   +24 Unfortunately, this is the time of big party in Petrozavodsk camp, so we can't change the time of the competition.
•  » » 3 weeks ago, # ^ |   +59 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 --Someone--'s phrase was given so much negative feedback? (Currenly I see -51.) Shouldn't we downvote non-informative bulk, and encourage adequate communication?
 » 3 weeks ago, # |   -13 Awesome!I hope I'll enjoy it
 » 3 weeks ago, # |   +46 A second version of April fool
 » 3 weeks ago, # |   +8 >inb4 angry Um_nik complaining about quality after the contest
 » 3 weeks ago, # |   -6 "Funny" -> Me: Wow! cool. "div. 1 recommended" -> Me: It will be funny for me :|
 » 3 weeks ago, # |   +10 Any constraint on team size?
•  » » 3 weeks ago, # ^ |   0 Yes, the max team size is 3 people.
•  » » 3 weeks ago, # ^ |   -8 Added to the announcement, thanks!
 » 3 weeks ago, # |   0 Note that now you can download the encrypted archive with open tests.
 » 3 weeks ago, # |   +3 It would be funnier if we get the problem statements before the contest ;)
•  » » 3 weeks ago, # ^ |   +27 Please don't ask impossible things, let's just hope the statements will be available at the start.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 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? :)
 » 3 weeks ago, # | ← Rev. 2 →   +16 "The authors to blame are: Kostroma, zemen, Golovanov399 and mathbunnyru." Why can't we blame ArtDitel? :D
•  » » 3 weeks ago, # ^ |   +38 Fixed, you are welcome to blame him too now.
•  » » » 3 weeks ago, # ^ |   +46 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:
•  » » » » 3 weeks ago, # ^ |   +43 You'll be answering questions like "why the problems are so bad??" in the contest interface.
 » 3 weeks ago, # |   +175 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
•  » » 3 weeks ago, # ^ |   +161 Comparing with our contest, this seems like a truly inspiring work of art.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +55 Comparing with high-frequency trading, this seems like a truly inspiring work of art.
 » 3 weeks ago, # | ← Rev. 2 →   +76 "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?
•  » » 3 weeks ago, # ^ |   +16 Thank you, that's the path we'll choose.
•  » » 3 weeks ago, # ^ |   +11 Maybe they use those 10 minutes to prepare other problems too, who knows
 » 3 weeks ago, # |   +18 GuessTheBugForces
 » 3 weeks ago, # |   +3 5kB/s, 2.0MB now. oh man..
 » 3 weeks ago, # |   0 "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.
•  » » 3 weeks ago, # ^ |   0 answers to open test cases are in '.a' files
•  » » 3 weeks ago, # ^ |   +5 .a files are outputs
•  » » 3 weeks ago, # ^ |   +2 If you aren't able to open the files try to delete .a part.
 » 3 weeks ago, # |   +13 Imagine reading J's statement on a regular Codeforces/ICPC contest...
•  » » 3 weeks ago, # ^ |   +10 Good idea, will add this problem to next rated cf contest
•  » » 3 weeks ago, # ^ |   0 It would be funny to give this problem printed on a piece of paper :)
 » 3 weeks ago, # |   0 It could be better if difficulty was like A>B>C>D>...
•  » » 3 weeks ago, # ^ |   0 Sorry, we didn't have time to sort problems ¯_(ツ)_/¯
 » 3 weeks ago, # |   +1 I like the format, but the problems are to hard, was not able to solve one.
•  » » 3 weeks ago, # ^ |   +8 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.
 » 3 weeks ago, # |   +18 After 1 hour:UPD5 The contest was rated.
•  » » 3 weeks ago, # ^ |   +22 Great idea, thanks!
 » 3 weeks ago, # |   +4 All statements in cf should be like Problem J
 » 3 weeks ago, # |   +3 Why my poorly prepared solutions are not passing?
 » 3 weeks ago, # |   0 I want more.
 » 3 weeks ago, # |   0 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?
•  » » 3 weeks ago, # ^ |   0 gosh, I tried different buffer-size bitset, either TLE or MLE..
•  » » 3 weeks ago, # ^ |   +34 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.
•  » » 3 weeks ago, # ^ |   0 You need to use long long instead of bitsets :))
•  » » » 3 weeks ago, # ^ |   -10 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?
•  » » » » 3 weeks ago, # ^ | ← Rev. 4 →   +8 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
•  » » » » » 3 weeks ago, # ^ |   0 Saw it, thanks!
•  » » » 3 weeks ago, # ^ | ← Rev. 4 →   0 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.
•  » » » » 3 weeks ago, # ^ |   0 It's true, solutions with recursion are too slow. The intended solution uses DP on the topological sort.
•  » » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 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
•  » » 3 weeks ago, # ^ |   0 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.
 » 3 weeks ago, # |   +8 What's the Djikstra bug?
•  » » 3 weeks ago, # ^ |   0 we used std::priority_queue with default comparator instead of std::set
•  » » » 3 weeks ago, # ^ |   0 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
•  » » » 3 weeks ago, # ^ |   +9 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.
•  » » 3 weeks ago, # ^ |   +43 We gonna publish the editorial next year, stay tuned!
•  » » 3 weeks ago, # ^ |   -60 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.
 » 3 weeks ago, # |   0 Will we be able to submit after contest ended?
•  » » 3 weeks ago, # ^ |   +3 It should be possible, the problems will be added to the archive.
•  » » 3 weeks ago, # ^ |   0 now available
 » 3 weeks ago, # |   +15 What is the bug in F?
•  » » 3 weeks ago, # ^ |   +19 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.
 » 3 weeks ago, # |   0 Never thought I would ask this, but how to solve A?
•  » » 3 weeks ago, # ^ |   0 We mixed up n and m and < and > :((
•  » » » 3 weeks ago, # ^ |   0 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!
•  » » » » 3 weeks ago, # ^ |   0 (random stuff in solution lol)
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 If you mix up m and n, you get very different rows and columns :)
•  » » » » » 3 weeks ago, # ^ |   0 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
 » 3 weeks ago, # |   -18 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)
•  » » 3 weeks ago, # ^ |   -8 1) swap(n, m) 2) wrong order in priority queue
•  » » » 3 weeks ago, # ^ |   -18 1)I thought they swapped > and < in A 2)nice
•  » » 3 weeks ago, # ^ |   +18 I think you should read the announcement once again :)
•  » » » 3 weeks ago, # ^ |   -18 I read it, I knew solutions would be wrong, but not that wrong
•  » » » » 3 weeks ago, # ^ |   +26 What can I say? We tried to be wrong in the best way possible.
•  » » » » » 3 weeks ago, # ^ |   -18 J was the best statement ever, make statements like this always
•  » » » » » » 3 weeks ago, # ^ |   +2 We did like the statement too!
 » 3 weeks ago, # |   0 Will the solutions of contestants be made public?
•  » » 3 weeks ago, # ^ |   +5 Buggy solutions for the problems with buggy author solutions — indeed, very useful to be published :)
 » 3 weeks ago, # |   0 what's the E bug? Besides, the correct formula is $1-p^n-(1-p)^n$ right?
•  » » 3 weeks ago, # ^ |   0 We're not sure, but it seems to be called an overflow.Wait a bit, we will publish the solutions :) Well, we hope.
•  » » » 3 weeks ago, # ^ |   0 But you just said "We gonna publish the editorial next year, stay tuned!"
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Nope, that was my colleague Kostroma.no jokes: We will publish them in several minutes, stay tuned.
•  » » » » 3 weeks ago, # ^ |   0 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.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 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
 » 3 weeks ago, # |   0 Contest is finished but still, authors are writing buggy statements in the comment section.
 » 3 weeks ago, # |   +17 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?
•  » » 3 weeks ago, # ^ |   +39 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?
•  » » » 3 weeks ago, # ^ |   0 I don't know if you're selling hugs or protesting global warming in Winter but yeah, it looks better.
•  » » » » 3 weeks ago, # ^ |   +18 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)
•  » » » » » 3 weeks ago, # ^ |   +18 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...
 » 3 weeks ago, # |   +27 In our country, there's nothing unusual about preparing contests the night before.
•  » » 3 weeks ago, # ^ |   +39 It's cool, because we were offered to write next SEERC, no need to change our workflow.
 » 3 weeks ago, # |   +11
 » 3 weeks ago, # |   +2 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.