farmersrice's blog

By farmersrice, history, 4 weeks ago, In English,

It costs 4.6 USD an hour to rent 48 cores / 96 threads on AWS. At this rate it will cost roughly 100 USD an hour to rent 1000 cores.

Assume we rent 1000 cores for 2 hours. Given that a very large contest has 20k users, this works out to 1000 * 2 * 60 / 20000 = 6 entire minutes of computation per user. 6 minutes is plenty of time to judge all a user's submissions.

If you are afraid of heavy load in the beginning and not at the end, you can of course alter distribution of cores for same cost (ex. 1200 cores in first hour, 800 cores in second hour).

CF receives 100k USD in the last donation round. This is enough to pay for the server costs of 500 rounds at 200 USD/round. Even assuming that only a tiny portion of funds is allocated to server costs, plenty of rounds can still be paid for without congestion.

It is also likely that these servers will be much more stable (I have heard a rumor that ITMO professor unplugged the power to the computers to spite some students and CF went down during that time, what if that happens in contest?)

It seems today's issues are not caused by server load but by some other bug, but of course there are plenty of times where the server gets overloaded and round is ruined.

Conclusion: 200 USD per contest for speedy speedy

EDIT: you could probably also mine monero or something while the servers are low-load to recoup some of the 200 USD.

Read more »

 
 
 
 
  • Vote: I like it
  • +305
  • Vote: I do not like it

By farmersrice, history, 5 months ago, In English,

Codeforces has tens of thousands of dollars in funding from the users and from telegram. Yet our forum avatars remain at 80 by 80 for commenting. They are literally 2 kilobytes in size. We see the same old grainy grainy pictures when we post. Anything other than an up-close face pic becomes a pixelated blob. It's so bad that it looks like how I see the world when I take off my glasses. CF has finally left beta, but it's left our forum avatars behind in the pre-alpha stage.

It's not 2010 anymore -- an upgrade is long due! I propose a new limit of 320 by 320. Given that CF servers can afford to give our programs 256 megabytes on the regular, sending a few 32 kilobyte pictures over the internet is no sweat. Imagine the sharpness! Looking at the comments to see your shiny new profile picture popping out in glorious clarity! This is what Codeforces should be like.

MikeMirzayanov, I think it's time to give Codeforces a long-deserved upgrade. (Plus, it would make you look even more handsome than you already are.) Let's make the greatest competitive programming site in the world even greater!

Read more »

 
 
 
 
  • Vote: I like it
  • +193
  • Vote: I do not like it

By farmersrice, history, 7 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +317
  • Vote: I do not like it

By farmersrice, history, 8 months ago, In English,

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!

Read more »

 
 
 
 
  • Vote: I like it
  • +73
  • Vote: I do not like it

By farmersrice, history, 8 months ago, In English,
 
 
 
 
  • Vote: I like it
  • +100
  • Vote: I do not like it

By farmersrice, 10 months ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +226
  • Vote: I do not like it

By farmersrice, history, 11 months ago, In English,

Because that's when they get AC.

Read more »

 
 
 
 
  • Vote: I like it
  • +301
  • Vote: I do not like it

By farmersrice, history, 12 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +34
  • Vote: I do not like it

By farmersrice, history, 12 months ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it

By farmersrice, history, 12 months ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +256
  • Vote: I do not like it

By farmersrice, history, 14 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +493
  • Vote: I do not like it

By farmersrice, history, 14 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +98
  • Vote: I do not like it

By farmersrice, history, 14 months ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

By farmersrice, history, 15 months ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • -25
  • Vote: I do not like it

By farmersrice, history, 19 months ago, In English,

Title.

Read more »

 
 
 
 
  • Vote: I like it
  • -34
  • Vote: I do not like it

By farmersrice, history, 20 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +108
  • Vote: I do not like it

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

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -24
  • Vote: I do not like it

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

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By farmersrice, history, 22 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -7
  • Vote: I do not like it

By farmersrice, history, 22 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By farmersrice, history, 22 months ago, In English,

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)

Read more »

 
 
 
 
  • Vote: I like it
  • +112
  • Vote: I do not like it

By farmersrice, history, 22 months ago, In English,

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).

What do I read? Where do I practice? Please let me know your recommendations, thanks.

Read more »

 
 
 
 
  • Vote: I like it
  • +29
  • Vote: I do not like it

By farmersrice, history, 23 months ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

By farmersrice, history, 2 years ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +85
  • Vote: I do not like it

By farmersrice, history, 2 years ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +49
  • Vote: I do not like it