Welcome to 2013-2014 CT S01E08: 2013 ACM-ICPC Rocky Mountain Regional Contest (RMRC 2013) + GCJ 2009 WF C-D. The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!
It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.
The registration will be available on the Gym page and will be opened until the end of the training. Be careful registering team: please, choose only whose members who will take part in the contest.
Good luck!
What is solution to problem L?
The problem L is a "Closure problem", see wikipedia for more details about.
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.