# NOI.PH 2017 Finals, Round 1

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 $N$ 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 $N$ up to $10^6$, and $T$ up to $100000$ test cases. Output the remainder after dividing the result by $10^9+7$.

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 $N!$ permutations for $N \leq 10$ and then pattern-matched a recurrence from there.

The official solution is simpler:

Let $p(n)$ denote the number of permutations of $n$ numbers, satisfying the constraints above.

If $N =1$, clearly there is only one valid permutation. Likewise, is $N = 2$, there are two valid permutations.

Otherwise, consider the number $N$. 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 $p(N-1)$.

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 $(N-1)\cdot p(N-2)$.

Therefore, $p(N) = p(N-1)+(N-1)\cdot p(N-2)$. 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 $N$ integers, the value of a subarray is the sum of the maximum values in all the subsequences of the elements in the subarray.

Answer $K$ queries. In each query, given a subarray, find the value of the subarray, again taking the remainder after dividing by $10^9+7$.

Assume $N$ and $K$ up to $100000$.

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 $O(NK\log N)$ solution gets 53 points, while my $O(NK+N\log N)$ solution got 65 points. I think an $O((N+K)\sqrt{N}\log N)$ 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 $S=7$ test cases to be solved in two seconds. A rather straightforward $O(N+K)$ 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 $M$ and $N$, how many distinct integers $x$ of the form $x=i\oplus j$ with $1 \leq i \leq M$ and $1 \leq j \leq N$ exist (where $\oplus$ is the bitwise xor operator)?

Assume $N$ and $M$ up to $10^9$, and up to $T=200000$ 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 $O(\log \max (M, N))$ 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 $m-1$ rows and $n-1$ columns, we can extend this grid to $m$ rows and $n$ 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 $M$ rows and $N$ columns. Let $k$ be the minimum number of cells needed to change it into a valid grid. Find $k$ and count the number of ways to change $k$ cells such that it becomes a valid grid. Take the remainder after dividing the answer by $10^9+7$.

Assume $N$ and $M$ are up to $2^{19}$, and $N\cdot M$ is up to $2^{20}$.

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 $275$ points, myself with $217$ points and Franz Louis Cesista with $183$ 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)

# NOI.PH 2016 IOI Selection Contest

The National Olympiad in Informatics — Philippines 2016 (NOI.PH 2016) concluded two weeks ago with the final team selection contest. The onsite contest consisted of a single, massive six-hour round (which, due to some hardware failure, ended up getting extended to eight hours) with five very challenging problems. (The problems can be viewed here.)

I began by opening and reading all of the problems. I started with the first problem, but I couldn’t understand what it was asking due to it having many errors in the explanation. I read the second problem, which was a blatant segment tree with lazy propagation task:

Given an array of $N$ integers $A_1, A_2, A_3, \dots A_N$, support $Q$ queries among the following types:

• Given $l$ and $r$, find the sum $A_l + A_{l+1} + A_{l+2} + \dots + A_r$;
• Given $l$ and $r$, find the sum $T(A_l) + T(A_{l+1}) + T(A_{l+2}) + \dots +T(A_r)$ where $T(x)$ is the $x^\text{th}$ triangular number;
• Given $l$, $r$, $a$ and $b$, add $a$ to $A_l$, $a+1b$ to $A_{l+1}$, $a+2b$ to $A_{l+2}$, $a+3b$ to $A_{l+3}$ and so on until $A_r$.

Obviously the constraints are just high enough to rule out the $O(NQ)$ solution.

I decided to postpone coding it until I had read the other problems, because I didn’t want to end up spending half the contest implementing it and the other half trying to find the bug, like I did last time during APIO 2016.

The third problem was the most interesting out of the five (and also the hardest—why are the interesting problems always the hardest ones?), and, although I couldn’t score any points on it, I do commend the problemsetter for writing such a beautiful problem. In short, given $N$ and $M$, we are tasked to generate a tree with $N$ nodes and $M$ pairs of nodes which are at distance $2$ from each other, or say that no such tree exists.

The fourth problem was an obvious free $100$ points if you knew union-find; it has a long and convoluted problem statement that eventually boiled down to performing union-find on the nodes in some specific order then a simple binary search the answer. I hadn’t read the fifth problem yet, but the solution was very obvious so I decided to code it. Not even an hour later, I already had $100$ points under my belt.

The fifth problem was also a very classical one. Basically, we have to rotate the points $45^{\circ}$ and then perform some 2-dimensional range queries using a Fenwick tree. I have never coded either of those before, but as I knew the idea I went for it anyway, since I didn’t have a clue on how to approach the other problems yet.

I spent a lot of time coming up with some formula to rotate the points the correct way. Geometry (and math) had always been my weakest point when it came to competitive programming, but luckily for me, I had just taken trigonometry during my previous year in school and had an awesome mathematics teacher who was passionate about making sure we understood how they worked, so, with much effort, I came up with the following formulas for how to rotate the points $45^{\circ}$ about $(0, 0)$:

$x'=\sqrt{2(x^2+y^2)}(\sin(\frac{\pi}{4}-\arcsin(\frac{x}{\sqrt{x^2+y^2}}))) \\ y'=\sqrt{2(x^2+y^2)}(\cos(\frac{\pi}{4}-\arcsin(\frac{x}{\sqrt{x^2+y^2}})))$

This maps each point $(x, y)$ to a new coordinate $(x', y')$, where we can now just use the 2-dimensional Fenwick tree queries. I found out after the contest that this was hilariously overkill, and the following formulas work as well:

$x' = x+y \\ y' = x-y$

But, whatever. I am still very proud of myself for being able to come up with the formula, and, shout-out to my math teacher for teaching me how to use $\sin$ and $\cos$ functions.

Now, the only thing left was to code 2-dimensional Fenwick trees. This part was surprisingly quite easy, as it turned out to be just two nested loops the same way we would code a 1-dimensional Fenwick tree query; of course, I still spend quite some time debugging as I made a few dumb mistakes, but I was able to finish thinking of and coding the entire solution within about two and a half hours, so I was really happy.

With about two hours left in the contest, I spent some time thinking about the third problem, but then couldn’t think of anything and just went for the segment tree problem. I scored half of the points for that problem, since I couldn’t find a way to implement the second type of query (finding the sum of triangular numbers). Math was not my strongest suit, and I had encountered a similar problem before when I had to find the sum of squares instead, and I wasn’t able to comprehend the solution. Of course this problem was easily reducible to that one, so I decided to give up on it and spend the remaining one hour trying to actually understand what the first problem was asking.

At that point, only Farrell had managed to score anything in the first problem (which I thought wasn’t too surprising, since a similar situation had already happened before, where I couldn’t understand the statement even after 10 clarifications while Farrell seems to understand it easily). I asked a few clarifications and it turns out that the problem explanation had lots of mistakes, which explains why I couldn’t understand it.

I eventually “understood” the problem and came up with a straightforward dynamic programming solution for the problem, but then my output wasn’t matching the sample output (by about three orders of magnitude) so I had to read the problem statement again and again before I finally found that I misread it, and at that point there was less than ten minutes left, so I stopped coding and just looked at the leaderboard.

Surprisingly, nobody else was able to score full points on any problem, which I thought was quite depressing as it showed the level of competence our country had in the competitive programming scene. In fact, besides a few, virtually everyone was stuck at $60$ points, which was basically $10$ points from brute-forcing the first problem (it actually gives up to $20$ points, but many had an overflow error which resulted in only getting $10$ points) and another $50$ points from brute-forcing the fifth problem. Nobody else was even able to score on the fourth “giveaway” union-find problem, and it got even more depressing when you realize that these people were among the top ten of the finalists during the NOI.PH 2016 finals.

Anyway, the contest concluded a few minutes after that. The contest was supposed to finish at 3:45 pm, and it ended up finishing, I believe, at almost 6:00 pm. I had some minor chest pain afterwards, I think it was from being too hungry and not eating anything, but luckily I was rushed to the hospital restaurant just in time and then everything went back to normal.

Overall, the contest was pretty well-organized (except for the hardware failure, but these things are usually unpredictable), and all the problems (except the first) were very-well written; for this, I give my sincerest thanks to the contest organizers and problemsetters.

Also, my heartfelt congratulations to all those who made the cut! Congratulations to Farrell Wu, for securing second place at $110$ points, Ian Palabasan at third with $70$ points, and Andrea Jaba, for clutching fourth, with $60$ points. I hope we can all get medals in the upcoming IOI!

Until next time!

# APIO 2016

APIO 2016 just concluded earlier this month, and my performance was quite disappointing. I scored only $46.38$ points, due to using a wrong strategy and wasting too much time on one problem (which turns out, only one or two people internationally even managed to solve), even though I am confident I would have been able to score $157$ points (which would have been enough for a silver medal) had I used my time optimally. Oh well, it isn’t my last year yet, so I still have a chance to maybe score gold medal next year.

The problem I spent most of my time on was the second one, which was the following:

Given a tree with weighted edges rooted at node $1$, change some edge weights so that the distance between the root and each leaf is the same. Each edge should have a non-negative weight. Minimize the total amount the edge weights have to be changed.

At first, I thought it was a very easy greedy solution; consider all the leaves which have the same parent. Clearly, all of these edges should have the same weight, so we will change it to the median, and now propagate the distance to the parent. After we do all the leaves, we now perform the same thing with the parents, and so on until we reach the root. It seems like a very easy problem, then I realized that there are so many different cases that will destroy my solution. First, there could be multiple “medians” which are all optimal; for example, one edge of weight $1$ and another edge of weight $1000$, we can change them both to any value between $1$ and $1000$, and they all have the same cost; eventually, one might give a better global result. What I did to handle this case was to give a “leeway” factor to it. I set it to the minimum possible median, and propagate this leeway factor to the parent as well, saying that we can increase the distance of this by the leeway at no cost.

I then had to replace finding the median with ternary search, and it took me maybe two hours to implement and debug this solution. I submitted it, and kept getting wrong answer, and I couldn’t find out why. Eventually, almost near the end of the contest, I found the critical corner case; this approach sometimes makes the edge weights negative (can you give one such case?) which is not allowed by the problem. I couldn’t find any way to salvage this approach after that, since there were simply too many cases and at that point, there were maybe only thirty minutes left and I haven’t even read the third problem yet.

I just gave up on it and spent the remaining thirty minutes frantically trying to understand, implement and submit the third problem, and luckily I was able to score $30.38$ points there. Looking back, I would definitely have been able to score the full $100$ points had I spent more time on it, since the solution ended up being very simple.

Although the contest was definitely very demotivating, at least it reminded me of the dangers of being too overconfident and persistent with a suspicious approach. I went for the high risk, high reward option (fully solving the second problem pretty much guaranteed a silver, and possibly a gold) rather than the safer approach of going for at least getting a bronze medal, and I suffered the consequences.

At least, I could experience this lesson firsthand before IOI 2016; it would be a real bummer to have to learn this lesson more painfully in the most anticipated contest of the year. In times like these, I tend to remember Andrew Matthews’ quote:

“Life is a series of lessons I need, happening in perfect order.”

And indeed, there is no truer lesson than that.

# World Codesprint April

Last Saturday, World Codesprint April was held on Hackerrank. (The problems can be accessed here.) It was a whole-day contest, with eight problems of increasing difficulty.

Most of the problems were very interesting and creative, and I thoroughly enjoyed the contest. Indeed, although I haven’t really written much about online contests in my latest entries, I felt compelled to write about this one, just because of the quality of the tasks.

I encourage you to read the tasks yourself, and try to come up with solutions!

My favorite task in the contest was the following:

lovely triplet of a graph consists of three distinct vertices ab and c, such that the shortest path between a and b, between and c, and between a and c all have a length $Q$ for some integer $Q$.

Now, I was expecting that the task would ask me to count the number of lovely triplets in some given graph, but the task was actually the opposite; given an integer $P$, we have to generate a graph with exactly $P$ lovely triplets!

We have $1 \leq P \leq 5000$ and $2 \leq Q \leq 9$. Of course, to make things harder, the graph we generate can have only at most $100$ nodes, and at most $100$ edges!

The task seems completely unapproachable, until we realize that the graph does not necessarily have to be connected. Even then, the problem is not trivial; we have to make a few other observations in order to successfully come up with a working algorithm.

Can you discover the rest of the required observations, and come up with an algorithm that will solve the problem?

Perhaps due to a stroke of luck, I was able to rank in the top 100 in this contest! I managed to win a t-shirt, making this the first time I have ever won anything from an online contest. I hope for more successes in the upcoming months!

On an unrelated note, APIO 2016 is in two days! I will make sure to update this blog after the contest and subsequent announcement of results.

# NOI.PH 2016 Finals, Round 2

I hadn’t published this yet as I was waiting for the official, final results to be posted. It was posted a week or two ago and now the final standings can be viewed here. Congratulations to everyone advancing to the training camp, and I hope to see you all doing your best in the final selection contest!

The National Olympiad in Informatics — Philippines 2016 (NOI.PH 2016) had the second round last February 14. (The problems can be accessed here. It appears that the privacy settings for both contests have finally been set to public, so feel free to try solving the problems yourself!)

It seems that the problems this time around are a bit harder than usual. The second problem, for example, was the following “easy” problem that only three people managed to solve completely (with the others scoring very minimal partial points):

Consider a grid containing $M$ rows and $N$ columns. A single cell on the $i^\text{th}$ row and $j^\text{th}$ column is marked. Determine the maximum number of cells you can still mark, if cells in the edges and borders of the grid cannot be marked, and marked cells cannot share an edge or a corner.

The constraints given have $N$ and $M$ up to $10^{12}$, with the answer guaranteed to be at most $10^{18}$, which makes it obvious that a closed-form formula is needed.

I managed to solve the problem, but it took me slightly over an hour of trying to determine all the possible cases and making many unproven assumptions. Meanwhile, Farrell was able to solve the same problem in less than half the time. Congratulations!

The other problem I was able to get full points asked for the $N^\text{th}$ positive integer whose digits, when read from left to right, are nondecreasing. $N$ is up to $10^{18}$.

The problem requires the use of combinatorics, and there are a lot of details in implementation. I ended up spending more than two hours on the problem, which was rather unfortunate because I wanted to have more time to tackle the remaining problems, which were more algorithmic in nature.

The last problem was the most interesting problem in the contest by far. The original problem is on a grid, but we can present an abridged version here. Given a tree with $V$ vertices, answer $Q$ queries. Each query asks for the lowest common ancestor of two nodes $i$ and $j$ if the tree is rooted at node $k$. Obviously, we have $V$ and $Q$ just large enough to rule out the $O(QV)$ solution. Can you spot a more efficient one?

Since I was already running out of time by this point, I only managed to implement brute-force solutions for the remaining two problems. I still did quite well, however, scoring a total of $306$ points in the end. Farrell followed with an astounding $240$ points, and the third placer, Shaquille Que, finished with a commendable $104$ points.

In other news, the XAPC that was intended for last year will be moved to this year, and held probably during early May. I am still working on the problems for the contest.

With that, I’ll see you all next time!

# NOI.PH 2016 Finals, Round 1

The National Olympiad in Informatics — Philippines 2016 (NOI.PH 2016) had its first of two finals rounds yesterday. (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.)

Congratulations to all participants! Eighteen of the twenty participants were able to score. The current tenth placer has $46$ points, and the participant immediately below garnered $40$ points. For those who were not able to score, don’t worry, there’s still plenty of room to catch up!

There is are rather huge gaps between the scores among the top placers—the current sixth placer has $56$ points, with those at fourth and fifth both having $104$ points each; Farrell Wu is currently at third place with $140$ points, just slightly below the second placer at $156$. I managed to secure a clear first, scoring $372$ points out of $400$.

The problemset this time around was, in all honesty, rather straightforward, with the exception of the third problem (which served its purpose as the “long and tedious” problem nobody bothers to read and really understand, but is not actually particularly difficult, long, or tedious for that matter). For example, the fourth problem in the set was a basic combinatorics exercise, the second problem is a standard application of sqrt-decomposition (which was ironic, as it was the only problem I didn’t solve, and I am normally good at data structures and bad at math).

For example, here is the first problem in the set:

Given a positive integer $N$, what is the minimum positive integer $K$ such that $K!$ is a multiple of the square of $N!$?

The problem has some subtasks, but during the contest, I immediately went for the full pointer with up to $200000$ test cases and $N$ up to $200000$.

It requires several insights to get right, although these insights are not really too hard to spot. Can you solve it?

From the contest, I have learned the importance of time management and not giving up. Although I did score really highly in this round, and in fact it has been my best round yet (excluding all or any practice rounds), I still feel that I missed an opportunity to get a perfect score. I only had one subtask left to go, and in fact, I still had a little less than two hours to try to solve it. Unfortunately, I gave up midway, because I was not confident with my ability of solving that problem. It is only after I got a hint, after the contest, that I realized how close I was to the solution, and to that elusive $400$.

That said, I wish everyone a good night’s rest, and an even better result in the upcoming contest. And for those who will be making it into the camp, I look forward to seeing and training with all of you!

Best of luck, but most importantly, have fun!

# NOI.PH 2016 Eliminations, Round 3

The National Olympiad in Informatics — Philippines 2016 (NOI.PH 2016) had the final eliminations round today. (The problems can be found here.)

Due to a conflict in schedule with an official school activity, I was not able to participate in it. It seems, however, that Farrell Wu has once again managed to bag first place, scoring a whopping $102$ points—almost twice the score of the four contestants tied at second place, who all have $56$ points each. Congratulations!

I was able to take a look at the problems, and they were brutal, especially when compared to the problems of the second eliminations round. Indeed, the median score was zero. In fact, only fourteen participants managed to get a positive score—my heartfelt congratulations go to all of them! Also, not a single problem was solved completely by any participant.

This time, the problemset was much more diverse, with two problems relying more on (I believe) mathematical reasoning, with the other two being pure graph and dynamic programming exercises.

Since I haven’t spent much time on the problems yet, I can’t say for sure which of the problems are the most interesting. The first problem, however, looks rather interesting:

Given $N$ positive integers $A_1, A_2, A_3, \dots, A_N$, we can multiply some of these integers by $-1$ such that $\max\limits_{i \leq N}(0, A_1 + A_2 + A_3 + \dots + A_i) - \min\limits_{i \leq N}(0, A_1 + A_2 + A_3 + \dots + A_i)$ is minimized. Print the actual solution.

The literate competitive programmer would have immediately recognized this as a modified version of the classical partition problem. Unfortunately, it seems the obvious $O(N^2\max A_i)$ solution will not work, since we have $N$ and $A_i$ both up to $800$, so this will take too much memory. And, using the “space saving trick” of keeping only two rows of the table a time will not work either, since we will not be able to reconstruct the solution. Can you think of a solution?

This concludes the qualifying phase of the National Olympiad in Informatics for the year 2016. I look forward to seeing the top twenty participants in the onsite finals from February 13 to 14, and for those who didn’t make it, don’t worry! Keep training, and for sure, you will definitely be able to qualify next year.

Good luck to everyone, and have a great year ahead!