k790alex's blog

Latin America Regional Contest 2016
By k790alex, history, 7 years ago, In English

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]
  • Vote: I like it
  • +42
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems can be found here: https://www.urionlinejudge.com.br/judge/en/challenges/contest/211

How to solve C?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      A further simplification is that squares can be considered as two diagonals, so you only need to consider .

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So this 5 teams will go to WF?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As far as I know, it depends on the spots given to each region.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how can we solve problem B ?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    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".

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

PDF version of the problems can be found at http://maratona.ime.usp.br/resultados16/contest.pdf

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Problems were opened for submission: https://www.urionlinejudge.com.br/judge/pt/problems/origin/136

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +26 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply