Hi,

The 2019 ICPC Mexico Finals starts in 30 minutes.

Let's discuss the problems after the contest.

There are some mirror contests starting 1h after the real one:

- https://www.juezguapa.com/concursos/icpc-latin-america-2019-final-official-mirror
- https://matcomgrader.com/contest/overview/6254
- https://www.urionlinejudge.com.br/judge/en/contests/view/496

This facebook page is posting updates frequently: https://www.facebook.com/acmitesochapter

Streaming:

- From Universidad de Oriente de Santiago de Cuba (Spanish): https://www.facebook.com/icpc.caribbean.media/videos/433791383990095/

Good luck to all the teams.

**UPDATE** The contest has started.

**UPDATE** Live scoreboard: https://global.naquadah.com.br/boca/score/index.php (use this if the previous one doesn't work https://global.naquadah.com.br/boca/scoreglobal.php?h=AT2oE0HBeAg8eox30q5wZOdk8SY_bIZ-hGKuX9OTrY661HqiWgHRra4KBYyrxV6IDqZeTVr7yJ6EpBVje50BxzQBkGZoTKMNPwb3UZpD_G79M9PmveqUhUUrtO04BJUpMwqPvrz_7o-QWTc)

**UPDATE** Problems available:

- https://matcomgrader.com/media/contests/6254/A.pdf
- https://matcomgrader.com/media/contests/6254/B.pdf
- https://matcomgrader.com/media/contests/6254/C.pdf
- https://matcomgrader.com/media/contests/6254/D.pdf
- https://matcomgrader.com/media/contests/6254/E.pdf
- https://matcomgrader.com/media/contests/6254/F.pdf
- https://matcomgrader.com/media/contests/6254/G.pdf
- https://matcomgrader.com/media/contests/6254/H.pdf
- https://matcomgrader.com/media/contests/6254/I.pdf
- https://matcomgrader.com/media/contests/6254/J.pdf
- https://matcomgrader.com/media/contests/6254/K.pdf
- https://matcomgrader.com/media/contests/6254/L.pdf
- https://matcomgrader.com/media/contests/6254/M.pdf

**UPDATE** Official results are ready: http://scorelatam.naquadah.com.br/

Congrats to the winners!!!

**UPDATE** These are the teams going to the world finals, there were 4 extra spots:

```
- UH++,CUBA
- Limitless, CUBA (new)
- Norman is Hunting, MEXICO
- E3, MEXICO
- #define TriLCI(404.0) :v, MEXICO
- pu+os, MEXICO (new)
- Guerreros de RodriGOD, COSTA RICA
- InChaVoLa, ARGENTINA
- GG Dem, ARGENTINA
- #NuevaConstitución UChile1, CHILE
- Rating MiSeRable, PERU (new)
- descomUNAL, COLOMBIA
- La bomba de tenedores, VENEZUELA
- Time com T, BRASIL
- Campinas Grande, BRASIL
- Amigos do Beto, BRASIL
- Rock Lee do Pagode Namora D+, BRASIL
- Rábalabaxúrias, BRASIL
- Triple G, BRASIL (New)
```

Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).Is there another way to solve K problem avoiding FFT?

Sure, naive multiplication does the job pretty well here. Expected complexity in this problem is $$$O(n^2)$$$.

We tried FFT with divide and conquer but the precision error is too big to handle up to 2^63 -1. In the end 10^4 for 0.1 seconds troll us :P

Because of the 2^63-1 constraint, the real limit is actually $$$n \le 16$$$. So you can do multiplication as slowly as you want...

:O i am dumb

In problem E we have to create a List with all the positions of E from 0 to n+s

Then we need to iterate the string if the position has an E, then we sum S to the ans if not we look for the closest E to this relative position and if its distance is less than S we add (s — distance from the closest E) to the answer.

Code for preview:

CodeCan someone please tell me why this solution for I is wrong? https://ideone.com/61vnoj

If a client i is sent an email k*(1e9 + 7) times, dp[i] is zero, but that client still needs to be counted towards the "number of emails after the improvements".

You should count separately the number of messages before the optimization and after the optimization because of the mod. Test case that breaks this solution was added one day before the competition.

How to solve G and F ?

Problem G could be easily solved with Suffix Automaton, you could build a Suffix Automaton of S in $$$O(n*log(n))$$$ and then for each query start at the root of the automaton and do the following:

If there is a transition from the current node with the current letter of the query, move through it.

Otherwise, if you are not on the root, go to the root and add $$$1$$$ to the answer, if you are on the root, then the answer is $$$-1$$$.

For Problem F, you have to solve the problem recursively. Consider you'll be putting floors from bottom to top, if you have $$$s$$$ remaining blocks and the last floor you put had $$$n$$$ blocks then the number of ways to put the rest is:

This is, if the next floor doesn't start in the first block of the last floor, then there are $$$dp(s, n-1)$$$ ways to put the rest, otherwise, you can pick any valid size for the next floor and you know where it will be.

This is $$$O(n^3)$$$ if implemented naively, but it can be optimized to run in $$$O(n^2)$$$ by pre-calculating some sums.

Another way to look at F is the following. First, you can ignore the first level (from the bottom upwards) of blocks. Let DP(s,b) be the number of ways to put the remaining blocks. To calculate this you look at three cases: - The first level of blocks is full - The first stack is empty - The last stack is empty

You can calculate the first case by simply ignoring s blocks. The second and third case are analogous, and you can calculate them by ignoring one stack. However, the cases eventually overlap, since the scenario where both the first stack and the last stack are empty can be reached from both cases. This can be solved by subtracting the value for the overlap. This is the formula:

DP(s,b) = DP(s,b-s) + 2 * DP(s-1,b) — DP(s-2, b).

In general I think it was good that problem-setter name was removed from each problem (I used to check the name of the problem-setter to try to guess complexity). Although, after reading problem C I feel bad the authors are not getting any recognition, very creative statement indeed.

Makes sense that the same guy proposed the two most interesting and brutal problems in the contest. Kudos to him.

In case you are referring to the first two problems here is an outline of the solution:

Problem A: build the graph where every possible set is a node, and there is a directed between A and B if B contains exactly one element more than A. This is of course a DAG and we need to find maximal anti chain here. Applying Dilworth to this graph is enough to find the solution. Notice that number of edges in the transitive closure is at most $$$N \cdot 3^K$$$.

Problem B: Every point can be rotated 90 degree several times without affecting the answer. Do this until every point is in the first quadrant. Let's find where is the corner of the optimal square in the first quadrant. Binary search over the length of the diagonal (it is proportional to the perimeter) and try to find a rotation of the square such that it doesn't contain any point. Each point will give you a possible interval to rotate the square. Find if the intersection of all intervals is not empty. The time complexity was $$$O(\log(-PREC) \cdot \log n \cdot n)$$$.

There was also a beautiful solution for this problem with expected complexity $$$O(n)$$$, similar to the algorithm that find minimal enclosing circle. Random shuffle points at the beginning, and try to find a valid square for all prefix. Suppose you have a maximal square for first $$$x$$$ points, if point $$$x+1$$$ is outside this square, no action needs to be taken, otherwise, recompute the square, but letting this point belonging to one side of the square. This solution is a little bit trickier to implement, since a pair of point can define two possible maximal (not both maximum) squares.

Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).Bonus: Can you solve problem D in $$$O(n \cdot log n)$$$.

HintTry to solve it first for the case where all brightness are different.