ACGN's blog

By ACGN, history, 5 days ago, In English

Author of the problem 2031C - Penchick and BBQ Buns here, hope you enjoyed the contest yesterday (Almost exactly 24 hours ago...)!

Looking at the votes on the editorial, it's obvious that it's a very polarizing problem: an hour or so after the contest, the problem had roughly equal numbers of "likes" and "dislikes", and now (as of writing) there are around 320 likes to 200 dislikes. Of course, this is completely predictable: the opinions on this problem were quite polarized for a few reasons:

  1. Troll and WA trap: it's very easy to fall into the trap of thinking that there is no solution for all odd $$$n$$$; thus, over 12,900 (!) WA on pretest 2 solutions were received, as compared to only 4,700ish Accepted solutions. This ratio seems a bit extreme for a problem C; in the previous Div.2's problem C (2028C - Alice's Adventures in Cutting Cake), there were 3,500ish Rejected solutions to 2,500ish Accepted ones.
  2. The construction: hard-coding the case $$$n=27$$$ seems weird and mundane, and with such a "big" base case, it may be annoying (and ugly) to figure out. Some testers said they were "disappointed" by the solution.
  3. In general, constructive math problems are going to attract two-sided opinions: people who solve it would love it and find it cute, people who don't solve it would be upset. This is especially true for a problem C, as most people can solve A, B and few people can solve E, F, and thus C and D are the biggest "choke points".

With these negative opinions, including during testing, why was this problem still adopted?

  1. There was no compelling reason to do so; a good number of testers liked it, and in general it received decent reviews across the community.
  2. There was no good alternative problem, especially as the problemset had already been changed once (see the editorial).
  3. I think a round with only conventional problems would be boring, and had always enjoyed constructive problems, and of course would love to share the problem with every one of you!

This problem reminds me of another "troll", controversial C: IMO 2024 C4, adopted as Problem 5 on the contest, otherwise known as the infamous Turbo problem. Without spoiling too much, there are some funny similarities:

  1. Both are constructives; the IMO problem could quite reasonably be translated to a ~2500 rated interactive problem on Codeforces.
  2. Both have quite unexpected solutions that many people do not expect, which contributes to its troll-ness. Once again, no spoiling the solution here!
  3. Both were proposed by a Hongkonger!
  4. Both received very polarized opinions. During the IMO, many participants, especially from stronger teams, resented it; many relatively strong teams scored poorly on it compared to a typical problem 5. I remember reading on AOPS all the negative comments regarding this problem; this is to be expected, given that some people may have trained for an entire year, risen above their peers, only to be hit with such a problem 5 and lose out on a good score and a medal?

But this is a core part of the competition process; you're gonna get trolled.

Me, my team and Problem 5

What makes the comparison between the two problems even funnier is that they are "opposites" in some way:

  1. The IMO problem was tricky in that its solution was simpler than expected, while this problem was more complicated than expected, with the $$$n\ge 27$$$ case coming as a "surprise";
  2. On the IMO, teams from stronger countries tended to hate the problem more, while here on Codeforces, our C seems more popular among the unrated contestants than the rated ones.

During problemsetting, I immediately associated this problem with Turbo, and felt that this would be an immensely fun and funny problem; this is the biggest reason for keeping it. And I hope you all had fun being trolled!

Some challenges?

A comment yesterday triggered my thoughts on variants of the problem. One of which is as follows.

Squares except 1

If $$$1$$$ is not allowed as a valid distance, what would the constructions be? For which $$$n$$$ is the problem no longer possible?

Solution

Minimum number of flavors needed

In the original problem, we did not limit the number of flavors. What if we want to minimize the number of flavors $$$F(n)$$$ chosen? Specifically, how well can we bound the growth of $$$F(n)$$$?

We introduce the shorthand $$$C_x(k)$$$ to mean the construction for the case $$$n=k$$$ using the method in level $$$x$$$, with $$$x=0$$$ being the base level (i.e. the original solution). The trivial estimate is $$$F(n)\le \frac{n}{2}$$$, based on our existing solutions.

Think about the problem for a bit!

Improvements

Once again, hope you enjoyed our contest yesterday!

Full text and comments »

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

By ACGN, history, 6 days ago, In English
A little backstory about the round (ACGN)

2031A - Penchick and Modern Monument

Idea: pwned
Preparation: HappyPacMan

Hint 1
Hint 2
Solution
Feedback

2031B - Penchick and Satay Sticks

Idea: ACGN
Preparation: HappyPacMan

Hint 1
Hint 2
Solution
Feedback

2031C - Penchick and BBQ Buns

Idea & preparation: ACGN

Hint 1
Hint 2
Solution
Feedback

2031D - Penchick and Desert Rabbit

Idea: AverageDiv1Enjoyer
Preparation: HappyPacMan

Hint 1
Hint 2
Solution
Feedback

2031E - Penchick and Chloe's Trees

Idea & preparation: ACGN

Hint 1
Hint 2
Solution
About Problem E
Feedback

2031F - Penchick and Even Medians

Idea: trunkty
Solution & preparation: maomao90

Hint 1
Hint 2
Solution 1
Solution 2
Solution 3
Challenge
Feedback

Round statistics

Fastest submission among all participants, and among rated participants:
A: tourist at 00:00:43, priyanshu.p at 00:00:56
B: tourist at 00:01:57, arnabmanna at 00:02:10
C: arvindf232 at 00:06:22, boboquack at 00:11:42
D: _Duck_Dot_Dot_Happy at 00:10:50
E: fzx at 00:11:27, Jack.YT at 00:20:38
F: peti1234 at 00:34:01, waiting_for_the_sunset at 00:54:34

More round statistics to be updated!

That's it for this round, and we hope you had fun with all the problems!

A few serious words from ACGN - about problemsetting, MathForces, and more
and from my own heart...

Full text and comments »

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

By ACGN, history, 19 months ago, In English

Hi! I got a message stating that "Your solution 123456789 for the problem 9999H significantly coincides with solutions tourist/987654321, jiangly/987654322."

Anyone who has looked that that one blog has seen numerous comments like this. Obviously, except for a few cases, no change has been carried out.

Of course, sometimes you didn't cheat, and you followed all the regulations. False positives happen.

Here are some things that you shouldn't (and should) say in order to make a genuine request for Mike to review your case.

1. do NOT over-emphasise your rating.

"pls pls pls give my rating back (emoji) i need it i was so close to expert"

First of all, it feels fake.

Besides, obsessing over rating is a common trait of cheaters — if you aren't cheating, you can get the rating back in a few rounds anyways. What's the worst that could happen? You could get back anyways, if you aren't cheating.

2. do NOT say "I didn't mean it, it must have been accientally leaked blah blah blah"

It is your responsibility to safeguard your code — and prevent cheating. If you code your solutions and don't prevent others from copying, you are guilty as well. This applies also to ideone issues. Read carefully, and avoid it next time.

3. do NOT say "this will never happen in future please give my rating back blah blah blah"

A murderer goes to court, sobs and says that this will never happen again, blah blah blah. Does this change anything? No, the murderer is still behind bars for their remaining lifetime.

You are no different. You still have to take responsibility. So take it.

4. DO give concrete sources or links if you want your review to be considered.

Mike will NOT take the time to plough through the Internet. Make his life easier, and he'll make yours easier.

e.g. DO — "the common source is [insert public link, or anything that decisively proves your innocence]"

DON'T — "we both copied segment tree template" with zero info

5. do NOT nudge Mike.

"MikeMirzayanov It has been a month without update. Do you plan to address it?"

No, he doesn't. He does look at the blog and review cases; if he didn't take action, forget it.


Overall, be nice. Don't be annoying about it, and leave a good impression.

Final thing: your history has a great impact on your CP career. If you cheated once, your credibility plummets. So stay away from cheating, and have a good day

Full text and comments »

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

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

As most people know, in yesterday’s round Codeforces Round 852 (Div. 2), problem F coincided with a previous problem on Codeforces. A few months ago, a similar thing happened to Codeforces Round 810 (Div. 1), which also had an issue of coincided problems.

Of course, we know what happened next: Codeforces Round 810 (Div. 1) was unrated for div.1, while as it stands, this round will be rated as per Mike’s latest blog post. I won’t elaborate more on that blog post; I assume you are familiar with Mike’s rationale.

I mulled over that decision for a while, and I’d like to raise a few points.

Full text and comments »

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

By ACGN, history, 2 years ago, In English

Every time after a contest, the Codeforces blog Rule about third-party code is changing is flooded with comments asking for Mike to review submissions, some of which are because of people sharing the same template and are otherwise distinct.

There is a solution that can handle these claims: ask users to submit a template before the contest, possibly as part of the settings, and can come in the form of a CF submission (so they can just input a submission ID). During the contest, they cannot edit the template, and similarities solely because of the template will not be considered when determining plagiarism.

I'm not familiar with how the plagcheck system works, but I'd like to ask for your opinions: is this feasible, and is this a good idea?

Full text and comments »

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

By ACGN, history, 3 years ago, In English

In Codeforces, there are all sorts of intelligent minds: mathematical, algorithmic, and creative minds all come together under one website to create a beautiful platform.

Hold up, there’s still something missing, a gap that, if filled, would make the platform truly marvelous.

Literature.

Most of the code on this platform is robust and correct. But they aren’t beautiful. #define mp make_pair? What even is "mp"? This is almost sacrilegious.

They don’t add to the literary beauty of this otherwise great platform.

#defines aren’t meant to be used this way. Nor are they meant to encode cryptic text like this submission.

The purpose of #defines are to make Codeforces show its literary beauty, the beauty otherwise obscured by confusing syntax.

This is a beautiful excerpt of Shakespeare. Looking at the actual text is pure eye-candy.

This is what #defines are for. Not to make confusing code even more confusing, but to make beautiful code even more beautiful.

From now on, keep this inner beauty of CP in mind; when solving problems, try to let out your inner literary mind, and quote from the literary giants.

To beauty or not to beauty, that is the question problem.

Full text and comments »

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

By ACGN, 3 years ago, In English

DISCLAIMER: NO TOURISTS AND RAINBOYS WERE PINGED

Ah yes, two names that most people on Codeforces have heard -- tourist and rainboy, one known as the CP Legend, and one as the user who does everything reverse. Such a great idea to put them together — a hypothetical user with the same ability as tourist, and solves problems the rainboy way.

For those unaware of the "rainboy way", it means solving the problems in reverse order. In particular, if he cannot solve the final problem, he solves no problems in the contest.

Unfortunately, rainboy had not yet reached red, peaking at 2398 rating. How far can this user go? We shall simulate this user through all the contests that tourist and rainboy took part in comparably, which adds up to 60 contests from Codeforces Round 385 (Div. 2) to Codeforces Global Round 19 over a span of 5 years. Drop a guess before reading the rest?

  • he will be unable to reach red
  • he will peak at GM (2400-2599)
  • he will peak at IGM (2600-2999)
  • he will peak at LGM (3000+)

Pre-discussion

In the simulation, I used Codeforces Visualizer to get our expected rating changes. Credits to the website.

One important thing to note is that an AK still stays an AK, but even if he solves one less problem, that could mean a score of 0 for our challenger. If he succeeds in AKing, he would almost certainly get a top 10 finish. Supposing that one starts at a rating of 2200, then a 10th place finish would give at least 200+ delta, and a top 3 finish could easily be 300+ delta.

On the other hand, tourist failing to AK a round would almost certainly lead to a 0 score and a huge negative delta. Assuming that one starts with 2400 rating, how negative the delta is depends on the type of round -- from around 100 for div. 1 rounds to 300 for combined and global rounds. In combined and global rounds, it is often difficult to AK, and such a fall would be easily felt.


All journeys must begin with a good username: how about a touring boy? "touringboy" -- no, "turingboy" to make it more programming style :)

With this set, let the journey/simulation begin, and may we wish turingboy high ratings.

First contest: Codeforces Round 385 (Div. 2)

Fortunately, tourist managed to solve problems A to C in the div. 1 version, and in this scenario, he would be able to AK this Div. 2 contest with ease.

However, the next context demonstrates how dangerous failing to solve a single problem is:

In Good Bye 2016, tourist did not manage to solve problem H. Unfortunately, that means turingboy won't be getting any points, and a rating drop of -173 follows.

Then our turingboy AKs, 4 times in a row.

Note: for Codecraft-17 and Codeforces Round 391 (Div. 1 + Div. 2, combined), tourist/turingboy got a FST.

Will he be able to reach the LGM mark? The answer is shown below!

turingboy's rating trends

Did you get it right? What do you think?

It is undeniable that rainboy is a skilled programmer deserving of LGM range. But tourist is simply different, otherworldly.

Did you like this "simulation"? If you did, please support this blog post to continue this series :)

Full text and comments »

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