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:
Can 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:
For 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.
A 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$$$.
This 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
$$$S = x_1 \cdot n + D \cdot \frac{n \cdot (n-1)}{2}$$$
From 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.
If 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$$$.
Let'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?
The 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