Добро пожаловать на 2013-2014 CT S01E08: 2013 ACM-ICPC Rocky Mountain Regional Contest (RMRC 2013) + GCJ 2009 WF C-D. Продолжительность тренировки — 5 часов. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.
Так как это тренировка, то возможно набор задач будет расширен, если для значительного количества участников он окажется простым.
Регистрация на тренировку будет доступна со страницы Тренировки и будет открыта до окончания тренировки. Регистрируя команду, выберите именно тех её членов, кто будет писать тренировку.
Удачи!
.
Еженедельные, сколько их всего будет вроде не сказано.
What is solution to problem L?
The problem L is a "Closure problem", see wikipedia for more details about.
Капитан так и не пришел.Как L решать? Там же после конденсации достаточно произвольный DAG получается?Задача сводится к "есть ориентированный граф, у каждой вершины есть цена. Необходимо выбрать набор вершин максимальной стоимости такой, что если в наборе есть вершина А, и есть ребро AB, то вершина B тоже должна быть в наборе."
Ее можно решать так. Добавим две вершины S, T. Рассмотрим вершину i. Если cost_i > 0 добавим ребро (S->i) пропускной способности cost_i. Если cost_i < 0, добавим ребро (i->T) пропускной способности -cost_i. Еще, если есть ребро (i->j) в исходном графе, то добавим ребро (i->j) стоимости inf в новый граф. Утверждается, что ответ это сумма всех положительных cost_i минус минимальный разрез между S и T в этом графе.
It was a great contest (although I solved only 2 problems), I know that gym haven't editorial but someone could explain me what is wrong in my solution for problem E (4937051) and problem G (4937051), I couldn't get it, thanks.
As far as I understand Java: E looks fine to me (algorithm-wise), maybe you just don't take enough care of all the tricks with float; in G, you're linking the same submission as for E.
There might be an editorial, btw.
ups, this is for G 4937380, and for E I was wondering about problems with floating point, could you explain me some precautions with it? thanks.
Basically, the value can be off by a little. You can get 10 - 15 instead of exactly zero, or something like that. (It also means there's no guaranteed equality.) You should test all conditions within this small margin of error, then — for example instead of ≤ 0, I use ≤ 10 - 7.
I don't see what you're doing in G, maybe it's not even a correct algorithm. I just did an O(N2N) bruteforce.
Basically what I did is:
Use a counter where it have how many people are seing the ads and while its less than all N (all the people) take this action: 1.- Find the best candidate, the best candidate is who have more freinds not seeing ads (including itself). 2.- mark the best candidate and his friends as visited (seeing adds).
Greedy, then. I don't think that would work. Try bruteforcing instead.
I tryed greedy because it could have N = 20, for brute force I could think only in try all possible permutations and that'll be too slow, you mean did it in O(N2^N) but I dont understand how you did it, could tell me a little?
greedy maybe wrong !!! brute force isn't to slow because if you want check all possible permutations you need O((2^N)*N) but if you want check all possible permutations you should use bitmask technic also yo can use DP (here is a sample code) sorry for poor endlish :))
Could anyone give some ideas on Problem C? Thanks!
Consider that, We are finding answer for university i.
It must hold that:
for all j != i R[i] * a + T[i] * b + S[i] * c >= R[j] * a + T[j] * b + S[j] * c
(R[i] — R[j]) * a + (T[i] — T[j]) * b + (S[i] — S[j]) * c >= 0
So, we have n — 1 inequality, and we must find plane(a, b, c, 0), such that Points = {( R[i] — R[j], T[i] — T[j], S[i] — S[j]) } are all above the plane.
If we have found such plane, we can shift/rotate this plane, such that it touches at least 2 points from Points.
Plane also must touch point (0, 0, 0) .
So try build Plane from point (0, 0, 0) and 2 combinations from Points and check.
delete не туда написал