Hola Codeforces!

The 2023 Argentinian Programming Tournament (TAP) was held last weekend. This is a 2023-2024 ICPC subregional contest for teams from Argentina to qualify to the South America/South Regional contest. You can send your solutions or do a virtual participation in the Codeforces gym. I invite you all to solve the problems.

The problems were written and prepared by elsantodel90, fredy10, Guty, lsantire, pablobce and me (MateoCV)

I would like to thank MarcosK for solving and reviewing the problems and providing valuable feedback.

Feel free to use this blog to discuss about the problems :)

Happy coding!

These were the authors of each problem:

AuthorsCan someone give me any hints on how to do A?

If we do exactly what the statement says: "for each trip go through all offices giving alfajores away and see how many are left at the end", then we end up with a $$$O(N \cdot M)$$$ solution, which is too slow. But we can improve it:

Hint 1Hint 2For each trip, then we'll do $$$O(log(10^9))$$$ operations of type $$$2$$$, and all the rest will be of type $$$1$$$. But operations of type $$$1$$$ don't do nothing, the number of alfajores left doesn't change when applying them, so we should try to come up with a way of completely avoiding them.

Hint 3A way of avoiding the useless operations would be by being able to solve the following sub-problem: "find the next office where some alfajores will be given away", i.e. assuming we are at office $$$i$$$ and we have $$$A$$$ alfajores left, find the left-most index $$$j$$$ such that $$$E_j \leq A$$$ and $$$j > i$$$.

SolutionThis sub-problem can be solved in different ways. One example is using segment tree or similar data structure. Another way is to modify the array $$$E$$$ into a decreasing array at the beginning, and then do binary search over it every time we need to solve the sub-problem.

The improved solution is then $$$O(N \cdot log(M) \cdot log(10^9))$$$

thank you so much

.

Can someone give me any hints on how to do E?

The name of the variables used below are the same as in the problem statement

Hint 1$$$S = x_1 \cdot n + D \cdot \frac{n \cdot (n-1)}{2}$$$

Hint 2From the hint above, we know the value of $$$S$$$ and we have $$$3$$$ integer variables $$$(x_1$$$, $$$n$$$ and $$$D)$$$, each of which could take $$$O(10^5)$$$ different values.

Hint 3If we iterate $$$2$$$ of those variables, then we can solve the equation and find the value of the third one, if exists. At first this is looks like a quadratic time solution, which is too slow, but we can speed this up if we carefully use the restriction of the statement saying that $$$x_i = A$$$ for some $$$i$$$.

SolutionLet's define $$$K = R-L$$$

We can iterate $$$D$$$ and $$$x_1$$$ in the following way

The check will then be done approximately the following number of times: $$$\frac{K}{1} + \frac{K}{2} + \frac{K}{3} + ... + \frac{K}{K}$$$

And this number is $$$O(K \cdot log(K))$$$ (why?)

The check could be done using the Bhaskara's formula or binary search (be careful with the overflow). And the final time complexity of the solution would then be $$$O(K \cdot log(K))$$$ or $$$O(K \cdot log(K) \cdot log(S))$$$

One more detail, be careful with the case $$$A=S$$$

Thanks

Can someone explain to me why my idea for problem G is wrong?

SpoilerThe idea is to connect each base to all other bases of lower height that do not have a base between them, and then find the minimum spanning tree of this graph.

The idea was correct, it was an implementation error, but I leave the comment in case anyone wants a hint of the solution.

Can someone give me any hints on how to do H?

Can someone give me any hints on how to do N? Please

Can someone give me any hints on how to do I?

Use the fact that (T+C)(Q+C) <= 10^6, i.e T*Q + C*T + C*Q + C*C <= 10^6. If you can calculate distance between a pair of figures in O(1), you can calculate for any circle the distance to any other figure and also the distance between every pair (triangle, square). Think how can you solve the problem with these data.