- Disclaimer : This article was originally written by zigui. I'm just translating original Korean article in English, but still, I totally agree with this article.
In 2017 IOI Day 1, there was one output-only task, "nowruz". When I first saw this problem in GA meeting, I couldn't see the input file (which I think is very important in output-only problem). I expected there will be various type of inputs, such as totally empty, almost empty, almost full, and so on. I could look at I/O dataset when the problem was revealed, and it was out of my expectation. Almost all of input cases are almost empty. It means that there was an important condition about input data, which was not mentioned in the problem description.
Score distributions of contestants in "nowruz" problem were very strange. It had no correlation with contestants' skill, previous records, other problems' score, or anything else. Students who got low score in this task said: "I thought about heuristic solution (which turned out to give 80+ partial score), but I thought that solution will give me low score." Actually, tudent with good mathematical intuition will never think that this "heuristic" solution whill give good score in general situation. So they didn't try, and got a low score. Definitely, it will not be an easy task building an algorithm performs well in general cases.
I think that output-only tasks are not appropriate problems for IOI. There are some reasons about it. First, output-only problems have little logical steps to solve tasks, and it's contradictive to IOI's goal, evaluating students' logical thinking ability. For example, I'll show you two easy problems:
- What is zigui 's Codeforces rating? 1) 1234 2) 2345 3) 2456 4) 2486
- 1 + 2 = ? 1) 1 2) 2 3) 3 4) 4
In first problem, there is no clue to solve this problem. If you don't know about zigui (maybe true, right?), it's all about 25% probability. In second problem, everybody knows that answer is 3).
These two problems all have one description and four possible answers, but they are very different in difficulty. The reason is simple. Second problem has logical steps to solve, but first one doesn't. Everyone knows that 1 + 2 = 3. It's well-known, can be proved, and based on mathematical knowledge that everybody knows. In first problem, no one will memorize about zigui 's rating, and it's impossible to get the answer through logical steps.
Although it's a bit exaggerated, I believe that output-only problems are not quite different from this case. You have to "find out" some important conditions. They are not in description, just in input files. There would be more conditions or not, but if you can find it, you will get high score. In solving problem, no mathematical proofs are required. To be even worse, it's better to not prove it, if you want to perform well in contest!
In case of "nowruz", there were no special description about limitation about K. It just said "at least one possible solution exists." There are no additional talk about conditions. For example, all input datas were composed of only one connected component, which was not the case in sample input. If you are writing papers about heuristic algorithms, you have to be very careful in time-complexity proof. You have to "prove" that this heuristic algorithms give almost correct result in almost every cases. But in "nowruz", it needed no mathematical analysis, because there were actually no conditions. Analyze what?
Second problem of output-only tasks is that the only way to solve task is trial-and-error. In science, logical steps are very important issue. It's not a science to just show how to do it, and prove by results. In output-only problems you can't find out the results before you actually code it, and it's very hard to mathematically prove it. This means contestants should "gamble" with their solutions, whether it will get a high score or not.
2013 IOI's "artclass" problem will be a good example. If you don't try, you can't predict results. (Translator notes: Art class is task like this, "Get an painting as input file, and find out what's the style of this painting, between modern art, landscapes, expressionist action paintings, and colour field paintings." This problem had a lot of issues back then, and current IOI syllabus explicitly exclude this kind of problems. you can see problem in this link : http://www.ioi2013.org/wp-content/uploads/tasks/day1/artclass/artclass.pdf) There was an 100 point solution which only uses G values (among RGB values). If you say to artists "This painting has less green color, so it seems like modern art!", they will think you an idiot. But if you are in output-only problems, it's perfectly fine idea. If you try it, you can get a score, even though it's correct solution or not.
I think "nowruz" is also the same case. It seems that they wanted many high scores (possibly 100+ contestants), but in contestants' view, it's impossible to try every possible ideas in their head and get a high score in 5 hours. If then, it's only about who tried, and who didn't.
Because of these reasons, I think that output-only tasks like "nowruz" don't fit in IOI at all. If they want to give these kind of tasks, include heuristic algorithms in IOI syllabus, write every information about input tasks in description, and give some good input restrictions, which can make problem "solvable". Solution itself also should be clear, can be solved by clear logical steps. If they can't do these, it's better giving this problem to some other competitions. At least, it's not a science at all.
