This year I wrote 5 problems, although 1 got rejected. The other four, 2 were used in Gemastik final round, and the remaining 2 were used in ICPC Jakarta. Probably some will get confused why I submitted some problems to Gemastik, given my stance toward the competition (FYI, I don't like Gemastik). Nevertheless, I still submit because well.. let's just say someone I know asked me to write 2 problems for Gemastik. Funny note for future contest organizers: if you approach me personally to write CP problems, it is more likely I will write one for you.

Regarding the problems I wrote this year, personally I don't think they are that interesting, compared to the problems I wrote last year. For comparison, I like the problem D - Forbidden Card, as it is an ad-hoc like problem, and it took me some time to assure myself that my solution was correct :P Although, if I have to pick my favorite among this year's problem, probably it will be G - Greedy Knapsack, given how stupid the problem description is :P

Next, I will write regarding the four problems I wrote this year, about how I came up with them, the solution (if the editorial doesn't exist), and any other interesting stuffs regarding them. I will list them in the order I came up with them.

Gemastik 2021 Final H - Ketahanan Website

Problem link: here
Editorial: none, described below

I was trying to make something involving chaos engineering, that's it. Honestly, when I re-read the description I think it doesn't even make sense ;_; It also seems convoluted, as I used few terms with close meaning. Hopefully the description is not that confusing..

The problem itself is quite classic. Notice that, the problem wants us to remove as few vertices as possible such that there is no path from 1 to any of the vertex without any outgoing edges. Thus, if we create a super node to represent all such vertices, then the problem turns into a minimum cut problem, which can be solved with max-flow. Note that as a vertex have at most 5 outgoing edges, the answer is also bounded by 5. Hence, any max-flow algorithm will reduce into doing at most 5 BFS. So, this problem can be solved in $O(N)$.

Rant: originally I wanted to print any minimum cut as well, but somehow the organizer cannot set up custom scorer in their DOMJudge. Literally few days before the competition, I need to somehow modify the problem such that we don't need to use custom scorer. First thing that comes to mind is to change so we output the lexicographically smallest. However, as it is risky (I don't have a concrete idea how to do it efficiently, nor do I have a lot of time to make any huge change), I decided to just print the size.

Gemastik 2021 Final E - Rekonstruksi Pohon String

Problem link: here
Editorial: none, described below

First thing that comes to mind when I tried to mix string and tree.

This is just greedy with some case-bashing. First, denote $D(i)$ as the depth of node $i$. Then, we will process each node based on the ordering in $A$. First, we set $C[A[1]]$ as $a$. Then, for $i \geq 1$:

• if $D(A[i]) < D(A[i+1])$, then we set $C[A[i+1]]$ as $a$.
• if $D(A[i]) > D(A[i+1])$, we find the ancestor of $A[i]$ which is on the same depth as $A[i+1]$. Suppose it is node $X$. Then, we set $C[A[i+1]]$ as $C[X]+1$.
• otherwise, both nodes are at the same depth. There are only two cases:
  • if $A[i] < A[i+1]$, we set $C[A[i+1]]$ as $C[A[i]]$
  • else, we set $C[A[i+1]]$ as $C[A[i]]+1$

Note that in the first case, it must be the case that $D(A[i+1]) = D(A[i])+1$. Hence, finding k-th ancestor in the second case can be done naively, and the total operation will still be amortized $O(1)$. Overall, this problem can be solved in $O(N)$.

Note: at first I want to ask contestant to print any possible solution, instead of the lexicographically smallest. However, I was too lazy to write the custom scorer, so I decided not to. Ironically, in the end I have to write the custom scorer when I write the testcase generator for this problem. Nevertheless, it is still a good choice to not allow any possible solution, as the organizer does not support custom scorer anyway.

ICPC Jakarta 2021 G - Greedy Knapsack

Problem link: here
Editorial: here - problem G

This is a harder version of Kattis - Trick and Treat. At first, I solved that problem with a weird DP + brute force, but later realized the observation that the optimum must be attained in the range of $[M-10, M]$. After that I came up with solution involving segment tree which can solve the problem in $O(N + MAX\_W \log N)$. This is my intended solution when I submitted this problem for ICPC. Then, Christo came up with a simpler solution which can be implemented using heap. This is the solution we used in the editorial. In this post, I will try to describe my solution.

First, both solutions build upon the lemma mentioned in the editorial, which states that the optimum $M$ must be attained in the range of $[T-MAX\_W+1, T]$. To prove it, for the sake of contradiction, suppose the optimum $M'$ is less than $T - MAX\_W+1$. Denote $S$ as the set of items taken when we set $M'$ as our capacity. Suppose $j$ is the lowest index for the item which is not taken. Then, as $M' + W[j] \leq T$, we can still take $j$ into our set. Notice that, the resulting set will be $S \cup \{j\}$. All of this contradicts $M'$ optimality, and thus, the optimum $M$ must be in $[T-MAX\_W+1, T]$.

From here, the solution in editorial tackle this problem by efficiently maintain the result of the knapsack across $MAX\_W$ different initial capacity. My initial solution instead try to maintain the result of a knapsack of a given capacity $Y$ from $Y-1$. Observe that, when we increase the capacity to $Y$, either no new items are added, or an item with index $i$ is added, and all taken items with index $j > i$ will be removed. Finding such index $i$ can be done using lazy segment tree. So, we start with capacity $T-MAX\_W+1$, and sequentially find the knapsack result until we reach $T$. The whole thing can be done in $O(N + MAX\_W \log N)$

Actually, I underestimated this problem a lot, especially after I learned Christo's solution. I thought this will be a medium level problem which will be solved by around 5~8 teams. Near the contest day, Rafael told me that this problem is expected to be the third hardest in the problem set, which surprised me. Judging from the scoreboard, it seems that is the case, though.

As a side note, the solution in the editorial is actually $O((N + MAX\_W) \log MAX\_W)$. As for now, I still don't know whether this problem can be solved efficiently if we set $MAX\_W \leq 10^9$. Below is the "killer test case":

• For solution in editorial, set the first $\sqrt{MAX\_W}$ items weight such that we will end up with ranges $[1, 1], [1, 2], ..., [1, \sqrt{MAX\_W}]$ in the heap. Then, proceed with $\sqrt{MAX\_W}$ items that have weight of 1. This will force $MAX\_W$ updates in the heap
• For solution described above, create test case like $50000, 1, 49999, 1, 49998, ...$. This will ensure that every change of capacity from $Y$ to $Y+1$ will change the set of the items taken.

ICPC Jakarta 2021 B - Bicycle Tour

Problem link: here
Editorial: here - problem B

Change Jakarta into Bontang and Ahmad into Ayaz and this is exactly my issue when I cycle around my home. I get bored easily with the same route, so I tried to came up with different possible cycling routes around my home. However, there are 2 additional constraints: First, if possible, I don't want to go through the same street multiple times. Second, as I suck in uphill, if possible I want to avoid uphills (although nowadays I have learnt to live with it). Which is why, if the problem description seems weird ("why not give the weight on each edges, rather than by using height difference"), it is just that I want to share my suffering.

I think there's nothing more to add to the editorial, I feel it is already well explained there.

As a side note, there is a variation of this problem which I cannot solve until now. Say, as braking is actually easier than cycling uphill, so I wanted to set the weight of an edge to be $\max{(H[j] - H[i], 0)}$ for an edge from $i$ to $j$. Note that this correspond with $H[j]-H[i]$ cost if $H[j] > H[i]$ (going uphill), and 0 otherwise (going downhill). However, I am not sure whether this can be solved efficiently. I think this can be solved using binary search and SCC, but I don't know how to make sure that we don't use the same edge twice.