Gordinho's blog

ACM ICPC 2017 Brazil Sub-Regionals
By Gordinho, history, 7 years ago, In English

On last saturday, ACM ICPC 2017 Brazil Sub-Regionals contest was held, featuring 13 problems and having more than 800 teams trying to advance to the Latin America Regional Finals that will happen in November. I created this thread so we can talk about the problems in the contest.

The problems can be viewed in this link (Portuguese): http://maratona.ime.usp.br/prim-fase17/maratona.pdf

This problems are in URI too: https://www.urionlinejudge.com.br/judge/pt/problems/origin/148

A — SegTree

B — Simulation with dp

C — LCM

D — Prime divisors

E — Simulation

F — Simple sort

G — Dp

H — Max path on dag

I — DFS/BFS

J — %3

K — I dont know

L — I dont know

M — monkey problem

Anyone know how to solve problems L and K?

  • Vote: I like it
  • +10
  • Vote: I do not like it

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

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

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

L is fast multiplication (FFT) as I explained here: http://codeforces.com/blog/entry/54459#comment-385072

K is a pure math problem. This is how I solved it:

We want (A + sqrt(B))^n and -1 < (A — sqrt(B)) < 1. Write the expansion of (A + sqrt(B))^n, it is the sum of sqrt(B)^i * A^(n — i) * (from n choose i) for each 0 <= i <= n. Note that there are 2 different parts of this number: the part that's completely an integer (when i is even) and the other that is multiplied by sqrt(B) (when i is odd). Let's write (A + sqrt(B))^n == x + y * sqrt(B).

Now, let's take a look at (A — sqrt(B))^n. We know that -1 < (A — sqrt(B)) < 1 so we also know that -1 < (A — sqrt(B))^n < 1. Now take a look at the expansion, it is the sum of (-1)^i * sqrt(B)^i * A^(n — i) * (from n choose i) for 0 <= i <= n. Note that the two parts are still on this number, but the part that's multiplied by sqrt(B) is negative. So (A — sqrt(B))^n == x — y * sqrt(B). It also means that -1 < x — y * sqrt(B) < 1, so the absolute difference between the integer part and the irrational part is less than 1. This means that:

x — 1 < y * sqrt(B) < x + 1

If x <= y * sqrt(B) < x + 1, x + y * sqrt(n) will be 2 * x. Else, it will be rounded down and the answer will be 2 * x — 1. So the whole problem is just finding x. Write a number as a pair of integers (x, y) which means x + y * sqrt(B) and define (x1, y1) * (x2, y2) = (x1 * x2 + B * y1 * y2, x1 * y2 + y2 * x1). Now you can use fast exponentiation to find (A, 1)^n = (x, y) while keeping the answer modulo 10^something.

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

    In the online judge I've only managed to pass L with suffix-array. It appears that the FFT uses way too much memory.

    Was FFT accepted in the actual contest?

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

      Yes it was. URI online judge is way worse than anything else. For example: problem I from last regionals is unsolvable in URI even using an O(N^2) solution because of time while I've heard that an O(N^2*logn) solution was accepted during the actual contest.

      Edit: How can you apply suffix-array on this problem?

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

        It's the brute-force approach with the help of LCP to avoid some recalculations.

        Let P be the input string, SA it's suffix-array and LCP it's lcp, S an array that store's partial sums, V an bitset of size 26 * N and count an integer.

        S[0] = 0

for i from 0 to N:
  if i != 0:
    count = LCP[i] + 1
  else:
    count = 1

  for j from SA[i] + LCP[i] to N:
    S[count] = S[count - 1] + P[j] - 'a'
    V[S[count]] = 1
    count += 1

print V.count()

        Also, that Internet Trouble problem (the one that is impossible to get accepted on URI), I was trying to get mine accepted... Without success :(

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

          As long as I can tell the worst case behavior of this solution can be easily forced by De Bruijn sequences for example, so I may even assume that the tests are weak.

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

How do you solve Online Range Mode Query on Problem A?

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

    sw1ft

    The values are between 0 and 8, in this way you can build 9 segment tree with lazy propagation (one for each number (0, 1, ..., 8)).

    To Find the most frequent value in a range [i, j] you just need to check in all segment tree and take the the number witch the amount of occurrences is maximum

    For update of a value x you just need do it

    Seg_Tree[ node ] [ (numb + x)%9 ] = Seg_Tree[ node ][ numb ]

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

Can someone explain the solution for B, please?

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

    I started writing some hints for the problems (in portuguese) at https://paulocezar.net/2017/09/12/regional-maratona-2017.html

    For problem B you can use pigeonhole principle to prove that a solution always exists. Based on that you just simulate the LFSR keeping track of the sum of the elements seen so far modulo X. When a repeated value is found that means you found a subsequence divisible by X, now you just have to check if the number of elements is greater than or equal to Y. It's easy to see that by keeping track of the first occurrence of each sum (modulo X) and stopping at the first time you find an answer you minimize the values of I and F as requested.

    → Reply