For implementations, see my submissions↵
#A — Serval and String Theory↵
↵
<spoiler summary="Solution">↵
It is only impossible if the number ofswapsk is 0 and r is not universal, or if r consists of only one distinct character.↵
↵
Time complexity: $O(n)$↵
</spoiler>↵
↵
#B — Serval and Final MEX↵
↵
<spoiler summary="Solution">↵
For the MEX to be 0, we must remove all 0s from the array and then apply the operation on the whole array. We cando this in one operation unless both the first and last element are 0, in which case it takes two operations.↵
↵
Time complexity: $O(n)$↵
</spoiler>↵
↵
#C — Serval and The Formula↵
↵
<spoiler summary="Solution">↵
It is always possible if x != y. WLOG, assume x>y. Note that a+b=a^b (^ is xor) if and only if the bitwise and of a and b is 0. Then, let M be the least power of 2 greater than or equal to x. Using k = M-x will set all bits in x to zero except one, and since x>y, the bitwise and of x+k and y+k will be 0.↵
↵
Time complexity: $O(1)$rremove all zeroes in one operation (with endpoints on the leftmost and rightmost zeroes) unless both the first and last element are 0, in which case it takes two operations. Once all zeros are removed, we can MEX the whole array resulting in 0.↵
↵
Time complexity: $O(n)$↵
</spoiler>↵
↵
#C — Serval and The Formula↵
↵
<spoiler summary="Solution">↵
It is always possible if x != y. WLOG, assume x>y. Note that a+b=a^b (^ is xor) if and only if the bitwise and of a and b is 0. Let M be the least power of 2 greater than or equal to x. Using k = M-x will set all bits in x+k to zero except one, and since x>y, the bitwise and of x+k and y+k will be 0.↵
↵
Time complexity: $O(1)$ (with bitwise operations)↵
</spoiler>↵
↵
#D — Serval and Kaitenzushi Buffet↵
↵
<spoiler summary="Solution">↵
Consider reversing time: we iterate over the dishes backwards, and at each move we can increase r by one or take the current dish and decrease it by k. We must end with r >= 0. We greedily eat a dish every time we can. If we ate a dish earlier but the current dish has a greater value of d[i] than it, we can replace the older dish with the current one to maximize the answer (since we can save the k for the current dish instead of using it earlier). To do this, we maintain a sorted multiset of all dishes we have taken so far. The answer is simply the sum of all elements in the multiset.↵
↵
Time complexity: $O(n\log{n})$↵
</spoiler>↵
↵
#E — Serval and Modulo↵
↵
<spoiler summary="Solution">↵
Let A be the sum of all elements in a and B be sum of all elements in B. Note that k must divide B-A. We can iterate over all divisors of this value and check each of them. This will run in time since the maximum number of divisors of B-A is less than 3000.↵
↵
Time complexty: $O(3000n\log{n})$↵
</spoiler>↵
↵
#F1 — Serval and Colorful Array (Easy Version)↵
↵
<spoiler summary="Solution">↵
Consider the middle index of the final subarray. We can iterate over this index, keeping track of the closest occurrences to the left and right for each index using sets. For each middle index, we iterate over all values 1 to k (except the value of the middle index) and choose the closest index (either to the left or right) to the middle index, or mark it as equal distance to both sides. If the number of values on both sides is equal (or differs by 1), we can update the answer with the number of required moves in this case.↵
↵
Time complexity: $O(n^2)$↵
</spoiler>↵
↵
#F1 — Serval and Colorful Array (Easy Version)↵
I did not solve this (mostly due to spending 30mins debugging F1). If you did, please post your solution in the comments.↵
↵
Overall, contest was fun and all problems were very good.
#A — Serval and String Theory↵
↵
<spoiler summary="Solution">↵
It is only impossible if the number of
↵
Time complexity: $O(n)$↵
</spoiler>↵
↵
#B — Serval and Final MEX↵
↵
<spoiler summary="Solution">↵
For the MEX to be 0, we must remove all 0s from the array and then apply the operation on the whole array. We can
↵
Time complexity: $O(n)$↵
</spoiler>↵
↵
#C — Serval and The Formula↵
↵
<spoiler summary="Solution">↵
It is always possible if x != y. WLOG, assume x>y. Note that a+b=a^b (^ is xor) if and only if the bitwise and of a and b is 0. Then, let M be the least power of 2 greater than or equal to x. Using k = M-x will set all bits in x to zero except one, and since x>y, the bitwise and of x+k and y+k will be 0.↵
↵
Time complexity: $O(1)$r
↵
Time complexity: $O(n)$↵
</spoiler>↵
↵
#C — Serval and The Formula↵
↵
<spoiler summary="Solution">↵
It is always possible if x != y. WLOG, assume x>y. Note that a+b=a^b (^ is xor) if and only if the bitwise and of a and b is 0. Let M be the least power of 2 greater than or equal to x. Using k = M-x will set all bits in x+k to zero except one, and since x>y, the bitwise and of x+k and y+k will be 0.↵
↵
Time complexity: $O(1)$ (with bitwise operations)↵
</spoiler>↵
↵
#D — Serval and Kaitenzushi Buffet↵
↵
<spoiler summary="Solution">↵
Consider reversing time: we iterate over the dishes backwards, and at each move we can increase r by one or take the current dish and decrease it by k. We must end with r >= 0. We greedily eat a dish every time we can. If we ate a dish earlier but the current dish has a greater value of d[i] than it, we can replace the older dish with the current one to maximize the answer (since we can save the k for the current dish instead of using it earlier). To do this, we maintain a sorted multiset of all dishes we have taken so far. The answer is simply the sum of all elements in the multiset.↵
↵
Time complexity: $O(n\log{n})$↵
</spoiler>↵
↵
#E — Serval and Modulo↵
↵
<spoiler summary="Solution">↵
Let A be the sum of all elements in a and B be sum of all elements in B. Note that k must divide B-A. We can iterate over all divisors of this value and check each of them. This will run in time since the maximum number of divisors of B-A is less than 3000.↵
↵
Time complexty: $O(3000n\log{n})$↵
</spoiler>↵
↵
#F1 — Serval and Colorful Array (Easy Version)↵
↵
<spoiler summary="Solution">↵
Consider the middle index of the final subarray. We can iterate over this index, keeping track of the closest occurrences to the left and right for each index using sets. For each middle index, we iterate over all values 1 to k (except the value of the middle index) and choose the closest index (either to the left or right) to the middle index, or mark it as equal distance to both sides. If the number of values on both sides is equal (or differs by 1), we can update the answer with the number of required moves in this case.↵
↵
Time complexity: $O(n^2)$↵
</spoiler>↵
↵
#F1 — Serval and Colorful Array (Easy Version)↵
I did not solve this (mostly due to spending 30mins debugging F1). If you did, please post your solution in the comments.↵
↵
Overall, contest was fun and all problems were very good.
