...And a year has gone by without me writing any post.

This year I wrote a bunch of problems. Yet, there were none that I think is interesting. In total, I wrote 14 problems. 2 were unused, and 1 problem I wrote last year is finally used. So basically I published 13 problems. The breakdown is:

• 2 problems for CS2040C (module I TA-ed in NUS)
• 7 problems for Gemastik (preliminary + final)
• 4 problems for ICPC Jakarta (INC + ICPC)

As I mentioned before, I don't think any of them are pretty interesting. By interesting, I mean I don't feel "smart" for coming up with them. However, if I have to choose which one is the most interesting, it would be either Menghitung Pohon String (Gemastik final round), Pendakian Gunung (Gemastik preliminary round), or Short Function (ICPC Jakarta 2022).

Just like last year, I would talk about problems that I published this year. Maybe how I came up with them, solutions for them (if they don't have editorial and I can discuss them), stories regarding those problems, etc. There is no particular order here, I just write them randomly. However, I would group problems which are similar, in a sense that when I developed them, they are basically just a variation of each other.

I didn't realize this when I was writing this post but heck, this post is pretty long. Anyway, enjoy.

Gemastik 2022 Preliminary D - Array K-Cantik

Problem link: Here
Editorial: Same link as above

I first came up with this problem when I brainstormed for CS2040C problem. Originally, $K$ is a part of the input, so we only need to solve for a fixed $K$. However, when Steven tested it, he deemed it too hard for CS2040C. Then I need to come up with easier problem within 1 week :s Luckily I did it...

Anyway, after that I realized that it's possible to solve this problem for all $1 \leq K \leq N$, so I decided to "upgrade" the problem. Also, it is easier to make the test case for the upgraded version :P During the contest, I think none of the teams who got AC actually submitted the intended solution. IIRC, all of them use some sort of ternary search, though I could be wrong. I haven't checked whether ternary search can correctly solve this problem, though.

CS2040C - Array Smoothening

Problem link: Here
Editorial: None

Cannot discuss this problem as Steven might reuse this in the next iterations of CS2040C ><

This is the problem I came up with as the replacement for Array K-Cantik. I still think that this problem is too easy, but this was the difficulty that Steven wanted. Anyway, it's a simple problem that tests your greedy intuition.

CS2040C - Building Highways

Problem link: Here
Editorial: None

Cannot discuss this problem as Steven might reuse this in the next iterations of CS2040C ><

This might be controversial but I actually have used this problem before. Back then, I used it for internal contest in Ristek UI. I decided that it is still fine to reuse this as 1) the contest is internal, so only very few people have read this, and 2) the internal contest is pretty old, I think we did it around 2018.

I actually like problem with special properties like this. While the solution is usually not generic, tackling problems like this can feel satisfying, at least for me. Anyway, while this looks like a graph problem, the solution is deceptively simple :)

Note: quite coincidentally, a "buffed-up" version of this problem appeared in this year's OSN (Building Bridges). However, I think neither me nor the writer of this problem are aware of each other's problem :P Also, while I say that this one is a "buffed-up" version, the problem is pretty different. It just has the same "spirit" as this one (lol idk what I'm writing here).

Gemastik 2022 Final G - Menghitung Pohon String

Problem link: Here
Editorial: Same link as above

Yeah, this is a variation to Rekonstruksi Pohon String I wrote last year. Actually, I submitted this to ICPC Jakarta last year. Initially, it was going to appear in INC. However, during testing, the problemset was deemed to hard. In order to balance things a bit, the scientific committee (SC) decided to throw away one problem. And it was this one :')

While Rekonstruksi Pohon String is not really hard, I felt this one is pretty hard. For comparison, Rekonstruksi Pohon String took me around 5 minutes to solve (idea.txt wise), while this one probably took me around 1.5 hours (3 sessions of cycling around my home in Bontang). Back then, I wanted to submit this to KSN, but decided not to because

1. The subtasks are janky,
2. I have to retract Rekonstruksi Pohon String from Gemastik as the SC of KSN may participate in Gemastik, and
3. Prabowo thought this problem is too hard. IIRC back then he cannot solve it.

I think the interesting part of this problem is that the relation of edges (check the editorial to see what I meant) is already fixed by the input. Hence, while this kind of problem smells like a DP problem, it is not. In fact, it can be solved by DFS + combinatorics only. However, I kept the constraint of $K$ to be up to $26$ to make the problem more natural. Yet, if I can revise this problem, I think I would add new constraint which enforce the input $A$ to be valid (i.e there is at least one valid assignment). It would simplify the problem a bit and made the solution a bit cleaner.

ICPC Jakarta 2022 E - Substring Sort

Problem link: Here
Editorial: Same link as above

I made this when I brainstormed for CS2040C problem. Yes, you are reading it right. Who the hell came up with this abomination when trying to write a problem for a data structure & algorithm course taken by undergrad students.

Originally I thought I can just store for each pair of strings, in which indices do they differ. Well, at this point I already know that this is not suitable for CS2040C. Then I realized how wrong this solution anyway, as the sorting process may invalidate the indices.

After that, I thought "ah, probably I can make segment tree to work here". But no, I cannot come up with reasonable solution using segment tree. Then, what about sqrt decomposition? Thinking a bit, I felt it might work. While I don't have the concrete idea, storing the comparison result in each block and manually comparing for prefix/suffix which do not fully fit in a block should work. One thing I would praise here is the ability of the ICPC Jakarta's SC to understand my high-level idea of the solution that I submitted. Everytime I read it, I feel like I am reading a garbage :')

Do I like this problem? Idea-wise, maybe, but not so much. Would I implement the solution for this problem? Probably not. I haven't really work on the detail, so whatever is in my mind right now looks complicated. However, Prabowo told me their official implementation is not that lengthy. Hopefully it is true.

Gemastik 2022 Preliminary I - Mengurutkan Karakter

Problem link: Here
Editorial: Same link as above

In my attempt to simplify Substring Sort, I thought "what if there is only two strings?". Then, the problem becomes quite simple: store the differing indices, and use a data structure which supports update and range sum query (RSQ). After that, for each query, find the nearest differing index, and find which one is smaller. To flip the substring, use the RSQ data structure.

However, "what if I want to sort the character in each index?". Boom, this problem was born.

While my greedy intuition already told me the solution for this problem, somehow it took me a while to prove why it is correct. After that, I rewrote the operation a bit to make it easier to understand (swap instead of sort). Overall, I think this is a classic greedy problem, but I think it is fine for an easy problem.

ICPC Jakarta 2022 D - City Hall

Problem link: Here
Editorial: Same link as above

I was trying to think of shortest path version for a problem I wrote last year. To make it a bit different, I just changed the metric. One nice thing about quadratic function is that it is easy to find the optimum point. While they are fundamentally different, this problem kinda reminds me of another problem I wrote back then in 2020.

An interesting part of this problem preparation is determining "what kind of answer we should accept?" If we use the traditional "answer with relative or absolute error within some epsilon", then this might be bad when the answer is very huge. Back then I suggested to have the height to be a multiple of $2$ or just print up to two decimal digits, however the concern from the SC was that it might hint the solution. There was also concern with the current setting (absolute error only), as it seemed to be rare to have this kind of setting. As it turns out, some ICPC WF problems also have this kind of setting, so we settled on absolute error only.

Gemastik 2022 Preliminary B - Pendakian Gunung

Problem link: Here
Editorial: Same link as above

A natural follow up from City Hall is to find the shortest path to all vertices. However, I cannot come up with any idea. Then, I "relaxed" the problem a bit by changing the metric into absolute value. This time, it is possible. I quickly came up with the idea of constructing a graph with height information attached to each vertex, which is also described in the editorial. Note that this works as $|a-b| \leq |a-c| + |c-b|$, where equality happens only if $\min(a, b) \leq c \leq \max(a, b)$, which happens if we choose the optimal height.

ICPC Jakarta 2022 K - Short Function

Problem link: Here
Editorial: Same link as above

Back then, I had a chat with Prabowo and he said that they still need a lot of problems for ICPC Jakarta. Thus, I began to write some random functions, before stumbling upon this one. It was easy to solve this up until the part where I realized I need to calculate $\lfloor 2^K/N \rfloor \bmod M$ for some $M$ (in the case of this problem, $MOD-1$). I checked with Prabowo, and he said that if $M$ is prime, we can just rewrite this into $(2^K - (2^K \bmod N)) \cdot N^{-1} \bmod M$.

However, $M$ is not prime. Thus, I am back to scratching ideas on my vscode. Yes, I am too lazy to grab a pen and paper. Then, I thought "yeah, maybe I can just modify the multiplication". Wrote some Python code to verify, and yes, it worked. By the way, the multiplication I mentioned here is sort of described in the editorial, where it was mentioned that we can represent an integer with two integers $p$ and $q$. Then I submitted this problem to ICPC Jakarta.

When I submitted this problem, the mod is originally $10^9+7$. However, I realized that with this mod, there is an easy solution to calculate the expression above. This is because $10^9 + 6 = 2 \cdot 500\;000\;003$. As $500\;000\;003 > N$, we can reduce the problem into the case where the mod is prime. So I checked with the SC, and they said they will change the mod to the FFT mod anyway. This one can't be cheesed like before.

During testing, some of the testers found a different solution which requires 128-bit integer. Note that technically, GCC already supported 128-bit integer (__int128). I haven't really understood the solution, but it looks correct.

INC 2022 K - Permutation Construction

Problem link: Here
Editorial: None, described below

There are several ways for me to come up with problems:

• observe something in real life and try to make a problem out of it
• doodled and somehow it turned into a problem
• misunderstanding a problem into a brand new problem
• invert an existing problem
• etc, etc

This one is actually an invert of a question from CS2040C midterm paper (see the last question, Find Next Larger). The funny thing is, even Steven did not realize that this is the inverse of that problem.

My solution for this problem is to do topological sorting. If $A_i = -1$, I will make edges from $i$ to $i+1$, $i+2$, $\dots$, $N$. Else, I will make edge from $A_i$ to $i$ and from $i$ to $i+1$, $i+2$, $\dots$, $A_i - 1$. To tackle the $O(N^2)$ edges, I compress the edges into ranges. Then, I do BFS-like toposort using segment tree which supports RSQ and searching for lowest index with minimum value (in this case, $0$). This solution runs in $O(N \log N)$, which is still reasonable.

When I wrote this problem, I suspected that there should be a much simpler solution. Nonetheless, even if there is, I think this problem is still not so simple, and would still make a fine problem in INC. Note that because this problem is technically a variation of CS2040C problem, I specifically asked the committee to not put this problem in ICPC Jakarta. Just in case NUS decided to compete in ICPC Jakarta.

Note: I remembered that I was sick when I submitted this problem to ICPC Jakarta, that the short description was very messy and the samples were wrong. Thanks Rafael for following up.

Gemastik 2022 Final D - OR dari Subhimpunan

Problem link: Here
Editorial: Same link as above

Huh, I cannot remember much about this problem... I think I was reading some COMPFEST problem (?) Nevertheless, I think this problem is not too hard. The problem is pretty standard, as observations for bitwise operations are pretty well-known by now. However, during the actual contest, the number of AC is not too many.

Gemastik 2022 Preliminary H - Soal Query Digit

Problem link: Here
Editorial: Same link as above

Really, I cannot remember how I came up with this problem. I guess I was trying to make a stupid query problem, and this just popped up.

Apart from my solution which I described in the editorial, I think I saw several other solutions. At least, I know Prabowo and Ricksen's solution were different. For example, there was a solution where each node stores the contribution of a digit (i.e what is the contribution of $1$, $2$, $3$, and so on).

Perhaps I should have set the time limit to 2s instead of 1.5s. Now that I see it again, it looks ugly. Anyway, if I used the rule "2x solution time", the time limit would be 1s, in which there will be much more TLE. Luckily I decided that 1s would be "too strict", and it turned out to be true. I think a bunch of solutions have $O(\log N)$ time complexity per query, but their time is somewhere between 1s and 1.5s. Even I don't like it if constant factors matter in a CP contest.

Gemastik 2022 Final J - Jika Saya Menyebutkan X, Maka...

Problem link: Here
Editorial: Same link as above

The inspiration for this problem came when I watched this video from DougDoug. My original solution was the Aho-Corasick based solution which I briefly mentioned in the editorial. Initially I thought that this problem is hard, but then I realized there is a simpler solution using Suffix Array. Only one team solved this problem tho, so maybe it is still hard... albeit I think the scoreboard of Gemastik do not really reflect the difficulty of the problem.

There was an issue with this problem where the sample in the description was wrong. Initially, the words used in sample were "makam" and "mama", before I changed them into "merem" and "meme" because well... the previous words just seemed so wrong to be used together. Then I manually changed the sample in the description, which turned out to be a disaster. The testcases are still correct, and luckily at the point some teams pointed that the sample was wrong, not many teams have attempted this problem.