Please Stop Guaranteeing Things
There are two common meanings for something being “guaranteed”, and often it is up to the reader to guess the author’s intended meaning. This is annoying and creates unnecessary barriers to entry.
Meaning #1: The thing we are guaranteeing is provably true for the given input. The thing we are guaranteeing is simply true. We don’t want to provide a proof since it would be long, unnecessary, and annoying to read, and might spoil the solution, but you have our word that an answer always exists.
Example: We give you two positive integers A and B (1 <= A, B <= 100). Find some positive integer C (1 <= C <= 200) such that C < A + B. It is guaranteed that some C exists.
Meaning #2: The only input that is legal is input for which this is true. The thing we are guaranteeing might not always be true without this guarantee. Thankfully, we are providing this guarantee so that you only need to concern yourself with solving the problem for inputs in which this is true.
Example: We give you two integers A and B (1<=A, B <= 100). Find some integer C such that (A-C) * (B-C) is negative. It is guaranteed that some C exists.
Examples in real problems:
Examples where 'guarenteed' means that “It can be proven that for all inputs following the constraints, X”
Code Jam 2020 Round 1A, problem B
Codeforces round 633 Div1B (it's clear what the author meant, but still this type of usage)
Examples meaning “The only inputs that are valid inputs are inputs for which X”:
Code Jam 2020 Round 2, problem B (An incorrect interpretation of this could have resulted in failing the large test set)
There are tons of guarantees in the input section for things like: all edges are distinct, the graph is a tree, the array is a permutation, the sum of array sizes across all test cases is reasonable, the total number of queries is reasonable, the input is sorted, et cetera. I didn’t include them because it is clear what they mean. The important part is that this is a completely different type of ‘guarantee’ from the first one. We shouldn't be making contestants figure out what the author means; people want to solve interesting problems, not read novels.
Alternatives:
Meaning 1: Make it clear that the ‘guarantee’ is just to make the problem more understandable, not an additional constraint on input.
“It can be proven that X”/“Under the given constraints, X is always true”
“Notice that some X always exists”.
In the example above: “It can be shown that some C always exists.”
Meaning 2: Make it clear that this ‘guarantee’ is an additional constraint on the input.
Input is only allowed if X.
In the example above: “Only input for which some C exists is legal input.”
Just don’t provide the ‘guarantee’ at all and make it a red herring
“If no solution exists, print -1”
In the examples above: “If there is no suitable integer C in the valid range, print ‘no’ instead”
Counter Arguments:
"Red herrings don’t work. 99% of the time if there isn’t an impossible case in samples, and the impossible case isn’t super obvious like n=1, then an impossible case just doesn’t exist.”
That’s probably true. One option is to have really weak samples to disguise that, but maybe that is undesirable for other reasons. A second option is to write more problems where there is a nontrivial impossible case, but not put it in samples so people stop thinking this way (definitely keep it in pretests though!). Even without either of these things, there are still some quite nice problems with red herrings for which the contestant proving that it is always possible is helpful. Perhaps you can make the guess that it is always possible and have a slight advantage, but finding why it is always possible is usually a nice head start on the problem too. 2019 China Collegiate Programming Contest Final Problem I is a great example of this. A red herring doesn’t have to trip people up to ‘work’ either; if it makes it clear that it is your job to figure out whether something might happen, that’s okay too.
"You just suck at reading problems. Use samples. Reread the statement. This is a skill, you have to improve it.”
Okay, Um_nik, you got me.
Update: Examples of how to do it the right way:
Problem G from Educational Round 89 is a model solution to this issue. It does an fantastic job of entirely avoiding all ambiguity and confusing guarantees. It is crystal clear that the additional constraint is an additional constraint, and it is worded in a succinct, easy to interpret way. Problem authors/coordinators orz
(My reaction to first reading this problem at 54:13 is pretty funny and might cheer you up if you wrote the problem)
