I read the IOI 2018 competition rules, and noticed this addition to the rules of the previous year:
"Also, contestants can use the grading system to view the statistics on contestants’ scores for the competition tasks. For each task, a percentage of the total score among all contestants for this task, divided by the total score among all contestants for all tasks, will be shown."
-- IOI 2018 Competition Rules
What do you think: would it be a good or bad thing if this passed the GA vote? Do you have good arguments for or against this rule change?
We were surveyed last year regarding this. I'm soooo grateful they've decided to pass it. As long as you only see stats, there's no way to assess your position so you shouldn't be psychologically affected by it. On the other hand, this way, the strategy one contestant chooses to pursue does no longer influence the final outcome to the same extent. That is, now the IOI is more about informatics and less about strategy (the only reason for which I know the rankings are not public is the above-mentioned one — that knowing your position after say one hour may be harmful to your performance). Best example is last year's nowruz, that maaaany contestants (including several who got gold) thought would be the hardest and started to solve the others, whereas if they knew that nowruz had maaaany scores of ~80, they would've given it more thought/time (in the current case one only needed to want to invest the time of coding a bfs in the hope of getting that 80).
Yeah, I think the only way you could be psychologically affected by it is if you are unable to get many points on the easier task, in which case you might stress. Even so, I think its a good idea and I'm interested to see what it will be like in contest. I wonder if it will lead to overall better results or not (although it is unlikely we will be able to determine that).
Well yeah but if you don't get points on the easy one there are 2 cases:
you don't get points on any of them -> you're stressed
you get points on another one -> you're stressed but also helped cause you know which one to target (and it's not that bad to know you've solved the average and you're left with the easy, it can actually boost your confidence)
It's definitely going to be different and they are also probably interested in how's this change going to work. Let's hope it's just gonna be better for everyone.
I believe that with regards to classical tasks, the ability to estimate the difficulty of a problem is something reasonable to demand from a contestant. I consider it a part of the solution, not strategy.
On the other hand, the output only tasks are highly different. First, your score depends on the details of the testcases nature, which is maybe something you can check, but it is like saying "here is half of the statement, please decipher the other half". Second, your relative score depends on what different approaches exist. In a classical task, you don't even have to write code to know what score a certain approach should get. In output-only, even if you prove that for instance your approach is 2-approximation (and this is rarely possible), you can't know how much it's worth and how much can others get. Therefore deciding its difficulty is not even a strategy, it's a guess. Here, seeing statistics is something that reduces the uncertainity.
With these in mind, I'd rather see no output-only and no statistics. But if the output-only kind of tasks is to remain, the statistics addition is a good thing.
"I believe that with regards to classical tasks, the ability to estimate the difficulty of a problem is something reasonable to demand from a contestant. I consider it a part of the solution, not strategy."
Well it depends. First, if assessing the difficulty of a problem is part of the solution, doesn't that mean that the only way for somebody to find out which problem is harder is by actually solving them both? In my opinion, it's a matter of intuition/approximation to see how hard a problem is. The only way you could get some relevant information about it is by either solving it or (and this is rarely possible) proving its equivalence to some other problem whose difficulty you know. I think that in most cases one's correct assessment of a problem's difficulty (when the assessment is made prior to solving that problem) is a simple guess. Guess = intuition + luck, one thing that is debatable good or bad and one that is definitely bad.
On the other hand, I totally agree with your second point related to output only tasks/
I think you either have some experience, or need to rely on intuition.
I only now noticed that what I wrote applies more to who wins/gets gold than the whole spectrum of contestants. In that range, yeah, I assume that any contestant has at least some idea on how to solve every task, or they are aware of a limitation* that stops them, and the only question is which ones I'm able to code and debug in given time.
For the lower part of the field, there may indeed be the problem if I should code the one I know how to solve or maybe one of the others is easier. I agree that seeing statistics here might be helpful indeed.
I'm saying this as someone who missed IOI gold by wrongly estimating difficulty of one task, so the statistics would surely help me.
*By my limitation I mean that I decompiled the problem into subproblems and one of them is the same or harder than something I encountered before and know it's beyond my abilities. As an example: the first time I ever coded LCA was at Baltic OI. I stopped working on a problem once I found I'd need LCA (I knew the theory, just never coded it before) and went back to it only after I finished all I could in the other two tasks. I wrote some code that even passed the sample and submitted "if (small input) print LCA_solution; else print bruteforce_solution" :D Yes, I got 0.
But IOI isn't a race with time. Each contest lasts 5 hours. Not trying a problem at all for 4 hours because you think it's hard is completely valid strategy as long as you decide to try it after those 4 hours, and even if you think a problem is super hard, you should always, always try to get at least the easiest 20-30 points (the problems are designed in a way that gives you those few points easily). This is something completely independent on how you assess problems' difficulties. Then, if you see that the simple approach gives you a lot more points than you hoped for, everything is well.
In that case you needed to code it and although you could code it in 10 min, it may take you 30 mins to think of several approaches (it's a completely invalid strategy to code the first thing that pops into your mind, isn't it?) + again we're talking about strategies. In nowruz there were 2 empty tests, the only way you could get a partial score was by trying those (not like an usual problem), so 20 points at most. And well regarding my point, it doesn't matter that it is participants' fault or not for not trying nowruz. I was just stating that it's better to have stats to avoid this sort of situations, where stronger people get beaten by weaker ones because of a strategy choice (may it be the worse strategy in the world)
"That is, now the IOI is more about informatics and less about strategy".
If anything, this rule introduces even more strategy into the contest, because now submitting your code is a double-edged sword: you find out whether your submission was correct, but you also reveal the difficulty of the problem to your opponents, thus helping them. A good contestant therefore has almost no incentive to submit a problem that they are certain will score 100 points until the last 30 mins or so. A less experienced contestant will on the other hand submit the easy problem because they are less certain their code was correct, and probably get fewer points. The result is that the bar is not an accurate estimate of the difficulty of the problems, not fulfilling its intended purpose.
Now assuming everybody sticks to their old behaviour and always submit their code, there's another problem with this rule: knowing that a problem is easy / hard changes the mindset with which you approach it, making it easier to solve. Consider now the contestants who switched their mindsets (something along the lines of: "Ok, none of the best techniques I throw at this problem works, maybe just try something dumb" or "I tried all the dumb stuff, maybe this problem actually requires some thought"), took their time to think from multiple perspectives, and finally solved the problem. These contestants, who, in my opinion, posses an important skill (of looking at a problem from multiple angles), are put at a disadvantage by this new rule, because those who come after them already have the right mindset / approach spoon-fed to them. If the latter are fast coders, they can easily solve the problem as well by putting in less effort than the first solvers.
Estimating the tasks' difficulties is the contestant jobs, and as ania said this does not come only from intuition, it also comes from experience, which should always play to the contestant's advantage. Solving your work first should never put you at a disadvantage: precisely what this rule is doing.
It's needless to say I am strongly opposed to this new rule being passed.
You seem to forget that this is an olympiad, a childish fun problem solving competition, and not a freaking war that requires military strategy. Do you seriously believe that with the current difficulty of IOI tasks, someone would be crazy enough not to submit a solution just after they coded it? First, they wouldn't have a guarantee that the others did the same, and so the information about that problem's difficulty may be out anyway. Second, it's much harder to test your solution and be 100% sure it fullscores than to submit it (let alone the fact that, as I will prove below, the advantage of doing so is not really that relevant, so it's not worth to risk that much for an almost 0 benefit).
Now, indeed, it is really important for a contestant to be able to look from different perspectives to a problem. It usually is required even in easier IOI problems, but let's make this clear: knowing that a problem is easier or harder doesn't mean you know anything about how to solve it (take ACM/any online contest for example). It's not like knowing that you're looking for an easy solution or for a complicated one actually helps you (the difficulty is usually subjective anyway, but regardless, you'll still need to consider any possible ideas just as you needed before). Also, let's not forget that you may come up with a harder alternative solution (or the other way around). What really helps you and what is actually the whole purpose of this rule is that you'd at least know that you're wisely spending your time.
A guess is a guess, regardless of the many reasons you might have to really believe in it. Experience comes to the contestant's advantage at all points and it helps him solve problems anyway, it really doesn't need to be highlighted once again. In IOI, nowadays, most people who get gold solve at most 3 complete problems — that is, they are unable to come up with a complete idea for half of the problems, and these are the best contestants we're talking about. It means that when it comes to half of the problems, all but <10 people need to guess the difficulty of a problem based on gut/experience.
Anyway, it's not up to any of us. I felt the need to complete your arguments so that people that have a decision power and read this have the complete perspective of both sides in mind when they vote.
For your first argument, I agree, it's more of an edge case for the very good participants (which may come into play for the first few places, but that's another less important story).
For your second argument... you were just making the point in your first comment that knowing the problem was easy would have helped in solving it. "Best example is last year's nowruz, that maaaany contestants (including several who got gold) thought would be the hardest and started to solve the others, whereas if they knew that nowruz had maaaany scores of ~80, they would've given it more thought/time (in the current case one only needed to want to invest the time of coding a bfs in the hope of getting that 80)." It's true that it doesn't give you the solution, but like in the case of nowruz, it puts you in the right mindset.
A guess is a guess, but it might be more educated if the contestant has more experience. And I think experience has to be highlighted at every stage of the contest and at all contestant levels. This experience is an indicator of how much practice the student put in, how many and difficult problems he solved. This practice should be rewarded, not downplayed.
For the response to my nowruz opinion. It only proves what I said: it guides you when it comes to what problem to try. It doesn't put you in the right mindset. Telling you try that one, not the other one doesn't tell you just write a bfs. Of course the rule would eventually lead to certain score changes, but I think that the kind of change taking the problems in the right order makes, is a change for the better. My example of nowruz highlights what happens with and without the rule: without the rule good contestants lose points on an easy problem. With the rule, nobody gets tricked. The problems are difficult enough to not require extra challenges (such as guessing which problem is easier).
And on the long run the educated guesses win. On the short run, though (which is the case of IOI because there are only 2 days of contest), uneducated guesses have equal chances to win. I agree that the situation would be different if IOI had 20 days of contest. It only has 2, which means that contestants should go for the deterministic (not probabilistic) solution.
Rofl. tl;dr but this strategy of not submitting because giving info something that doesn't work in contest, where around 50 people can solve hard problems and other solve only 2 or 3.
Let me disagree. If tasks are binary then this would help a lot. But tasks on IOI have subtasks which highly hide such information like whether tasks was fully solved or not. There is no difference between one guy scoring 100 pts and 5 guys scoring 20 pts each.
There's a difference between one guy scoring 100 points and 200 scoring 20 points each or 50 scoring 80 points each. The one with 100 points is a statistical blip.
Exactly, that confirms my point that anybody intentionally delaying his submissions due to his strategy of "not revealing information" is definitely too confident guy who vastly overcomplicates and overthinks his strategy shooting himself in his foot while doing that.
With the top golds and hardest subtasks, or when the contest has progressed enough, that's right. Very fast partial submissions near the beginning of the contest still reveal something. (I have no idea how fast people bounce off 0 in IOI since I never spoiler myself with live scoreboards.)
My concern is more about the places around 100, where the faster, more skilled people can help others pull up to them and even overtake them by having e.g. slightly better score from an output-only problem.
Slightly better score in an output only problem means more time being put in that problem, means probably the contestant is better (he was faster at solving the others) + usually the differences aren't made by strange-scoring problems (look at scoreboards from editions with only static scores and see if people don't have different scores)
This is actually related to the prisoner's dilemma. Each individual solution does little to change the score bar, so it necessitates a whole group's compliance for this to work. However, individually it's always better to "backstab" the group and submit the coded solution. So the Nash equilibrium is that every contestant sends their solution as soon as possible, as was intended.
Why? If it's correct, then it doesn't matter when you submit it, and if it's wrong... you can always test it locally or try solving other problems first.
Because each person contributes a negligible percentage to the score bar. Last IOI each day had an average score of 26554. Last year, a 100 would contribute 0.37% to each task's bar.
So your logic is: there's a 37% chance that the counter increases by one, a person reacts differently enough to a difference of 1 enough that they think of a solution, code their idea up, and get more points, pushing you out of your medal by a few spots.
Tripping on your way to the contest hall is an astronomically higher worry than this.
You're ignoring scales. Oh, how much I hate when people ignore how a problem can scale up. A 100 by each of 50 people contributes 18%. A 40 by each of 100 other people contributes some 14% more. A 20 by each of 200 other people contributes as much again. These aren't small numbers.
How about having to roll for tripping many times? After all, you're in a crowd most of the time, there's confusion, everyone wants to get where they should be and be done with it...
Your analogy falls apart in a similar way to your math. Still, the comparison I was making is not between tripping and not tripping, it's between maybe tripping with a small chance and certainly not at no cost whatsover. The prisoner's dilemma is about taking risks. You don't take risks by taking a look at other problems because IOI doesn't have time penalty.
Look, it’s simply PATHETIC to consider a valid argument that someone would send their code later just because they don’t want to give information about difficulty. That argument is simply made up and you have to be very stupid to actually do it. I really see no point in trying to prove something obvious. Ask contestants what they would do if you actually want to see the truth. All those arguments that you think you have may work in a room with 320 perfect logicians, or military guys, not high school human beings. It’s also pathetic to see how many people got tricked by those arguments and the confidentce in expression to upvote that stupid idea as a valid argument and downvote mines. I’m giving up now on posting anymore cause if what i just said is not enough to shut up everyone’s mouth about that garbage strategy that nobody would use, then you really are a lost cause
This is you right now:
Yes, if you can't argue normally, without getting emotionally invested so much that a different opinion is being PATHETIC (ALL CAPS!!!1!) and insisting how stupid everyone who doesn't agree with you is, then stop posting.
Note that the team leaders will decide if this rule will be used this year (during their first meeting at the IOI), so we don't know yet if it will be used.
So if your like or don't like this rule, you can tell your team leaders what they should vote :)
Wanna bet on how many people will ignore it and still try to solve something they can't?
I also don't think this is fitting for IOI. In contests with public scoreboard, there's a time penalty, so if you can't solve something and look at the scoreboard to decide if there's something easy you haven't tried, you still lose time. There's no such counterbalance in IOI.
Losing time while looking at scoreboard?
No. What Xellos meant is that if you have team A who solves the easy problem on their own and team B that didn't solve it until the scoreboard told them that the problem is easy, then even if team B does solve the problem, they will rank below A because they solved the problem later.
It's not a freaking scoreboard. Just a partition of 100 in 3 parts. I think it's a good choice for IOI because it better achieves its main purposes: to attract people and not to repel them.
As for your only argument against: you lose time, doesn't that mean that you've lost something? If you manage to do as good as somebody who just happened to start with the right problem although you've lost some good time because of your initial choice, doesn't that make you at least as good as that somebody? (cause you did the same thing in less time) And let's not forget that that somebody also has access to the same data and if you then make a good second choice they can also make use of this stat to decide upon their next move.
And yep I wanna bet, but there's no way to know how many people ignored the stats. I guess that if they try to solve something they can't although they know which one is the easiest, it means they can't solve any problem anymore.
And as a last point, assuming people would actually ignore the stats, wouldn't that mean that the rule affected nobody and therefore harmed in no way IOI purposes?
And the part of the scoreboard in CF that matters to me as far as choice of the next problem to solve is the relative ratio of people who solved each problem. The only information that's lost is the subtask ratio, but the subtasks that don't matter are statistically irrelevant anyway.
People who would think "nah, the rules for this aren't nice enough, I'm not going" aren't exactly those with an aptitude for algorithmic thinking. You're making a basic mistake: trying to appeal to people who don't and won't care.
If you lose time you couldn't translate into points anyway, you don't lose anything.
No. If I can only solve a hard CF problem after seeing that many people solved it (difficulty estimate helps me A LOT sometimes), I'm not going to tell myself I'm just as good as the first 2-3 people who solved it, even if I took less actual time solving it as them, and the scoreboard will reflect it.
That was a figure of speech, we obviously can't know. I was talking about just the most stubborn noobs though, not everyone.
And the part of the scoreboard in CF that matters to me as far as choice of the next problem to solve is the relative ratio of people who solved each problem. The only information that's lost is the subtask ratio, but the subtasks that don't matter are statistically irrelevant anyway.
To me it's more relevant to see exactly who solved what (I find it important to distinguish between the case when [person 1 solved A, person 2 solved B and person 3 solved C] and [person 1 solved A B C and the others did nothing]). It does help indeed but not to the same (or comparable) extent, at least not in my case (this is subjective though)
People who would think "nah, the rules for this aren't nice enough, I'm not going" aren't exactly those with an aptitude for algorithmic thinking. You're making a basic mistake: trying to appeal to people who don't and won't care.
You're making a basic mistake as well: I'm appealed to CP and algorithmics, but that doesn't mean that if the only international event I have the chance to attend regarding this passion of mine has serious issues (which fortunately is not the case) it can't repeal me and therefore cut off from my desire to do CP. I'm already at a pretty high level and I'll keep doing CP no matter what. But the myself of 4 years ago could've been REPELLED by some stupid rules (which again, is not the case, the rules are not bad, only that I, for one, consider this one as a pretty clear improvement). Same works with problems. When I was 7th grade I heard of the notorious Art Class. That literally made me reconsider the idea of competing in IOI, because at the time (and now as well) I found it as a highly stupid choice for one problem out of 6 to tell apart the brightest high school minds of the world. So if someone is in the neutral zone, or barely in the positive one, with the very wrong choice of problems/rules you can and will be repel students, which goes against IOI's goals. I do agree, though, that IOI won't just take someone completely bored about informatics and make him suddenly interested in it. I've talked about the antithesis between appeal and repel to highlight what bad rules/problems can do.
No. If I can only solve a hard CF problem after seeing that many people solved it (difficulty estimate helps me A LOT sometimes), I'm not going to tell myself I'm just as good as the first 2-3 people who solved it, even if I took less actual time solving it as them, and the scoreboard will reflect it.
Here I can't say much...I simply disagree. If I can do something in less time than someone who just took up that problem faster I don't consider myself any weaker than that person. It's definitely subjective. But, regardless of what you think, talking about an Olympiad where speed doesn't matter and you have only 3 problems in 5 hours, it really shouldn't make a difference. You have to admit that if someone already solved the hard (implicitly, let you know that it's doable) then that someone anyway has a huuge advantage over you in terms of time. So yep, if that someone is unable to solve anything in the remaining time (in which you were able to come up with the solution and code for the hard problem), than you don't deserve more, because speed doesn't play a that important role in olympiads. It does in ACM and CP, yes. But, it's subjective again. I think that someone is better than someone else based on his ability to solve a problem when time->infininty not when time=5 hours (just as in research). Now if you want to make a competition out of it, it definitely is not possible to make the contests significantly longer than 5 hours, but I simply don't think that time matters that much to say that if someone did something faster he's better.
Personally, I'm not 100% convinced that this is a good thing.
From my point of view, the primary intent behind this rule is probably to help the weaker contestants. It is possible that it will help them a little bit. It is possible that it will do nothing at all. However, I've also seen too many cases where (in a contest with a public scoreboard) a contestant becomes discouraged because they see that "everybody else" is getting a problem they are stuck on, even though they were good enough to solve some other problems as well. Another potentially harmful effect might be that this new information will push more of the weak students to work on one problem only (the "easiest" one), and they will lose points they could have scored in the easy subtasks of the other two tasks.
But the main point here is that without any experience it is almost impossible to tell what this change will do in practice. So the two things I intend to do before voting are:
I think kind of related that for example Russian NOI have problems sorted in difficulty order so everyone solves from easiest to hardest. I think this rule was made so committee doesn't have to sort problems yet contestants do this themselfs.
I have a question : AFAIK IMO provides their problem in difficulty order. Does such statistics bear any real difference to that IMO system? I don't have a good argument against that, although I'm not convinced that this justifies the rule change either.
If it turns out that the statistics is no more than a subtask version of IMO system, then it'd be helpful to hear an opinion from past IMO contestants.