A Guide To Gaming Points In Academic Olympiads
/ 7 min read
Preface
This article is the second entry in the Guide to Gaming Points series, namely Gaming Points in Informatics Competitions. It also served as the representative paper of the Hebei team at NOI 2009 and an important achievement in Bojie Learning Network’s 2009 research plan. After the third edition of Gaming Points in Mathematics Competitions received broad praise, and after being inspired by the classic essay Guide to Gaming Points by “I Am an Idiot”, I decided to write another piece on how to score as many points as possible in informatics contests.
Content
I reused the same title, Guide to Gaming Points, not to plagiarize, but to explain the idea more concretely. I wanted to add more theory and more method to the name, to make the so-called “gaming points” strategy into something that could actually function as a useful approach in informatics competitions.
I performed reasonably well in NOIP 2008, scoring 330 points and making the Hebei provincial informatics team. I also attended the WC 2009 winter camp and got 101 points, but my real strength, especially in advanced algorithms, was not that strong. So while I was happy, I also felt that it was worth summarizing a set of practical point-gaming tricks that might push OI a little further forward. While studying for informatics competitions, I often searched in many places for relevant material. Yet every source left gaps, and sometimes two sources would even directly contradict one another, which made learning inconvenient. As far as I know, this article was the first attempt to summarize such contest techniques in a concrete and systematic way. In that sense, it may count as “the first person to eat the crab”. I hope this article can encourage more materials that summarize and organize informatics competition methods. Because my goal in writing it was to provide contestants with a relatively complete set of techniques for earning points, I decided to make the article open in spirit: anyone may revise it, add to it, republish parts of it, or quote it freely so long as the source is acknowledged.
Because the article is primarily a summary, I cannot guarantee that every idea in it is original. If Guide to Gaming Points were compared to a beautiful bouquet, then the flowers in it would all be the result of other people’s hard work. My own work was simply to select them, make the vase, and arrange the flowers in it.
The length of this article is obvious. In order to keep it accessible and easy to understand, and because this is not a formally published book, there may be some redundant passages or overly simple examples. I hope the experts will forgive that and read selectively where necessary. This article references many papers by top competitors and books by senior coaches, and quotes some passages and code from them, for which I am sincerely grateful. In fact, writing this piece felt easier than writing Gaming Points in Mathematics Competitions. Mathematics contests require proofs, and rigorous proof is always difficult. Informatics contests, by contrast, only require a result, and the existence of “partial scores”, along with black-box testing, makes them especially friendly to point-gaming strategies.
This article begins with contest mentality, takes constant-factor optimization as a foundation, uses mathematical analysis and conjecture as guiding ideas, treats imperfect algorithms as a main strategy, and keeps search as a universal final method. Through these parts, it explains several point-gaming strategies in informatics competitions and then demonstrates them in practical examples to show how powerful these approaches can be.
It is worth noting that this article does not discuss the “directly output the result” trick from Guide to Gaming Points by “I Am an Idiot”. In recent OI contests, that method is difficult to score with and does not reflect the actual nature of what informatics competitions test. “Being able to solve the problem” is the hard truth. In fact, most of the methods in this article are not really about cheating at all, but about how to use slightly weaker algorithms to still earn relatively high scores. I hope readers will learn not only point-gaming techniques from this article, but also gain insight into problem solving itself.
If “well-equipped weapons, mastery of military theory, and advantageous troop deployment” are the three elements of victory in war, then in informatics competitions, solid programming skill is the weapon, efficient algorithms are the military classics, and clever strategy is the advantage in troop deployment.
This article uses a footnote-heavy writing style. Many statements used for definitions, explanation, supplementation, and previewing later content are placed in notes. I find this makes the logic tighter and the main thread clearer. But “note” does not mean “unimportant”. Quite often, ideas with no room elsewhere and many useful details end up in the notes. I hope readers will get used to this style.
There is also a lot of code in this article, for two main reasons. First, because this is not a formal publication, I am not worried about length, and I hope readers will not care too much about the size of a PDF. More importantly, this is an informatics article centered on competition strategy, so it needs to explain the details of writing and debugging code rather than merely listing ideas and algorithms the way many other essays do. Readers who dislike code may skip over it. In order to make better use of internet resources, Guide to Gaming Points also opened an official website on the forum of “Mathematics and Logic”, where the latest version of the article, related problems, source code, test data, supporting material, and discussion all became easier to access.
Because point-gaming is inherently an irregular method and also the product of many combined ideas, I have forcibly divided the various methods into separate chapters. This does not necessarily match the way people naturally think, and it inevitably creates repetition, whether in examples or arguments. I ask for the reader’s patience.
Because my own level is limited, mistakes and omissions are unavoidable. I welcome corrections and suggestions for future editions of Guide to Gaming Points. Thank you for your support.
Some time ago, rumors that NOIP would cancel guaranteed admission spread widely. If competitions return to their natural state, that would indeed be a healthy direction for OI. Learning OI should not be only about prizes or admission; it should also be about acquiring knowledge, mastering skills, and serving future study and development. In practice, students who study informatics competitions often show strong logical thinking, rigorous expression, and broad knowledge, especially in mathematics. At present, domestic software in China is still nowhere near as widely adopted as the foreign monopolies in the market, and this creates a serious information-security concern. If we want national independence in development, we need our own information industry and our own intellectual property. The education system also pays far too little attention to informatics. These are exactly the problems that our generation of OIers should help pioneer solutions to. This article itself was edited and produced with domestic software and published under Red Flag Linux as a small gesture of support for local software and industry. What keeps domestic software from spreading is often not lower quality or weaker technology, but users deciding it is inferior before ever giving it a chance. If we can change those unfair assumptions and push back together against foreign monopolies, then a revival of domestic software may not be far away. Learn OI, contribute to the development of the national information industry, and even to the progress of informatics as a whole. I hope that is more than an empty slogan. If that grand goal could ever become reality, or if this article could encourage even a few OIers to support national industry, then the enormous effort that went into writing Guide to Gaming Points would have been worth it.
I sincerely wish every reader, guided by Guide to Gaming Points, can go farther and farther, and more and more successfully, along the road of OI.