Contest Code: CZIL2021
Question Code: COZPH3
Question link: #include hint_h | CodeChef
The solution involves printing out the final states of the bottles after they have
been subjected to the given force.
The following conditions remain true during the force application process.
● A bottle on which a ‘L’ or ‘R’ force is applied will fall in the direction of force
, irrespective of the states of the adjacent bottles.
● For the bottles on which direct force isn’t applied their states can be
obtained by considering the distance of the respective bottle to its nearest
bottle upon which a direct force is applied. This consideration of forces wrt
distance will give us 3 outcomes :
○ [ 1 ] [ L ] A bottle will fall to the left iff the distance between the
bottle and the nearest bottle on its right which is given a [ L ] force is
less than the distance between it and the nearest bottle on its left
which is pushed to the [ R ] ( if there exists any ).
○ [ 2 ] [ R ] A bottle will fall to the right iff the distance between the
bottle and the nearest bottle on its left which is given a [ R ] force is
less than the distance between it and the nearest bottle on its right
which is pushed to the [ L ] ( if there exists any ).
○ [ 3 ] [ . ] A bottle will remain stationary iff the distance between it and
the nearest bottle on its right given an [ L ] force is equal to the
distance between it and the nearest bottle on its left given an [ R ]. It
can also remain stationary if none of the bottles on its left or right
are given any forces of action.
BRUTE FORCE AND OPTIMAL SOLUTION :
BRUTE FORCE APPROACH : O(N^2)
The solution to the problem can be obtained by picking a particular bottle
and then iterating through its left and right in order to find the distances.
This solution will have a O(N^2) time complexity as each loop for iterating the
bottles will contain nested loops for checking the distances.
OPTIMAL APPROACH : O(N)
The optimal solution will involve pre computing the distances to the left and right
of each bottle and storing them in a vector / array.
Thereby during the iteration for finding states the resulting distances can be
easily obtained by taking the values from the pre computed array thereby
reducing the time complexity to O(N)