I apologize for the long hiatus, I hope nobody thought this blog was dead. 😉
The National Olympiad in Informatics — Philippines 2017 (NOI.PH 2017) has recently concluded, and the final standings, along with some official (funny) commentary, can be viewed here. I’ve been meaning to write about the eliminations for some time, as there were a number of interesting problems; however, schoolwork had caught up and I had no time to write it. In fact, finals week has started, but luckily the only final I have this week is Economics and it is already over.
The first round of the two-day contest started on February 18, 2017, running for five hours from 1:35PM to 6:35PM. (As of writing, the contest itself is, for some reason, private. You can access the link here, but unless the privacy settings are changed, the problems aren’t actually accessible from that link. Instead, I will link directly to the problems in the succeeding paragraphs, so you can still access them.)
I really do not understand the purpose of this contest was. I read through the problems, and three of the four problems were combinatorics tasks. In the whole contest, there were no optimization problems, graph theory, algorithms or data structures involved except some dynamic programming.
In fact, I doubted whether the contest was a programming one, or a math one. In the previous years of NOI.PH, the first day always tended to be slightly biased towards math, but there was always at least one purely algorithmic or data structure problem to offset it. I feel that this contest went way overboard.
I like to remember that this contest is called the NOI, not the NOIMO.
Anyway, let’s move on to the discussion of the problems:
The easiest problem, Betty’s Bitter Batter Bother, can be roughly stated as follows: How many permutations of the first positive integers exist such that, for all numbers starting from the third one, at least one of the two numbers before it is greater?
Assume up to , and up to test cases. Output the remainder after dividing the result by .
My combinatorics is trash, so when I first saw this problem I thought it would be some sort of hard dynamic programming optimization problem, possibly optimized with segment tree or something. In the end, after failing to think of a solution better than dynamic programming with bitmask, I ended up writing a brute-force program that simply considered all permutations for and then pattern-matched a recurrence from there.
The official solution is simpler:
Let denote the number of permutations of numbers, satisfying the constraints above.
If , clearly there is only one valid permutation. Likewise, is , there are two valid permutations.
Otherwise, consider the number . It should be clear that this number can only go to either the first slot or the second slot.
If it goes to the first slot, then the conditions for the second and third slots are automatically satisfied, and it can be shown that the answer is .
If it goes to the second slot, then the conditions for the third and fourth slots are automatically satisfied. At the same time, the first slot can have anything. It can be shown that the answer is .
Therefore, . Voilà, we have a one-liner solution that gets full points.
Although I was the first to get it, this problem really irked me because there are no algorithms involved, just pure mathematical reasoning (or brute-force searching a pattern). I do not really see the point of including such problem in an informatics competition, especially considering the fact that the NOI.PH is supposed to be the qualifier for the IOI, which in itself puts almost no focus on combinatorics. Indeed, in the two years I had the opportunity to join the IOI, there were zero counting problems of any kind.
I missed the second-easiest problem, The Chenes of the Chorva, due to a careless misreading of the problem statement. I had already become accustomed to skimming through the problem statement, and, because they were usually sabaw, I missed the condition that the array was bitonic (as it was only mentioned in the start, and it seemed to be part of the legend rather than part of the problem; it was not mentioned in the constraints. It seemed many other participants also missed this condition). Here is the problem:
Given a bitonic array of integers, the value of a subarray is the sum of the maximum values in all the subsequences of the elements in the subarray.
Answer queries. In each query, given a subarray, find the value of the subarray, again taking the remainder after dividing by .
Assume and up to .
I spent a very long time trying to come up with a solution to the unsorted version of the array, but could not come up with a good solution. An solution gets 53 points, while my solution got 65 points. I think an solution might exist for the unsorted version, but I did not flesh out this idea as it was unlikely to pass; there are up to test cases to be solved in two seconds. A rather straightforward solution without any complicated data structures exists for the bitonic array.
My favorite problem is the first one, and, although I did not get it, I really applaud the problemsetter for this beautiful task. Simply put:
Given and , how many distinct integers of the form with and exist (where is the bitwise xor operator)?
Assume and up to , and up to test cases.
It is very tempting to generate a grid with all the answers and try to find some patterns in it, and indeed, I wasted too much time doing so. There are many beautiful patterns in that grid, but a formula that works for all pairs of numbers was elusive. The official solution answers each test case in time using dynamic programming on the digits, and elegantly deals with the cases.
Farrell was able to solve this problem fully; congratulations!
I have a strong distaste for the fourth and hardest problem, which was basically combinatorics disguised as a grid problem. The problem was, objectively speaking, very interesting, but I believe it has no place in the NOI.PH and would have been better placed in some Ad Infinitum contest. The problem goes as follows:
Given a binary grid with rows and columns, we can extend this grid to rows and columns using the following process:
Make a new column. The value in each row of this column is the parity of the sum of the values in the corresponding row.
Make a new row. The value in each column of this row is the parity of the sum of the values in the corresponding column.
Call a grid generated this way a valid grid.
You have a grid with rows and columns. Let be the minimum number of cells needed to change it into a valid grid. Find and count the number of ways to change cells such that it becomes a valid grid. Take the remainder after dividing the answer by .
Assume and are up to , and is up to .
I will not discuss the solution to this problem, but it boils down to pure combinatorics and some dynamic programming.
I have said it before, but I will say it again in hopes that the problemsetters and organizers will take notice. I really do not understand the purpose of having a day of math problems in the NOI.PH. This gives a distinct and unfair advantage to those who are good at maths, which would be all well and good until you consider the fact that the contest this is supposed to prepare the contestants for the IOI, which has very little to no math problems at all.
The rationale I have been told is that the number of competitive programmers, or “algorithm people”, in the Philippines is relatively low, whereas the number of mathematicians is quite high; thus, there is a desire to bring some “math people” into the NOI.PH, and then just train them after. Supposedly, “math people” are easier to train.
This reasoning makes sense, but it does not justify weighing mathematics and algorithms the same. I understand using this reasoning in 2015 and 2016; there were some math problems in the first day, but even then, these math problems were still algorithmic in nature; Dili Magpakopya and A Simple Problem!, both math problems from 2015 and 2016, respectively, still required some algorithms. The first problem required a Sieve of Eratosthenes, while the latter required a sliding window. This contest, on the other hand, had three almost purely combinatorial problems.
This reasoning also falls apart when you consider the fact that there are already algorithm people, some of whom did not make it to the top ten simply because they performed poorly in the math contest! There was even a contestant who was able to solve a nontrivial graph theory task in the second day, getting fourth place in the algorithms contest, who did not make it simply because he was unable to spot the required combinatorics formula in the first day. To put enough weight on mathematics that this can happen is a slap in the face to people who actually train algorithms, and it might even end up being contrary to the goal of getting more people interested in algorithms; people who are good in algorithms will be discouraged from training algorithms and train math instead, just to have a chance. Case in point: said contestant now wants to enroll in MTG to improve his math for next year.
Rant aside, when contestants are not good at the contest topic, it does not make sense for the organizers to change the contest topic; instead, it should be the contestants who should improve at that topic. I first became interested in NOI.PH back in 2014 because I found algorithms interesting; had I known that the contest would be 50% mathematics and 50% algorithms, I would never have joined, knowing that I would not have a chance against those who were already very good at math.
In any case, congratulations to all the top scorers of this contest! Three of the top four participants of this contest, Farrell Eldrian Wu with points, myself with points and Franz Louis Cesista with points, will go on to make the top three overall. In what order, find out soon!
(Or look at the leaderboard in the link on top. 😛 haha)