Hello Codeforces,
I would like to invite you all to participate in the 2018 ACM Amman Collegiate Programming Contest (AmmanCPC 2018). The contest was originally held on the 5th of May, and it will launch in Codeforces Gym on Saturday, 2 June 2018 10:00 UTC.
The problems were prepared by alfadel (Ali Fadel), Vendetta. (Ibraheem Tuffaha) and The-Legend (Abdulmajeed Alzoubi).
Thanks to flerynn (Yosef Darwish), M.Dawwas (Mohammad Abu Dawwas), customer101 (Abdalrhman Ali) and Qumair (Fares Obaid) for sharing the ideas of four problems, to Motarack (Motasem AL-Kayed), customer101 (Abdalrhman Ali) and SAFWAN.K (Safwan Olaimat) for testing some of the problems and to Ownography (Eyad Hajja) for reviewing problem statements.
Also a big thanks to Um_nik (Alex Danilyuk) for sharing the solution idea for a problem and to Hasan0540 (Hasan Alhamsh) and justHusam (Husam Musleh) for the contest wouldn't have been possible without their help. :)
The duration of the contest is 5 hours, and the registration will be open 6 hours before the start of the contest.
Good luck for everyone, and I wish you all Accepted solutions.
UPD: Tutorial
http://codeforces.net/gyms
It was a nice contest, thanks! will there be any tutorial?
Thanks, Glad you liked it. and yes there will be a tutorial which will hopefully be posted in the next 24 hours, sorry for the delay.
Tutorial is up.
How to solve M?
What I actually did is:
1) for each query x and y find the lca of them.
2) ans = cost of going from x upto lca + cost of going from lca down to y + for any node on the path between x and y maximum possible cost of going from this node to any leaf node (which not in the path between x and y) and cost of coming back from that leaf to that node.
I maintained 2^i th max cost along with 2^i th parent and used binary lifting (lca style) to find the maximum double traversal cost.
But I stuck in: how to maintain that maximum double traversal cost which is not in the path between x and y ?
Can anyone help me? Or share your idea how you solved this problem?
Well the solution is pretty simple
Consider sum = sum of ALL costs.
Now since we can go over any edge twice, when we move from X to Y we can traverse ALL the edges twice except the edges on the path from X to Y. Root tree at 1. So just store this data:
Cost of moving from root to node let it be A[i] for ith node
Cost of moving from root to node but considering the reversed cost. let it be B[i] for ith node
Finding LCA is a standard task. let L = LCA(x,y)
answer = sum -(A[x]-A[L])-(B[y]-B[L]) (just remove the costs of edge we cannot traverse).
So you dont have to maintain "maximum double traversal cost" because ALL edges can be traversed except the ones on the path from x to y.
Ohh ! I got it.
I considered to traverse twice only any single path whose sum is maximal. But I can traverse any edge twich other than those are in the path between x and y.
Now found my mistake. Thanks you so much !
How to solve A and J?
A: optimal segment begins where one of the segment begins or ends when one of the segment ends.
J: case bashing basically, depending on most significant bit of A, B and V. Key observation: 2^k OR (2^k — 1) is (2 ^ (K + 1) — 1). If A, B and V have the same most significant bit, we can apply recursion. Be careful on tight TL
Thanks for the reply. Can you elaborate a bit more on A?
lets say the segment we have to form is A to B (B-A+1=k)
now consider if A lies within some given segment.
Where can B be? it can be " not in any segment " in this case we shud just move A to left till B is not in any segment. since doing so will only increase our answer.
now lets say B is at the end of some segment and A is still between some segment.
If value of the segment B is in, is less than the value of segment A is in, then we should continue moving A to the left till A reaches the beginning of that segment(note that our answer will still increase only.) but if the value is larger then we should not move A(because our answer will decrease)
Try to do this analysis.
Now We know that optimal segment will either always start at starting of some given segment or will end at ending of some given segment.
So we only consider such segments using two pointer or line sweep or whatever you call it, and then return the maximum value.
Got it.. Thanks :)
Tutorial is up.
What is the model complexity in G and L? Vendetta.?
Also, time limits in M and J were quite tough imho. I got TLE quite a few times being punished for too slow I/O.
O(K × A3) for G where A = 26, and O(N2 × M × N!) for L.
As for the limits they were at least double the time needed for the judge main solution to run using fast I/O for all problems.
Didn't get the chance to check on I/O efficiency and add notes, sorry for that.
Hmm, I think I know how to solve G in AK log A :D
And it seems my idea for L is far from intended. Thanks :)
For problem G, there are probably ways to improve the solution whether using more greedy approaches than what we did or improving the implementation. As for L there is another solution which probably runs O((N - 1)!3 * log(M)) using Matrix Exponentiation.
Tutorial is up.
Is there some place I can access the data to debug?