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)