Hello everyone! I found some problems of the practice contest quite interesting, and I decided to share what I have done to solve them.

Update: The official solutions are available here.

Gift

First, we have to observe that if $$$x[i] = 2 (\forall 0 \leq i \leq n-1)$$$, then we can alternate between red and blue. For example, $$$answer[0] = 'R', answer[1] = 'B', \ldots$$$. This way, any interval of type 2 with a size larger than 1 is satisfied. So if there is a type 2 interval of size 1 the solution must return 0.

Each element in the same type 1 must be the same ('R' or 'B'), but there are overlapping intervals of type 1, which all must be of the same color. For doing that I sorted all the type 1 intervals according to their first element in non-decreasing order, then I iterated for each interval in the sorted vector comparing it's first element with the largest last element of the previous intervals, and in the case of being lower or equal I "mixed" both intervals into one and stored it in another vector of pairs, where the first element of each pair is the last element of the interval ans the second element is the first element of the interval (to run binary search on it later). This takes $$$O(n \log{n}) + O(n)$$$ time.

Now, it is possible there's a type 2 interval completely inside a type 1 interval or a "mixed" interval, and in that case we have to return 0. For each type 2 interval we run a binary search to find the "nearest" type 1 "mixed" interval (the one with the minimum last element larger than the one of the type 2).

Finally we "paint" each block alternating between red and blue as follows: keep an index of the current "mixed" interval. Iterate for each block: if it's inside the current "mixed" interval and the previous block too, paint the current block with the same color you painted the previous one, else paint it with the other color. After all of that call $$$answer$$$ with the final string.

Total running time for this full solution is $$$O(n \log{n})$$$.

Squares

For the first subtask we can set $$$k = 1000$$$ and in each query, the answer will be the number of $$$-1$$$ of the given array.

For a better solution, we must notice each subarray (of std::vector labels) of size $$$k$$$ must be different to every other subarray of size $$$k$$$. The idea I had is to iterate for each element of labels from $$$k$$$ to $$$n-1$$$ (inclusive) and put $$$0$$$ unless is necessary to put $$$1$$$, that is, when the first or second element of such sub-array is $$$1$$$, because if we put $$$0$$$ in that case we aren't going to increase the number of $$$1$$$s in the next iteration, a necessary datum for finding $$$x$$$ later.

After doing what I explained in the last paragraph, our subarrays should look like that: $$$[0, 0, \ldots, 0], [0, 0, \ldots, 1], [0, 0, \ldots, 1, 0], \ldots, [0, 1, \ldots, 0, 0], [1, 0, 0, \ldots, 1], [0, 0, \ldots, 0, 1, 1], [0, 0, \ldots, 0, 1, 1, 0], \ldots, [1, 1, \ldots, 1, 1]$$$. Note that with this methods we're gonna have $$$k-1$$$ different sub-arrays of size $$$k$$$ with $$$m$$$ $$$1$$$s, for each $$$m$$$ from $$$1$$$ to $$$k-1$$$, so tthis method works for an array with size less than $$$(k-1)^2$$$, which is enough for subtasks 1, 2, and 3.

In each query, we first look for the index of the first $$$-1$$$ in the input vector. Being $$$i$$$ such index if it exists, we return $$$n-i$$$. Else we continue counting the number of $$$1$$$s. Being $$$m$$$ such number we return $$$m*(k-1) + k-j$$$ where $$$j$$$ is the index of the first $$$1$$$ after a $$$0$$$.

Please write the full solution in the comments below, because I didn't find it.

Update (full solution): The main idea is to create an array $$$p$$$ of $$$0$$$s and $$$1$$$s of size $$$n$$$ such that every sub-array of size $$$k$$$ is unique. We can store the starting position of every possible sub-array in another array of size $$$2^k$$$ (with $$$k = 10$$$ if we want to get full score), accessing the indexes of that array using bit-masks. For example, let $$$r$$$ be the position array, $$$r[11]$$$ stores the position of the sub-array $$$[0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0]$$$. In that way, is enough to "translate" the input array in find_location to an integer $$$val$$$ (in this case, a bit-mask) and return $$$r[val]$$$, but first is necessary to check if the input array has some $$$-1$$$. Now you may be asking, how to generate $$$p$$$ in first place?

That problem is equivalent to building a De Brujin sequence with $$$A = {0, 1}$$$. You can read the G4G article if you want more details, but in summary we can do it by constructing an implicit directed graph such that each node represents a sub-array of length $$$k-1 = 9$$$ (again, is better to use bit-masks rather than vectors) and has two edges: one representing $$$1$$$ and the other representing $$$0$$$. Each of them "adds" its associated number to the original sub-array, and "eliminates" the first one. Note that both the in-degree and the out-degree of each vertex is equal to 2, so we can run a modified DFS to find an Eulerian circuit while storing the number associated with each node traversed (representing a sub-array) and after that create the sequence from the Eulerian Circuit. For more details you can check the official solution.

Routers

In this problem we have to implement binary search to find the location of routers in $$$O(\log{l})$$$ time each one. This works for Subtasks 1 and 2.

For reducing the number of queries when looking for the location of each router, I stored in a vector the minimum location where $$$use detector(x)$$$ appears each time I called $$$use detector$$$. In that way, I for each router $$$i$$$ I iterated for each element of the vector until I find an element and set the right bound of the binary search with that element. I also set the left bound with the position of the last router "discovered" plus one. Reducing the space search in that way I could get like 37 of 40 points.

Jelly

First of all, this is an optimization problem, because we have to maximize the different number of flavours we can buy with the given constraints. This is important, considering that we know we may approach the problem with dynamic programming or binary search, for example, depending on the constraints.

The source code of my solution can be found here. Feel free to download it and view it on your favourite text editor since it doesn't look well on the webpage.

Subtask 1

One of the most accurate ways to find the best answer is to try all possible combinations and then select the best of them. In this case, we can write two nested loops with $$$i$$$ and $$$j$$$, bit-masks representing the flavours we buy in Store A and in Store B, respectively (if a bit $$$k$$$ is equal to $$$1$$$ then we buy flavour $$$k$$$). In each iteration, we must check that the sum of costs of flavours bought don't surpass our budget ($$$x$$$ in the case of Store A, and $$$y$$$ in the case of Store B). After that, we update the answer variable if appropriate.

The time complexity of this solution is $$$O(n2^{2n})$$$, so it passes the system testing because in this subtask $$$n \leq 12$$$.

Subtask 2

The complete search approach described above won't work in this subtask because this time $$$n \leq 200$$$, but we can apply dynamic programming with a 3-dimension DP table. $$$dp[i][j][k]$$$ is the answer for the first $$$i$$$ flavours with $$$j$$$ budget in Store A and $$$k$$$ budget in Store B. We initialize the table with all values equal to $$$0$$$. After that, we iterate the table and updating each element with the maximum answer between not buying flavour $$$i-1$$$ ($$$dp[i-1][j][k]$$$), buying it in Store A ($$$1+dp[i-1][j-a[i-1]][k]$$$) and buying it in Store B ($$$1+dp[i-1][j][k-b[i-1]]$$$). After all iterations we return $$$dp[n][x][y]$$$ (I guess you realize why).

The time and memory complexity of this solution is $$$O(nxy)$$$, which is more or less $$$O(n^3)$$$.

Subtask 3

In this subtask, we have no budget for Store B, so unless flavour $$$i$$$ is free in Store B ($$$b[i] = 0$$$), we have to buy it in Store A. Of course, is convenient for us to buy the cheapest flavours possible to save money and buy the biggest quantity possible. We create another vector $$$c$$$ such that $$$c[i] = (a[i], b[i])$$$ and then sort it. Then we iterate $$$c$$$ from $$$0$$$ to $$$n-1$$$ adding $$$1$$$ to the answer each time we find a free flavour or a flavour that we can buy in Store A. We have to update our budget each time we buy some flavour in Store A.

The time complexity of this solution is $$$O(n lg n)$$$ or $$$O(n)$$$, depending on how we sort $$$c$$$.

Subtask 4

The solution for this subtask is like the one for the previous one but this time we only need to sort $$$a$$$, iterate it buying all flavours possible until we can't continue buying in Store A. Then we continue buying in Store B until buying all $$$n$$$ flavours or finishing with our budget for both Stores.

The time complexity of this solution is $$$O(n lg n)$$$ or $$$O(n)$$$, depending on how we sort $$$a$$$. Note is not necessary to sort $$$b$$$ since all elements in $$$b$$$ are equal.

Subtask 5

We have to note if we can buy $$$i$$$ flavours, then we can buy $$$i-1$$$ (if and only if $$$i > 0$$$) and if we can not buy $$$i$$$ flavours, then we can't buy $$$i+1$$$. Thus, we can implement a complete search solution trying to buy different flavours until we can't continue.

First, we have to sort $$$a$$$ and $$$b$$$ to select the cheapest flavours possible. Then we buy all possible flavours in Store A starting from 0 all possible flavours in Store B starting just after the last flavour we couldn't buy in A. After that, the idea is to "change" stores: instead of buying some flavours we already bought in A, we try to buy them in B (we can do it by iterating backwards, if $$$i$$$ is the flavour to buy, then we iterate from $$$i-1$$$ to $$$0$$$). This way, we can have more money to buy the next flavour in Store A. If that is not enough, then we reverse the change and we try to buy some flavours we already bought in B in Store A to save money to buy the next flavour in Store B. If even that is not enough, then we stop and return the number of flavours we could buy.

The time complexity of this solution is $$$O(n lg n)$$$ or $$$O(n)$$$, depending on how we sort $$$a$$$ and $$$b$$$.

Subtask 6

First we create $$$c$$$ such that $$$c[i] = (a[i], b[i])$$$ and we sort $$$c$$$ in non-decreasing order. Also, we maintain two different 2-dimensional arrays or vectors, $$$dp0$$$ and $$$dp1$$$, $$$dp1[i][j]$$$ stores the maximum number of flavours from $$$i$$$ to $$$n-1$$$ we can buy in Store B with $$$j$$$ amount of money and $$$dp0[i][j]$$$ stores the minimum amount of money we need to spend in Store B to buy all flavours from $$$0$$$ to $$$i-1$$$ (inclusive) with $$$j$$$ amount of money. The idea of this is not having to decide between buying in A or in B because doing that would consume too much memory, since $$$x, y \leq 10000$$$. Also, since $$$c$$$ is sorted for Store A we know is cheaper to buy flavours with smaller numbers in the sorted $$$c$$$.

Thus, we can fill $$$dp1$$$ like in the knapsack problem but each flavour has a value of $$$1$$$, and $$$dp0[i][j]$$$ as the minimum between $$$dp0[i-1][j]+c[i-1].second$$$ (buying flavour $$$i$$$ in Store B) and $$$dp0[i-1][j-a[i-1].first]$$$ (buying flavour $$$i$$$ in Store A if we have enough money). After filling both tables, we iterate from $$$0$$$ to $$$n$$$ (inclusive) looking for the answer: if $$$i$$$ is our iterator, then we consider buying $$$i$$$ flavours plus the maximum number of flavours we can buy only in Store B from $$$i$$$ to $$$n-1$$$ with a budget of $$$y-dp0[i][x]$$$.

The time and space complexity of this solution are something like $$$O(n^2)$$$.

Now this "editorial" contains all problems, but some of them are poorly explained. Please comment if you want me to continue improving this, or ignore if you don't care.