Editorial for COCI '12 Contest 6 #3 Dobri


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

A naive solution, trying all possible combinations of three elements for every i, is too slow. Its complexity is O(N4) and is worth 40% points.

Since the values in the array are small, we can have an array P which tells us if there exists a certain value in the array before the current position i. More precisely, P[x]=1 if there is a value x in the array A before the position i, else P[x]=0. Using that, we can improve our starting solution. Instead of trying every possible combination of three elements, we try every possible pair of positions (j,k) less than i and ask if there is a value A[i]A[j]A[k] in the array before i. We have that information in the array P on the position A[i]A[j]A[k]. After processing the position i, we set P[A[i]]=1. We have thus achieved the complexity of O(N3) and 70% points.

For 100% points, we need an algorithm with a time complexity of O(N2). Instead of asking if there is a value A[i]A[j]A[k] for each pair (j,k) in the array before i, we can ask for every position j if there is a pair of values before i such that their sum is equal to A[i]A[j]. We can again use the array P to answer that, because the sum of two small numbers is also a small number. After processing the position i, for every pair (i,j) with ji we set P[A[i]+A[j]]=1. Using this optimization we get a solution that is fast enough and that achieves full points.

Notice that the space complexity of the algorithm is O(maxAi), but if there were larger numbers in the task, we could use a balanced tree instead of the array P. In C++ we can use set and map. We would thus get a solution of a space complexity O(N) and time complexity O(N2logN) which was worth 70% points in this task.


Comments

There are no comments at the moment.