It was the 2nd question in the coding round.
The problem statement goes like:-
There are N ponds in a town and i-th pond has water level A[i]. You have to make town sustainable in M days.
A town is said to be sustainable if it has a sequence of ponds with strictly-increasing water levels. On each day you can perform the following operations:
- Select three conecutive ponds and merge them into i-th pond. Where the water level of the resulting pond is the sum of the water level of the three ponds for some index i where ( 1<= i<= N-2)
- After merging, ponds with index (i+1) and (i+2) disappear.
Determine if you can form a sequence of ponds with the increasing water level in exactly M days Print 1 if possible otherwise print 0.
Note:- 1-based indexing is followed.
Contraints:
1<=T<=10
2<=N<=500
0<=M<=(N-1)/2
1<=A[i]<=10^9
Time Limit: 2 seconds for each of input file
Memory Limit: 256MB
Source Limit: 1024KB
Example:-
1)
N=4
M=1
A=[1,2,1,4]
Approach:
- Select index 2, and do the operation.
- The list becomes [1,7], which is a strictly increasing list.
- Hence, it is possible to make a striclty increasing list.
Therefore the result is 1.
2)
N=5
M=1
A=[6,2,10,8,6]
[18,8,6], [6,20,6], [6,2,24] are the only possible lists after applying 1 operation, none of them are increasing. Hence the answer is 0
