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)
Be a problem setter please.
The meaning can be easily deduced by the context..
I completely agree. I got confused quite a lot when I first started CP ( and often get confused these days too. ).
What's the difference? I mean, for you as a contestant? What will change if you will always assume the second kind?
It is more difficult because you have to come up with an algorithm that works not for all inputs and hope that it covers all cases when the solution exists.
And in the first kind you have to come up with an algorithm that works for all inputs. How is that easier?
Maybe with problems requiring precomputation if some part of the range is invalid in case2 you don't need to precompute it or be careful of RTEs at least. Example: if answer is X / (N-100) if I'm bored enough to generate answer for all values of N in some range I'll face RTE for N = 100 although it's not part of the test cases. Sure it won't be as trivial but that's just an example!
I guess, having it explicitly stated as the first kind would allow you to use some other techniques without concern, like induction, for example. It also might make you think of more general approaches.
Finding that out yourself might be more or less the same in most cases, but you would be approaching this path with less certainty as opposed to knowing for sure that what you are trying to prove is in fact true.
I think the problem is that this formulation makes some contestants understand something, and other understand something else, and it comes as a risk/reward situation for the formers. However, this situation might a lot of the times come from the ambiguity in the statement, and is not a conscious choice of the contestants. Hence, the contestants might have to develop "novel reading" skills to figure out when it makes sense to consider the first meaning or the second, which is probably not the point of problem statements.
You can also assume that every solution you come up with is correct. Should I write "not every solution you come up with is correct" in the statement?
You are saying that sometimes you can make some assumptions based on wording (but not explicitly written in statement) and that can help. And also that can backfire. Yep, that's true for many things. You can submit any greedy without proof. Sometimes you will save time, sometimes you will get penalty (or even systest fail).
Or you can use failproof way and always assume second kind.
I think it's more up to debate than you suggest. When it comes to ambiguity for example, a lot of the people might assume a formulation to mean something, which might be different from person to person.
For example, if for me seeing "is guaranteed that" would mean that it's provably true. This means that trying to find out why is certainly not a dead path. If I'm not sure about that, I would approach this idea with more caution.
Moreover, sometimes maybe a "true proof" (by "true" I mean something that comes up naturally and incrementally through insights, and doesn't start by assuming that it's true and doing some induction) is really hard, and maybe knowing that something is true makes it easier for you mentally grasp on proving that it is true than considering that it might be true.
All in all, I think the biggest problem is that when people see a textual pattern, they are inclined to consider its meaning from past experiences. That's why I think that explicitly stating what a "subsequence" means and explicitly stating what "it's guaranteed" means for the context of the problem is something to be encouraged at all times, if it's not 100% clear for people. And that's probably why, if I were to organize a contest, I would probably resolve ambiguities when people are confused about statements, instead of giving the frustrating "no comment" answers.
After all, in my opinion, people should focus on solving problems, not endlessly read statements until they find the tiny sentence that makes them realize that they might have understood the problem wrong.
Everything written in natural language can be understood in different ways by different people. This is why we are trying to come to some widely accepted terms (such as subsequence) so that most of the people will understood it in the same way.
And it doesn't work because of people like you who believe that problemsetter should think for all participants, and problemsetter's time worth zero.
I believe that writing a clarification as a participant is the last resort. It should be done only if you reread the statement at least a couple of times and you strongly believe that there is a mistake or two equally possible interpretations and the answer to you clarification is important for all people trying to solve the problem and the answer to your question cannot be (in reasonable time) deduced from samples and notes (or, generally, whole statement).
This is even more true for contests with tens of thousands participants.
For example, I have seen several clars along the lines "there are two possible interpretations and for the first one samples are wrong". Then you can deduce that the second one is the right one!
Also for Codeforces where we have coordinators who proofread the statements: please assumed that statements are at least logically correct.
Sure, but why write a statement that can be interpreted in two different ways if we can just as easily write it so that the contestant understands what we mean immediately? It wastes contestant's time trying to figure out the meaning and your time answering stupid clarification requests.
I'm recommending we stop 'guaranteeing' things that are always true and instead say 'it can be proven'.
No we can't. I assure you we can't write the statement in a way that everyone will understand it the same way. Even if we'll use just mathematical notation someone still will understand it somehow differently.
There are no fixed rules for problemsetters and there won't be as long as we continue to use natural language to write the statements. I agree with you that it is better to use words in some fixed sense. But it doesn't mean that they won't still have all the senses people want.
I think that I have never used the word "guaranteed" in the first kind from your post, but I cannot be sure. We still need some way to provide guarantees of the second kind and all of them could be understand as guarantees of the first kind by someone. You could argue that your phrases are better suited for the job but it is just your views on language. For me the word "guaranteed" works in the second kind as well as your phrases.
Slightly related: Some time before I thought about setting the contest with checkers and validators instead of natural language statements. This should resolve the language ambiguity problem, right?
lol I hope you are trolling with that last comment. I certainly prefer clear English statements to code that validates the input. The second would be way too difficult for new contestants to understand.
Just to be clear, this isn't a criticism of your problems or you or anything. The reason I satirically mentioned you in the post was that I don't like the attitude of "contestants are stupid and ask dumb questions so we shouldn't try to write better problems" instead of thinking of writing problems as an exercise in both the contestant and writer are on the same side trying to get the contestant to understand what the writer means.
I think if we are more careful with our guarantees (outside of the obvious
it is an tree/permutation/connected graphwe can make maybe not everyone, but a lot of people like me who put in a good faith effort into reading the problem understand it more easily.You think that you are a savior who knows what is best for all. Well, you are not. The things you want may be better for you and worse for other people. Don't accuse problemsetters of making their job wrong, they try their best for your pleasure.
Also, it might mean that the samples are screwed up or old version of statements was accidentally posted. It is OK to be wary of things that look broken.
Let's just all always write clarification "isn't everything broken?" in the start of the contest. That would be great.
Yeah, well, except for the fact that a very sound translation into romanian of "subsequence" would be "subsecventa", which is the "argotic word" for "(contiguous) subsegment" (in a romanian task, whenever you hear of "subsecventa" you should automatically think of "subsegment", if you're worth anything in the CP community, supposedly).
I think it's bad and frustrating for romanian tasks to not clarify the notion of "subsecventa" in the same way as I think it's bad for english tasks to not clarify "subsequence".
Maybe some feel that deciphering the statement meaning should be part of solving the task, but I think encoding implicit meaning in some "inside phrases" is not the right way to do it.
Here's a clear example of where it matters:
Imagine a much harder version of this problem. If you submit and get WA for some reason and now want to generate test data for yourself, you don't know if you can just pick random numbers or if you have to do something more clever. In hindsight the author intended the second meaning; I think we can remove this confusion in particular with more careful wording.
It wasn't a "hindsight", author wrote "it is guaranteed" which is a clear indication of the second meaning. Wow, I can ignore everything you say and see it my way too, who would have guessed.
Author should have write "input is only allowed if the answer exist"? So you are saying that answer exists for all inputs within limitations, right?
Of course I unterstood what you wanted to say. And of course there will be people who won't.
It is not as easy as you think to write a statement that everyone will understand the intended way. It is only easy to write a statement that you will understand the intended way. Of course you think that means that everyone will understand it the intended way, but that's not true, sorry. I assure you that all the problemsetters write the statement that they will understand it the intended way.
If your problem contains an important constraint, clarify that it's an important constraint. Meaning #1 is just "no need to overthink this". If you just treat problemsetting like "whatever, learn to read statements", you end up with shit statements.
There's also a 3rd meaning where it's a constraint on the input, but not very important, like "you don't need to check if a solution exists". That's why I view it as making the key parts of the problem stand out, not different phrasing for different formal things. Just that if you have some generally unsolvable problem + special condition, make sure it's not lost in the text.
All constraints are important.
It's not "whatever, learn to read statements", it's "I did the best I could, now it's your fucking term".
"term" — you mean "turn"?
Yeah, sorry, autocomplete. I guess that's how I write statements.
Your apology message has 24 upvotes which shows how much people loves you and supports you but most of your replies are still downvoted here, which is sufficient to show how wrong you are on your point
I am obviously joking. It's not an apology. I have nothing to apologize for (in this conversation). Fuck off.
And yes, people may see my points as wrong. That doesn't mean I will stop defending them.
Yes I agree with you , but I used so humble words and you replied so rudely to me. Don't you think you could have conveyed your message without using that last two magical words. Sometime it may hurt someone as you are inspiration for many and such reply from your inspiration is the most demotivating thing.
I am talking about your previous reply
https://codeforces.net/blog/entry/77574?#comment-626518
I totally agree that authors should pay more attention to this wording than they do now. However, I don't agree that we shouldn't use the word "guarantee" at all. If authors guarantee something in the input section of the statement, then they add some constraints on the input. For other meanings, other words should be used. Some time ago I included the following phrases to the list I used to give to authors on Codeforces (and I hope they still receive it):
It is guaranteed that...It means that the input is specially prepared so that the condition holds. This should be put in the legend and input section. Example:It is guaranteed that the given edges form a tree.We can show that an answer always exists.This phrase should be put in legend/output and means that for every possible input an answer exists. No additional constraints are added here.Definitely guaranteeing that the input is a tree/permutation/sorted array is still okay; everyone knows what the author means there. Specifically, I think we should stop 'guaranteeing' things where:
that thing is always true (just say 'we can show that an answer always exists'/'it can be shown' or something similar so we know what you mean)
or our guarantee is made outside of the input section and/or introduces a non-obvious constraint on input, like in this problem. For instance, if you just read this problem and imagine you aren't smart, it is very difficult to tell what n is legal input.
I agree it would be nice if we could just agree that all guarantees would be constraining/of meaning 2. Then it would be unambiguous. The problem is that now that we have started guaranteeing tautologies, you can't be sure if the author was careful in his word choice and it really is a constraint, or if he just hasn't read this post.
EXACTLY this thing happened again in problem F of the div2 today!
In the output section, it says:
(it is guaranteed that in this case there is such a sequence of actions). In my opinion a much better wording would be 'we can show that in this case there always exists such a sequence of actions'.Just to be sure on your point. Let's say that instead of guaranteeing provability, they asked to print
NOT SO SMALLif there is no sequence of action with length $$$m \le 500\,000$$$. For this specific problem it looks like a bad idea, but do you intent to claim this is bad in general?I think it could be good to do something like that for other problems. Like you said, this problem already had a lot of cases, so I don't think it would be good for this particular example. But in general, I think that saying something like 'print
NOT SO SMALLif there is no sequence with $$$m \leq 500\ 000$$$' is another good alternative to a guarantee.It is clear that it is up to the contestant to determine whether it will ever happen. If instead you want to assure contestants that it won't happen, say something like "we can prove that there always exists a sequence ...". I'm just saying that 'guarantees' are bad because they can mean two different things.
Yeah, I think sometimes problemsetter may want to guarantee something for the problem's input data, but not really prove it is always possible (even it is). I was wondering if you object on that kind of thing. If the objection is strictly about the wording, I agree that it should be improved too.
Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).
vovuh I strongly believe we should stop guaranteeing tautologies and say "It can be proven" instead of "It is guaranteed" for things that are always true under the stated bounds.
I think, it is fine in this problem. If it's about $$$n=2^k$$$ then how can it be proven that $$$n=2^k$$$? It cannot be, we just guarantee that the input fits this condition. Maybe you're about "it is guaranteed that the answer exists" but meh, this is just my old habit because sometimes I saw a lot of clarifications like "is the answer exist???" and just taught myself to write something like this in the statement to prevent this.
Yeah, I think he means that he prefers to write "it can be proven that the answer always exists".
I'd like to see "It can be proven that for all legal inputs an answer exists", which is true. It seems confusing to me because it might not be obvious to some people that if $$$n=2^k$$$ that means it is possible, so it might appear that this line is adding an additional constraint on the input, which it isn't actually doing.
I'll consider this improvement (and will try to get rid of this habit) in upcoming rounds, thanks :)