Привет, Codeforces! Мы рады сообщить, что собираемся провести новый контест на csacademy.com. Round #18 состоится в воскресенье, 12.02.2017 в 21.30 (Мск). Если Вы хотите принять участие в этом раунде, Вам необходимо зарегистрироваться перед началом соревнования. Раунд создан для обеих девизий ( Div1 + Div2), с 8 заданиями различной сложности, которые надо решить за 2 часа и 30 минут.
Мы горды работать с desert97 как с автором задач для этого раунда.
Формат конкурса:
- Вам перелагается решить 8 задач за 2 часа и 30 минут.
- Мы обеспечиваем обратную связь на протяжении всего конкурса.
- Задачи не будут засчитываться частично: то есть либо вы выполнили задание, либо нет (ACM-ICPC-style);
- Оценки будут присваиваться в динамике: в зависимости от количества пользователей, которые справились с проблемой, оценка будет варьироваться от 100 до 1000;
- Помимо баллов, у каждого участника будет "пенальти", который будет учитываться при определении победителя.
О системе пенальти:
- Пенальти вычисляется по следующей формуле: время, потраченное на выполнение последнего выполненного задания + "пенальти" за каждую решённую задачу. "Пенальти" для каждой решенной задачи равен log2 (no_of_submissions) * 5.
- Решения, которые не компилируются или не подходят для примеров тестовых случаев игнорируются.
- После того, как вы решили задачу и отослали результат, вы можете поэкспериментировать с решением, все последующие ответы уже не будут учитываться.
Традиционно, мы рекомендуем использовать обновленную версию Google Chrome. Если вы обнаружите какие-либо ошибки, пожалуйста напишите нам по адресу [email protected] или в комментариях ниже.
My solutions.
F: sparse table to precompute the min. position j such that gcd([i..j)) = 1 in a linear array, then DP counting the number P(i, g) of A[i..N) such that the last partition has gcd equal to g; there are just
possible values of g, so it's 
G: when solving the subtree of R, we keep a structure S that contains some previous ancestors and is able to answer queries "pick the best of them for any vertex v"; pick the son s with the largest subtree, solve all other sons' subtrees by bruteforcing over them and picking from S, then solving them recursively without S (starting with empty structures), then add R to S and solve the subtree of s recursively with S (HLD trick,
time if one query on S takes 
time)
How do you answer this query "pick the best of them for any vertex v"? And what is the time complexity for this?
Let fv(x) = Cv + xdepv. You're looking for the smallest x such that there's some fu(x) = fv(x), but it's enough to consider the smallest fu for each x; for a set of lines, taking only the smallest fu gives a convex (or concave?) polyline, to which you can add lines like in the convex hull algorithm. When all u can only be ancestors of v, fv will only intersect such a polyline once and you can find the segment of the polyline containing that intersection by binsearch. Note that lines are added in a very specific order in this algorithm, which simplifies things.
It's nice to see that editorial mentioned the fact that naive implementation of G works in O(N2). However, such implementation works in 0.121 on provided test data.
I really liked last problem! Too sad I made a stupid bug when fixing loops issue :(. Btw I guess that such picture can be a little misleading :P :
Take it positively, at least you could submit.
I don't get it. TL was changed during contest to 5s, but in archive it is set to 1,5s <- this is bad, but I get it. First thing I don't get is why I am getting "Accepted" even though I get TLE? Is that because it was killed after archiveTL=1.5s and execution time (shortly killed after 1.5s, to it is <1.6s) was compared with contestTL=5s? Second thing I don't get is why I started getting WA on 4th and 5th test in archive even though I am pretty sure I got them correctly earlier.
In TC, when you batch test on samples, it used to tell you "success" on top... when your code compiled.
In some other sites, in problems with partial scoring, getting a non-zero number of points gives you AC verdict.
And in CSAcademy, it tells you your solution is accepted when it passed some tests, even if it failed other tests. I've had it happen to me, luckily only when practicing. Once when the judging froze, I was getting AC in the "Submissions" tab, but it only meant AC on samples.
The time limit was always 1.5seconds, it was changed before anyone submitted any code to it. It was a typo on our part to make it 5 seconds in the first place, that's why it was changed during the contest (when we realised). On your first point, I don't know what to say, it seems like a bug if it gets you AC, we will check it out. Second part seems really hard to believe though. We will check that out as well, thank you :)