farmersrice's blog

By farmersrice, 3 weeks 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, 5 weeks 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, 2 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, 2 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, 2 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, 4 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, 4 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, 5 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, 6 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, 9 months ago, In English,

Title.

Read more »

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

By farmersrice, history, 10 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, 11 months 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, 11 months 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, 12 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, 12 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, 12 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, 13 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, 14 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, 14 months 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, 14 months 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

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

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

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

Read more »

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

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

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?

Read more »

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

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

Just curious.

Read more »

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

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

Repeal the division cutoff change

Firstly, it causes rating inflation. In all div1 + div2 rounds the div2 players boost the div1 players, so even if someone does really badly relative to div1, he or she will get a much reduced loss, or even a positive rating change! In these div2 rounds there will be no reds/yellows to counter the buffer as well, so candidate masters will benefit even more!

Secondly, it does not solve the problem it seeks to address, rather it shifts it to higher rating ranges. Now instead of barely 1900s being unable to solve anything, we will have barely 2100 “masters” being unable to solve anything! We all know these titles are just for show, but this is a little ridiculous.

In addition, this shifting of the rating range also exaggerates existing problems. In rare occasions, even now, somebody will score 1st place in div2 and jump to master or high candidate master even if their skill level is low. With this change, we will have people jumping to grandmaster without even doing a single div1 contest!

With this change, ratings will become a joke. And that is why we need to repeal the division cutoff change.

Amendments to the creation of division 3

Thanks to ppavic's insight, I revised my statement on repealing the creation of div3. There still need to be some key changes, however:

The rounds should be limited to players with less than 1400 rating. 1600 is much too high if we are aiming to see the difference between beginner players who can solve only easy problems like A and B. If someone can solve A, B, C, then he/she should be in div2, as that is already solving 3 out of the 5 problems. In addition, we need a quota on the number of div3 contests in order to stop them from hampering the div2 or div1 contests, perhaps one per month.

Read more »

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

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

http://codeforces.com/contest/963/submission/37451734

Not sure where my code has a bug, but I submitted 3 times and it's always the same error on test 48.

I could not decipher this part of the message:

Diagnostics detected issues [cpp.clang++-diagnose]: =================================================================
==6068==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x14e00978 at pc 0x00dc63fd bp 0x1355f754 sp 0x1355f750
READ of size 4 at 0x14e00978 thread T0

I would appreciate any help. Thanks!

Read more »

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