Editorial for COCI '12 Contest 6 #3 Dobri
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 , is too slow. Its complexity is
and is worth
points.
Since the values in the array are small, we can have an array which tells us if there exists a certain value in the array before the current position
. More precisely,
if there is a value
in the array
before the position
, else
. Using that, we can improve our starting solution. Instead of trying every possible combination of three elements, we try every possible pair of positions
less than
and ask if there is a value
in the array before
. We have that information in the array
on the position
. After processing the position
, we set
. We have thus achieved the complexity of
and
points.
For points, we need an algorithm with a time complexity of
. Instead of asking if there is a value
for each pair
in the array before
, we can ask for every position
if there is a pair of values before
such that their sum is equal to
. We can again use the array
to answer that, because the sum of two small numbers is also a small number. After processing the position
, for every pair
with
we set
. 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 , but if there were larger numbers in the task, we could use a balanced tree instead of the array
. In C++ we can use set and map. We would thus get a solution of a space complexity
and time complexity
which was worth
points in this task.
Comments