I'm posting this blog so we can discuss the solutions to the problems of 2018-2019 ACM-ICPC Latin America Regional Contest.
Links to problems:
G — Gathering Red-Black Fruits
K — KryptoLocker Ate my Homework
L — Looking for the Risk Factor
Happy discussion.
This is the final scoreboard of the contest
Well, the problem D and M were pretty easy, it was just implementation. A symetrical Pizza was just to solve the equation aXmod 360 = 0, however X was a float integer with two decimals. In the regional contest this was a problem beacause it got you WA even if you multiply X and 360 by 100. So We had to parse the number and remove the zero.
I would like to know how to Solve B,C and L. Thanks in advance
For problem B, you should notice that a rectangle must have two diagonals, and as the rectangle is inscribed in the circle, those diagonals must be diameters of the circle. Therefore you just have to check if there are a least two pairs of opposite points on the circle.
Problem C can be solved with a DP. DP[i][l][t] is the optimal cost for taking all trips from i, given that we have l minutes left of the discount and there have been taken t trips with the current discount. So the answer is DP[0][0][0].
For problem C you only need i and t for the matrix. there is only one valid l value for every i and t values
Nice observation! I coded the other one and it fit in time so I didn't think more carefully about that, maybe a little modification over limits could have done the problem more interesting :P
In fact, you only need to know the cost for a trip ending at point I, that was my AC in-contest
If you store optimal cost for trip I, then you can check 3 transitions:
1-Buy trip I and nothing after
2-Buy trip I and get next trip with a 50% discount
3-Previous transition + get any number of trips between i + 2 and i + 6 with a 75% discount
You also need to check if it's possible to buy by having sum_of_distances(i, i+k) < 120
EDIT: added solution
Problem C is possible with dijkstra too
Thanks to the peruvian team [UPC] La Señora K-ruskal for the main idea for problem B:
Two points in the circle are called opposite if are exactly separated by 180° (are at the same distance both clockwise and anti-clockwise). Having said that, if you can find at least two pairs of opposite points, you can asseverate that you can form a rectangle. See the image:
So, in order to find the pairs of opposite points you can use a set of prefix sums and find the opposite of a point doing: (x + s/2) % s, being x the current distance of the point and s the total distance sum of the circle. The s/2 means "add 180° from this position".
Code: https://ideone.com/jsIpPM
What happens when s is not even ?
If s is odd, you can simply answer 'N'
I've solved the problem L. Has been basically solved with an offline algorithm for manage the queries by your favorite update/query data structure (BIT, Segment Tree). Code: https://ideone.com/irbeZ3
Does anyone know what is the general idea to solve problem E? Thanks
Fix a base. Take the edges that project on the left/right of this base. Create a tournament graph where the direction of the edges is (u, v) is directed from u to v if and only if v projects to the left of u. The task is now counting the number of 3-cycles in this graph and that's way easier. Count everything — 3-cycles that don't exist. A 3-cycle that doesn't exists will have exactly 1 vertex that has 2 out edges and exactly 1 vertex that has 2 in edges. This doesn't treat the parallel edges case (the graph isn't exactly a tournament graph) but that's easily counted apart.
Here's another idea, though it may be equivalent. Iterate through the sides of the polygon counter-clockwise. Suppose that we are processing some side (the green side in the picture). Consider the consecutive edges after that one, and continue until the angle with respect to the horizontal has increased by , the relevant portion of the polygon is cut off by the grey line in the picture. Now it's easy to see that any two edges in this section, along with the green edge, form a triple that doesn't work (the red edges in the picture for example).
With some care you can see that this process actually counts every bad triple exactly once, so just iterate over all n sides, find the number of edges in the relevant section of the polygon and find the number of pairs of these edges. Finally just subtract this from the total number of triples. We didn't solve E during the contest but this did give AC on the online judge.
That's equivalent, the rest of the explanation is for understanding why that counts all the bad triples once.
Alright, makes sense
Let a[i] = Slope of ith segment, now we have to find triples of segments i < j <k such that one of the following conditions holds: a[i] > a[j] > a[k] or a[j] > a[k] > a[i] or a[k] > a[i] > a[j]. To count them easy, one can shift the array such that it only decreases once.
We actually managed to solve problem L online during the contest. The idea is that we can precoumpute the answer for every value of K that is either a prime smaller than 1000 or a multiple of 1000. Then for queries with small values of K we just output the answer we calculated for the largest prime that is less than or equal to K, and for large values of K we take an m such that 1000m ≤ K < 1000m + 1000, take the answer for K = 1000m and then iterate through the primes in the interval (1000m, K]. We can see that for each one of these primes p we only need to add to the answer, because p2 > 105.There are not very many primes in these intervals so each query is fast enough.
Did anyone solve problem F? Think im missing something in my implementation.
The max answer could be greater than 10^18, that could be your problem.
Didn't solve during the contest, but I got accepted on the online judge.
The idea is fairly simple, the i-th line describes a function fi from S = [1, 2, ..., Z] to itself. It is not difficult to verify that fiZ(S) = fiZ - 1(S), so fi restricted to Si = fiZ - 1(S) is a permutation. So we can simulate the first Z steps and check whether those work manually. After that, every fi will only move us on some cycle Ci, and we want to check whether they coincide. To do this, we try every element of C1 as a possible common value. If this element is not in Ci for some i, then this is impossible. Otherwise the cycles give us a linear system of congruences such that each solution of it is a valid number of steps, and we can solve this using general CRT.
The implementation, at least in C++, is not easy, because even though the moduli that we build during CRT do barely fit inside a 64-bit integer, it is possible that even the sum of two numbers of that size won't fit, so you have to be extremely careful with how you do each operation in order to avoid an overflow.
How did you manage the fact that module in CRT could be 100*99*98*97*96*95*94*93*92*91 ~ 6e19, and it doesn't fit even in unsigned long long?. I solved it in Java (post-contest) but it was a pain in my neck.
Well, the modulo in that case is actually lcm[100, 99, ... , 91], which does fit. To be honest I don't know whether there is a case that does not fit in an unsigned long long, if there is then it wasn't included in the official test cases.
Even if it does work, I would definitely advocate for using big integers rather than trying to make it work with C++ long longs, it was extremely annoying.
The largest modulo I could come up with is with [99, 97, 95, 94, 91, 89, 83, 79, 73, 71] which exceeds 264.
I don't get the decision of the problem-setter regarding the constraints. Having for example B ≤ 5 would be exactly the same problem, but without that unnecessary annoyance with the overflows...
During the contest, you could use 128 bit integers.
What is the expected solution for problem C? using C++ and a DP[time][pos] gives me a 0.850 AC with a 1 second time limit I believe it should be optimized further?
please read my previous comment
How to solve K?
The greatest positive sum is the sum of all positive numbers. The second greatest positive sum must be the greatest positive sum removing the smallest positive number or adding the smallest (in absolute value) negative number. This can be proven mathematically, but I won't do this right now.
So, the basic idea is to test both alternatives: removing the smallest positive number or adding the smallest negative number. To test if this candidate number is an option, half the sums must contain this number while the other half must not contain it, so you just need to check if this holds. The easiest way is taking the greatest remaining sum and checking if exists the this sum minus your candidate (if the candidate is positive. If it's negative you must check if exists this sum plus your candidate).
The sums must reduce by half every step, so you have a binary tree with height N. The complexity to do this is 2^N on every level of the tree, so N*2^N in total.
I don't think there are multiple solutions to this problem, but if there are you must be able to just store the answers on a set of sets and print them in order, but talking to contestants after the contest they didn't do this and got accepted (I just assumed the answer was unique)
The answer is not unique. See this case for example: -3 -2 -1 0 0 1 2 3
Here are two possible answers: -3 1 2 and -2 -1 3
Okay, so you must calculate every one of them and print in lexicografical order. I don't think there's a smart way to do this. Using set of sets you end up with O(N^2*2^N) or O(N^3*2^N). Is there any better way?
That's enough. Not every mask will be an answer too so it has good constant. There are at most 2^N answers and inserting one has cost N^2 at most. To make it even faster, you could push them into a vector and sort later, that has way better constant than using a set.
Coming back after some years (someone just asked me about this problem and I decided to implement the solution, so seems okay to add more information here):
The solution is exactly what was described above. Checking for both minimum positive and maximum negative is required. You can do a divide and conquer to find the solutions.
The tricky part is avoiding O(N^2) complexity on the divide part of the D&C, that brings the complexity to O(N^3*2^N) (at least on URI OJ I got TLE with multiset or vector+binary search. Maybe in the actual contest the machines were better and the time limit was more forgiving).
The good part is that it's not hard to bring this down to O(N). You want to find a matching pair of values: x and y, so that abs(x — y) = abs(element being removed), and since this difference is constant using two pointers (or storing the elements that you want to ignore and checking when against them while advancing) allows this part to become linear.
How to solve problems G, I and J?
For problem I, first we divide a stick man by levels as follows:
Now, we can use dynamic programming to solve the problem,
f(node, level)
= maximum number of stick men that we can make if we are in nodenode
and our current stick man is at levellevel
.Can you share the code for this problem?
Of course! solution I hope the code will be clear! If not just tell me
Yes, for problem I, dp is good. But, my coach has a pretty greedy solution problem I
This is the original solution of problem G. Ask any questions that you may have. https://1drv.ms/b/s!AqdRUIdEpNOHhnHQazJ_8jU2M-iU
The pdf looks great. Thank you very much. You said it is the original solution. Does that mean there are other original solutions? Do you have explanation pdfs for the other problems as well, by any chance?
How to solve problem J?
I problem A, using C++, I tried the approach of multiplying the angle times 100 and applying floor, but the way to do it wasn't floor(100*angle) but floor(100*angle +0.5).
If you read a = 144.01, and then do floor(100*a), it returns 14400, and floor(100*a + 0.5) returns 14401.