For competitors in a contest, it is also best to find, solve and submit the easier problems first given a set of problems. Otherwise, one might spend so much time in a single hard problem that he losses time that could have been more productively used to submit much easier problems. So instead of submitting 3 easy problems at the end of the contest, he only submits 1 hard problem. But the weight of the easy problem is just the same weight as a hard problem in a programming competition.
So, when one starts a contest, before solving any problem, he should scan and sort out which problems are easier to solve first. Then he should solve the easier problems first. If he wishes to win, then he should resist the temptation of solving the hard problem first for whatever reason. The easy problem and the hard problem would earn one the same amount of money if the contest awarded cash prizes. So why should one consume all his time in solving a hard problem, unless he is not after winning the contest and just simply after programming insight enlightenment?
In this post, I discuss about finding easy problems in the UVa problem archive. Easy problems are only relative in the sense that they are easy compared to the other problems also existing within the archive. So how do we define relativity? Through statistics.
Figure 1 shows a screenshot of the problem archive where statistics are shown for each problem.
Figure 1. Screenshot of the problem archive.
Two ratio statistics are shown for each problem. The first one is the ratio of accepted submissions to total submissions. Let’s call this the BR ratio. For example, for problem 10800, the BR ratio is 19.73%. The second ratio is the ratio of number of users who actually solved the problem to the total number of users who attempted to solve the problem regardless of whether they solved it or not. Let’s call this the UR ratio. For problem 10800, the UR ratio is 67.51%.
Two other statistics exist which are the total submissions for a problem (B value) and the total number of users who attempted to solve a problem (U value). For problem 10800, B is 5039 meaning there were 5039 submissions for this problem whether the submissions were accepted or rejected. For the same problem, U is 1265, meaning there were 1265 users who submitted solutions whether their solutions were accepted or not.
So given this statistics, how do we interpret them? Generally, to find an easy problem, we would want to look for one which has a relatively high BR ratio. This means that an easy problem would be a problem for which most submissions were accepted because it was easy to solve so most people solved it in their first attempt or submission.
Figure 2 shows an example were an easy problem is visually spotted out.
Figure 2. Problem 10865 is likely to be an easy problem.
In Figure 2, one can easily point out that problem 10865 can likely be an easy problem because of the high BR ratio relative to its surrounding neighbor problems. The BR ratio stands out at 71%. Its closest rival has a BR ratio of 55.81%. The 71% BR ratio means that for about every 10 submissions, 7 of those were accepted. With a higher statistical historical ratio, one’s likelihood of solving the problem becomes higher. So it would be better if one start with such easy problems when starting his career in programming in order not to get frustrated at the start of his career immediately.
There is a watch out though. Figure 3 shows an example.
Figure 3. Problem 717 appears to be an easy one but could be actually a real hard one.
In Figure 3, problem 717 stands out easily with a BR ratio of 83.33%. This ratio is very high compared to other problems’ ratios. But looking at its B value of only 18, something looks fishy. The B value is very low which means that out of the tens of thousands of coders, only 18 solutions were submitted. Looking at the U value reveals something even more dismal: only 12 users attempted to solve this problem.
So why did most users avoid this problem as only 12 out of the tens of thousands of coders attempted to try this problem? Most probably this problem is a difficult one which most coders have no idea on how to solve. And those who attempted to solve it were most likely the genius type of users. Remember in high school or college when there would always be someone in class who stands out because of his extreme intelligence. Well, this is perhaps the type of person who solves the problem like problem 717.
So one feel that he is confident to take on really challenging problems, and that most problems have become too easy already, and that he has had enough programming experience already so that he is no longer vulnerable to becoming frustrated whenever he is unable to solve difficult problems, then one must at all cost avoid this type of problems with high BR ratios but extremely low B values.
Notice also that for problem 717, out of the 12 users who attempted it (U = 12), all of them were able to solve it (UR = 100%), confirming that these few people must indeed be geniuses.
Speaking from experience to ahh:
ReplyDelete"For competitors in a contest, it is also best to find, solve and submit the easier problems first given a set of problems. Otherwise, one might spend so much time in a single hard problem that he losses time that could have been more productively used to submit much easier problems. So instead of submitting 3 easy problems at the end of the contest, he only submits 1 hard problem. But the weight of the easy problem is just the same weight as a hard problem in a programming competition."