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?
Auto comment: topic has been updated by Gordinho (previous revision, new revision, compare).
L is fast multiplication (FFT) as I explained here: http://codeforces.me/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.
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?
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?
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.
Also, that Internet Trouble problem (the one that is impossible to get accepted on URI), I was trying to get mine accepted... Without success :(
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.
How do you solve Online Range Mode Query on Problem A?
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 ]
Can someone explain the solution for B, please?
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.