Codezilla Editorial: #include<hint_h>

Contest Code: CZIL2021
Question Code: COZPH3
Question link: #include hint_h | CodeChef

Solution Logic:

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)