I know this round is from like 2-3 months ago but screw that, let's dig it up because I just solved it recently. Also I cannot see any people who are doing the same thing as me.

1) The problem statement:

Problem link: 2003F — Turtle and Three Sequences

Given two positive integers $$$n$$$, $$$m$$$ ($$$n \geq m$$$), and three sequences $$$a$$$, $$$b$$$, $$$c$$$ of size $$$n$$$. Find a sequence of length $$$m$$$ $$$p_1, p_2, ..., p_m$$$, such that $$$p_1 < p_2 < ... < p_m$$$, and $$$a_{p_1} \leq a_{p_2} \leq ... \leq a_{p_m}$$$, and $$$b_{p_i} \neq b_{p_j}$$$, $$$\forall i \neq j$$$.

Constraint:

• $$$n \leq 3000$$$, $$$m \leq 5$$$.
• $$$1 \leq a_i, b_i \leq n$$$, $$$1 \leq c_i \leq 10^4$$$.
• Time Limit: 3 seconds.

You can read the intended solution in this link: Editorial.

I would recommend you to try the problem out before scrolling further (or just don't, because the problem is rated 2800, so if you are a fellow blue hardstuck-er then you don't really stand much of a chance anyway).

2) My solution:

Prerequisite:

• Fenwick Tree.
• Constant optimization skill.

It would be best if we start from something manageable first. $$$m \leq 2$$$ is pretty simple, you literally just have to brute, it literally cannot get any easier than this, so let's move on.

For $$$m = 3$$$, it is more challenging, but you can solve it by iterating through all pair $$$(i, j)$$$ $$$(i < j)$$$, and for each pair, find the best index $$$k$$$ to the left of $$$j$$$ in $$$O(n)$$$, so the total complexity is $$$O(n^3)$$$. To optimize this, observe that we don't really need to keep track of that many $$$k$$$. We only need to maintain an array $$$suff_j$$$, containing up to $$$m$$$ candidate tuples $$$(a_k, b_k, c_k)$$$ with the largest $$$c_k$$$, such that $$$k > j$$$, $$$a_k \geq a_j$$$, and all $$$b_k$$$ are distinct (because at worst, we only have to skip $$$m-1$$$ candidates of the $$$m$$$ tuples). We can precalculate $$$suff_j$$$ in $$$O(n^2)$$$, so the final complexity for $$$m = 3$$$ is $$$O(n^2*k)$$$.

$$$m = 4$$$ is pretty much the same thing, except you have to also maintain the array $$$pref_i$$$, which contains up to $$$m$$$ tuples $$$(a_k, b_k, c_k)$$$ with the largest $$$c_k$$$, such that $$$k < i$$$, $$$a_k \leq a_i$$$, and all $$$b_k$$$ are distinct, then iterate through all pair $$$(i, j)$$$ just like the previous algorithm and iterate through all the candidate tuples in $$$suff_j$$$ and $$$pref_i$$$. The complexity of this is $$$O(n^2*k^2)$$$.

$$$m = 5$$$ is pretty tough, however. Previously, calculating $$$m^{th}$$$ best candidate to the left of $$$i$$$ and to the right of $$$j$$$ is pretty easy, but how do we take it a step further? Iterating through all the possible pairs of candidates (not just candidates, pairs of candidates) to the left of $$$i$$$ or to the right of $$$j$$$ is pretty infeasible, so we only have one choice: maintaining the array $$$between_{i, j}$$$, containing up to $$$m$$$ tuples with the largest $$$c_k$$$, such that $$$i < k < j$$$, $$$a_i \leq a_k \leq a_j$$$, and all $$$b_k$$$ are distinct.

We can use data structures used to solve range maximum queries like Fenwick Tree to calculate this array. Here's how: for each $$$i$$$, iterate $$$j$$$ from $$$i+1$$$ to $$$n$$$. For each $$$j$$$, get $$$m$$$ candidate tuples such that $$$a_k \leq a_j$$$, then update the Fenwick Tree with the tuple $$$(a_j, b_j, c_j)$$$. Once you obtained the three arrays, you just do the same this as the previous subtask, except you also iterate through the $$$between_{i, j}$$$. The complexity of this is $$$O(n^2*k*(k^2+log(n))$$$.

As the complexity might suggest, you indeed have to go pretty crazy on the constant optimization here (probably anything other than Fenwick Tree won't even pass, who knows, my program runs in 2.93s, which is like one Minecraft tick away from getting TLE).

Can we extend this for $$$m = 6$$$? Nope, I think I've pushed this idea to its limit already. Which is scary to think about, because author set the constraint on $$$m$$$ precisely equal to $$$5$$$, while the intended solution can go beyond that. Does the author know about this solution, so they set $$$m = 5$$$? And if yes, why don't they just write this solution into the editorial? Guess we'll never know.