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

### farmersrice's blog

By farmersrice, history, 2 months ago, ,

I cannot change handle color to headquarters!!!!!! It's a tragedy. The people are suffering, think of the children who have had their christmas ruined! Young schoolboys sobbing as they realize that they cannot even live out the dream of working at CF during the christmas magic. MikeMirzayanov please fix. Thanks for reading, like and subscribe.

• +317

By farmersrice, history, 2 months ago, ,

It has come to my attention that some of you geniuses are writing super fun games and tools! (UNoobAble)

So! As a user of codeforces, it is your duty to share with the world all the cool things you have done! Everyone wants to brag about what they've made; now is the time!

• +73

By farmersrice, history, 3 months ago, ,

• +100

By farmersrice, 5 months ago, ,

Today I want to share some interesting problems, that are very algorithm-like/logical in terms of thinking but are not really standard (kind of like some good ad-hoc question you can share with your friend). I'm not exactly sure what to call these, but they are very interesting to me and I hope they are interesting to you as well. If you have something similar, please share.

For some people they are quickly solvable and for other people (like me lol) it is near impossible. I tried to make the problem statements as interesting as possible. Images and problem statements are mostly compiled by me.

I will put up solutions in a day or two (viewing the solution kind of ruins the problem, much more than for ordinary Codeforces problems). Think! It's really much more fun than regular problems. Double promise!

# Two papers

source: unknown

You are playing a game against a magician! (You slept at 4 am last night. Who knows how you got here? Maybe you should sleep more. cough cough Mahotsukai) The guy says he's in charge of every const int MAGIC ever written. He also promises to show you some magic in his new mind game. You're a little skeptical.

Here's how it works. The magician enters the magic room and takes two pieces of paper, and writes two arbitrary real numbers on them, each in range from $0$ to $1$. Once the numbers are written, they cannot be changed. Then, you enter the magic room. You can pick exactly one piece of paper and look at the number written on it. Then, you must submit one of the two papers to the magician. Your goal is to submit the paper which has the greater number written on it. (If the two numbers are the same, then you win by default.)

Example: The magician writes down numbers $0.7$ and $0.8$ on a paper. You pick one paper and it is revealed to have the value $0.7$. If you submit the paper you looked at, you'll lose, because $0.7$ < $0.8$; by the same logic, if you submit the paper you did not look at, you'll win.

Figure 1: All the information you'll get.

One last thing: The magician is also a mind reader. He will know everything about your strategy before he even writes the numbers down. And when he knows your strategy, it will be hard to beat him!

You hate losing, and you love winning. Luckily for you, there's a strategy that guarantees you a win probability strictly greater than $50$%. You're going to show that pesky magician what you're made of, right? His magic constants have given you wayyyyyy too many FSTs. Now it's your chance to get back at him by beating him at his own game. What's your plan?

# One hundred prisoners

source: unknown

Uh oh. After you cheesed a data-structure-heavy problem that was meant to be solved in $O(n\ \sqrt{n}\ log\ n)$ with some sketchy $O(n^2)$ with pragmas, bitset, and the magic of low constant, the Codeforces Police (who strictly enforce algorithmic ideas) have finally caught you. You've just been put in Algorithm Prison, where inmates are condemned to solve high constant implementation problems with 0.5 second time limits for the rest of their lives. There are a total of $n = 100$ prisoners in the prison (including yourself).

The guards have a special challenge, since you're so smart. If you solve it, then you get to go free! No pragmas this time, though.

Each prisoner is assigned an integer from 0 through $n - 1$, inclusive. There can be multiple inmates with the same number assigned to them. There can be numbers that are not assigned to any prisoner.

The numbers are hidden from anyone's knowledge from an entire week, giving you ample time to strategize with your fellow inmates. The guards have already told you how it works ahead of time: On the day of the challenge, all prisoners are put in a giant circular room. No communication of any form is allowed between prisoners once they've entered the room. (This is strictly enforced by the Magic Duck, who will instantly eat any bit of information transmitted between prisoners, no matter what form this information takes.) Each prisoner can see the numbers assigned to all the other prisoners, but cannot see the number assigned to them.

Figure 2: The Magic Duck. He's hungry — for KNOWLEDGE. Quack.

After everyone has seen everyone else's numbers, all prisoners are taken into solitary rooms. Each prisoner must attempt to guess his or her own number. If at least one prisoner guesses his or her number correctly, everyone gets to go free!

But you hate relying on luck and probabilities. Remember that one time when you wrote a randomized hashing solution that was just impossible to break, but you ended up getting Wrong answer on test 147? That ain't happening again. This time, you're going to find a mind-blowing, stunning algorithm that guarantees victory for you and all your buddies. The question is: What's the algorithm?

• +226

By farmersrice, history, 5 months ago, ,

Because that's when they get AC.

• +301

By farmersrice, history, 6 months ago, ,

I want to delete my account, when will this feature be added? It has been so long since it was mentioned, but it seems nothing has been done for it.

• +34

By farmersrice, history, 7 months ago, ,

https://codeforces.com/contest/1200/submission/58612411

https://codeforces.com/contest/1200/submission/58619785

I'm that unlucky to just get the wrong base on test 19? Are you kidding me? Can I get this restored?

• +19

By farmersrice, history, 7 months ago, ,

For an entire 23 hours the world lost its shining gem: Codeforces. Just before the greatest site in the universe went down, I finally was finished with not-participating in the Educational Round 70 and made my last not-submission at not-contest time. I instinctively rushed to the greatest server of all time, the most shining pinnacle of pseudointellectualism: Proof by AC. Now was the time to make memes. Of course, this involves orzing many great and talented geniuses. (If you were unaware, it is a civic duty.) As a natural consequence, one must look at the friends' standings, to figure out how much to orz. Only logical, right?

But suddenly, while refreshing the almighty Friends Standings page (orz), DISASTER STRUCK!!!!!!!!!!

We encountered unknown technical issues, the website is temporarily unavailable. It is not yet possible to give any predictions when it will be repaired. Sorry about it.

For the rest of the day my mind was in agony as I was unable to access the greatest site in the universe, Codeforces. How else would I be able to fulfill my organic desire for pseudointellectualism and witty short comments? After all, upvotes are like the emotional currency of the mind. At night I tossed and turned, unable to think about the fact that the greatest site in the universe, Codeforces, might be encountered unknown technical issues, the website is temporarily unavailable. It is not yet possible to give any predictions when it will be repaired. Sorry about it.

In the night I had a miraculous vision. From the ashes of Codeforces would rise Codeforces 2.0. Never mind the fact that Codeforces was still in beta and hadn't even reached version 1 yet. CODEFORCES 2!!!!!!!!!!!!!!!!!!!!!!!!! Sample logo:

Actually it was kind of like Lichess 2.0, in the fact that it looked cooler but was actually complete garbage. And also in this vision everyone's ratings were reset to 1500, except for the top 10 who got manually restored. Thankfully I am very bad at visions.

As I prepared to proceed with my day, already colored grey by the absence of the shining light of Codeforces, I went back to my computer after eating a long and tumultuous breakfast, my mind uneased by the trivialities of food. And I reopened my browser to encounter the familiar message from the greatest site in the universe, Codeforces. After posting "JUSTICE FOR CODEFORCES" a couple times in discord, I finally felt that my duty was fulfilled. Solidarity was shown. Cue Starship Troopers scene "I'm doing my part!".

Then, all of a sudden, an image pops up. "Educational Codeforces round 70, open hacking phase finished, final standings". IMPOSSIBLE!!!!!!!!! I check again, but the greatest site in the universe still shows the same old error message.

I refreshed and refreshed and refreshed, but nothing came up. Until finally, the greatest site in the universe returned before my eyes.

The room flooded with a brilliant white light. The entire city block cried out in unison, a resounding sound soon heard around the world. It was back. Humanity was saved. The Dark Ages 2.0 had finally come to an end as the bringer of light, the greatest site in the universe, had finally returned. CODEFORCES. Sitting in my room, papers strewn across the floor in moments of agony while the site was down, I was paralyzed with a feeling of pure overwhelming bliss as the photons streamed into my eyes, weeping tears of joy.

Now remains the only question: Where were you when codeforces back?

• +256

By farmersrice, history, 8 months ago, ,

We need one, now!!!!!!!!! Let's do it, MikeMirzayanov. Or maybe we should ask atcoder for this one?

• +493

By farmersrice, history, 8 months ago, ,

The new version is not my style. I don't like bold things, it makes it harder to read for me. Is there an option to go back to the old style or something? That would be much nicer. Thanks. Pinging MikeMirzayanov.

• +98

By farmersrice, history, 9 months ago, ,

You have $N$ cups, each containing some amount of water. Each cup is identical and has maximum capacity $M$ milliliters. In one operation, you may select any two cups $a$ and $b$, which represents pouring water from cup $a$ to cup $b$. If the sum of the cups' volume is less than or equal to $M$, cup $a$ ends up empty and cup $b$ contains all the volume of the cups. If the sum of the cups' volume is greater than $M$, then cup $b$ ends up filled to capacity $M$ and cup $a$ contains the remainder of the water. Suppose the total volume of water in all cups is $V$. The question is: What is the minimum number of operations necessary to create $\left \lfloor{\frac{V}{M}}\right \rfloor$ cups of water that are filled to maximum capacity?

No constraints, the problem is original and comes from a real life scenario. My hypothesis is that as long as you merge small to large then it will take the same number of operations, which is also optimal — but I can't think of how to prove this. Any ideas?

• +11

By farmersrice, history, 10 months ago, ,

So today's contest was declared unrated because of a mistake in the statement/test preparation for problem A. Of course, I was upset, given that I was doing relatively well even after the re-judge. (Sad to say, I ragequit and went to do work)

It seems like the biggest problem in a case like this is when some participants get WA after 30 minutes, receiving a big penalty due to the re-judge, as opposed to people who got it right in the first few minutes. (see here). Aside from this, I don't see any major issues coming from the re-judge that call for making the round unrated.

In my view it looks like a simple and easy fix for this would just be to shift all the submissions' time penalty calculations that were rejected in the re-judging to the time that they would have been at from the start of the round. What I mean by this is, for example, if some user solves problem A at time 00:03, and the rejudge gives his or her solution WA on 00:30, and then this user solves it given another 2 minutes at 00:32, then the end result score penalty calculation should have the +1 penalty for wrong answer and assume that the user has solved this at 00:05 (3 minutes first submission, then took 2 minutes to fix error — so shift to 5 minutes).

Then at the final judging the scores will closely reflect results that would have occurred as if no error had happened in the first place, and the great penalty discrepancy would no longer be an issue.

Of course, we can't change the result or status of today's round (especially considering that the case in which the triangle direction could have been reversed was not clarified in the statement), but this might be a good way to handle similar situations in the future. What do you think?

• -25

By farmersrice, history, 14 months ago, ,

Title.

• -34

By farmersrice, history, 14 months ago, ,

I would like to cut down on some of the spam in comments. Thoughts?

• +108

By farmersrice, history, 15 months ago, ,

https://codeforces.com/contest/1061/submission/46134575

https://codeforces.com/contest/1061/submission/46134614

Same code for 1061F gives wrong answer on test 1 for C++17 (invalid input format), but goes to test 159 for C++14 (accepted after submitting a second time). I feel like my problem lies within some input issue or something to do with returning the vectors, but I can't find it. Can someone please enlighten me? Thanks in advance.

• -24

By farmersrice, history, 16 months ago, ,

http://codeforces.com/contest/1074/submission/45462396

http://codeforces.com/contest/1074/submission/45462405

These two codes are exactly the same, except for this part:

In the Wrong answer on test 14 submission:

for (int i : inTree[rootp]) {
inTree[rootq].pb(i);
distToRoot[i] = distToRoot[i] ^ distToRoot[p] ^ edgeWeight ^ distToRoot[q];
root[i] = rootq;
}


In the Accepted submission:

edgeWeight ^= distToRoot[p] ^ distToRoot[q];

for (int i : inTree[rootp]) {
inTree[rootq].pb(i);
distToRoot[i] ^= edgeWeight;
root[i] = rootq;
}


(This is the end of the method, so xor-equals edgeWeight shouldn't change anything later on.)

I thought xor sum is both commutative and associative? What's the difference between these two snippets? Am I missing something really obvious? Thanks in advance.

• -3

By farmersrice, history, 16 months ago, ,

It seems there are a significant number of hacks on Codeforces — and not the type where halyavin nukes your solution.

Just recently there were those 2 chinese guys who got accounts hacked (here).

Roughly a year before that there was this one round where a bunch of well-known reds had their submissions hacked and submitted by a horde of random accounts.

And now this post (here).

Are there any updates on these? How did they happen? Are the bugs fixed? I don't think I ever saw anything except "ok, we got hacked but 3 days later we got accounts back, problem solved".

I'm not trying to say nothing is being done, of course, there is probably a lot of good work going on behind the scenes, but it seems nobody knows what exactly is happening.

• -7

By farmersrice, history, 16 months ago, ,

Super casual, no commitment necessary.

Only requirement is being purple or higher at some point in the past (or now).

There's 12 hours left to register and obviously 2 is better than 1. PM me

• +6

By farmersrice, history, 17 months ago, ,

Just curious as to what you guys like to do. Personally, I enjoy playing go/chess and a variety of other games, and listening to music that has 0 correlation with my actual life. (hmu if you want to play go or chess)

• +112

By farmersrice, history, 17 months ago, ,

I searched a lot of resources online, but they're super long. I don't want to spend tens (hundreds?) of hours reading a poorly-written introduction, so I thought I would ask here.

My math background is limited (currently doing linear algebra).

• +29

By farmersrice, history, 18 months ago, ,

I'm using mingw, gcc --version gives 5.3.0 on my windows 10 desktop. When I add the lines

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


and compile, it says

c:\mingw\lib\gcc\mingw32\5.3.0\include\c++\ext\pb_ds\hash_policy.hpp:610:78: fatal error: ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp: No such file or directory
compilation terminated.


I don't remember what it says on mac but it also doesn't work there. (I think mac is gcc 4.8 installed through homebrew.)

In the past I just used ubuntu vm to use the library, lol. But it is a bit of an annoyance.

Any tips?

• +8

By farmersrice, history, 18 months ago, ,

Now that there are like 2000 tutorial blogs by high-level users, I believe there should be a separate section for them as opposed to mashing them together with the round info / other announcements on the home page. Probably a separate tab on the top or something would be nice.

Thoughts?

• +85

By farmersrice, history, 18 months ago, ,

I've noticed that sometimes heavily-downvoted comments will arbitrarily disappear. Some of them are extremely distasteful, but others just seem to be typical downvote material. And sometimes my child comments get upvotes/downvotes even though I can't see them anymore!

Don't know if it's automated system, manual removal, privacy feature, or something else (maybe even english/russian settings?)

Anyone know why this happens?

• +49

By farmersrice, history, 20 months ago, ,

I would like to shamelessly plug my good friend minimario's legendary soundcloud track "Starships"

https://soundcloud.com/alex-gu-254660687/starships

• +3

By farmersrice, history, 21 month(s) ago, ,

It seems that the equations and such are no longer italic. This is really bugging me. Is anyone else seeing the same thing? How can I turn it back?