Hi,
Today was held the Latin America Regional Contest.
The problem set can be found here (sadly it requires an account): https://www.urionlinejudge.com.br/judge/en/challenges/contest/211 The results can be found here: http://score.acmicpc-latam.org/
Congrats to the winners!
- 1st — UH++ (Cuba)
- 2nd — PUMMAS (Argentina)
- 3rd — [UFPE] 0xE (Brazil)
- 4th — UNICAMP] Veni Vidi Codi (Brazil)
- 5th — PUCP-FCI O(1) O(n) O(u(n)) [Peru]
Problems can be found here: https://www.urionlinejudge.com.br/judge/en/challenges/contest/211
How to solve C?
The angle of rotation can only be 90, 180 or 270 degrees.. The reason is that every point in the set must be vertex of a regular polygon (not necessarily the same). Now the only regular polygon with all is point with integers coordinates is a square. Knowing this the problem become much simpler. The rest is counting.
A further simplification is that squares can be considered as two diagonals, so you only need to consider
.
So this 5 teams will go to WF?
As far as I know, it depends on the spots given to each region.
The contest was held on several sites. The champion of each site is guaranteed a spot in the World Finals, the others must wait for the distribution of other spots, but surely will be more than 5 teams from LATAM going to WF (for instance, this year (season 2015-2016) there were 6 Brazilian teams, which means many more LATAM teams were there).
Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).
how can we solve problem B ?
You can take the whole graph and remove the nodes that don´t satisfy the necessary condition. You can detect this nodes easily using structures from stl like set and updating neighbours of the removed node storing the degree of every node. The remaining graph is the answer to the problem.
Why is this correct? The only proof required is: if we extract a node at some point there is no answer containing this point. So the remaining graph is a maximal graph satisfying "the condition".
PDF version of the problems can be found at http://maratona.ime.usp.br/resultados16/contest.pdf
Problems were opened for submission: https://www.urionlinejudge.com.br/judge/pt/problems/origin/136
A brief solution description to all problems of this contest:
A: easy one.
B: detect and delete all invalid vertices until not found. This can be optimized by data structures, for ex., priority queue.
C: Only need to consider alpha = 180 degree. So it's enough to consider center = all mid-points of line segments with vertices in input points.
D: The best permutation is like this(for ex. n=9: 2 4 6 8 9 7 5 3 1). This can be found by writing a brute-force program to process small cases.
F: easy one.
G: Use S and P to denote the string and the pattern. For each position in S and P, calculate the right-most position with the same character at the left of this position, then calculate the position differences. Now, except at most 26 positions, the problem is translated to a classical pattern matching problem. The matching of that 26 positions can be done by brute force.
H: Sort the cost from the bigger to smaller. Check if you can use points to pay that days account one-by-one. This can be optimized by data structures like DSU.
I: DP-optimization. O(n^3) DP is obvious, which can be optimized to O(n^2logn).
J: The problem is indeed asking for the largest prime not more than the input number.
K: Maxflow.
It seems that there's some issue with the test data of problem I in URI online judge. My program can pass all official test cases.
Same here, I even submited my solution without multiplyting by C (cost per kilometer) and it passed more testcases than with it. I think they are going to update the test data soon.
Portuguese editorial can be found here: https://algorithmmarch.wordpress.com/2016/11/15/final-brasileira-da-maratona-2016/
Based on the portuguese one, a Spanish editorial can be found here: https://caloventorendos.blogspot.com.ar/2016/11/solucionario-regional-latinoamerica-2016_19.html