Please subscribe to the official Codeforces channel in Telegram via the link ×

l_WhiteEagle_l's blog

By l_WhiteEagle_l, history, 13 months ago, In English

I have some reasons for that, if you have any doubts please comment below.

Firstly, you can't be sure whether your current solution is correct or not. I mean, how can you know if a solution with AC probability of 0.12345.... is going to pass? How to know if that's the intended solution? And even after getting AC you'd still be worried that your solution might get FST, and the probability was not the "intended" one.

Secondly, it does not measure the skill of an individual properly. For example, a middle rated participant (CM, Expert) would like to make the probability of AC as high as possible(to avoid FST), they might think that current probability is not high enough. So they spend more time looking for better one. While some low rated participant(pupil, specialist), wouldn't care about probability that much, because they don't have much rating to lose if it FSTs. They could write some solution which "somehow" gets AC, while that middle rated is still looking for better probability. Note, that I'm not talking about high rated people(Master, GM, etc...), I mentioned middle and low rated ones only.

What's your opinion about this? Comment below

And please don't be ratist, this is my secondary account.

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

| Write comment?
13 months ago, # |
  Vote: I like it +8 Vote: I do not like it

A problem where the probability of an expected solution passing is about $$$0.12345$$$ is definitely not a good one. But probability-based problems are not like that. The probabilities that the authors consider are much closer to $$$1$$$, most of the time the model solution has no more than $$$10^{-6}$$$ chance of failing; sometimes even better than that. For example, in yesterday's problem D, I am pretty sure that any reasonable implementation can process at least $$$100$$$ different prefixes of $$$s$$$ as the candidates for the answer. So, the probability of the model solution (and any its implementation) failing is about $$$2^{-100}$$$. Do we seriously need to consider this?

13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

AC probability of 0.12345....

This kind of probability is not meant to pass, nor have I seen any problem in CF where such a probability is expected to pass. You're trying to give an extreme example, but the exaggeration itself is what completely misses the point. The actual problem I suspect you're grumbling about (1743D - Problem with Random Tests) is one where the chances of TLE are so minuscule that nobody skilled in probability analysis should be concerned about it. If the randomness made somebody hesitate, then it simply implies that this person was not skilled or familiar enough with probability to handle this problem smoothly.

I think the problem here is that you're treating probability as some completely separate issue from the diverse array of topics that are covered in CP. Struggling with probability-based problems is not very different from say, struggling with DFS problems because you're not good at DFS. Dealing with probability is one of many different skills that one can learn and master in CP.

If anything, one notable difference is that these kinds of problem require you to utilize your knowledge in a more practical sense: there is quite a difference between writing a program to solve a problem that asks about probabilities of some given scenario that is being described and writing a program where you yourself are actually experiencing the scenario of dealing with probabilistic factors. The latter is imo more immersive to the CP experience, since it's a challenge that the programmer is directly facing and addressing.

This additional dimension is also very important for practical applications, because actual programming challenges in the real world would often deal with randomness or have opportunities to exploit random distributions.

So yes, I think it does measure the skill of the participants, just not in the way that you would usually expect from how skills in other topics are measured, but it's still nonetheless a skill that is just as relevant and important to the spirit of CP as these other skills, if not more.

A "middle rated participant" (as you call them) should try to gain many of these different skills. The example of a "low-rated participant" solving it while a "middle-rated participant" hesitates has nothing to do with the probabilistic nature: it's simply a scenario where the correctness of a relatively simple solution is not trivial to determine. For example, there are many problems where it's tricky to realize that a greedy approach works, but low-rated participants might solve it greedily without thinking if it works while higher-rated participants hesitate. Or problems where brute-force won't TLE but it requires some skill to realize why that's the case. This is not inherently a problem, especially with how rare they are, so low-rated participants that naively attempting problems without thinking about whether their approach should work would not actually get very far.