Help in COOK-OFF 2018. Question: Chef Restores an Array
link:
This was really nice a question . I followed lhic’s solution and got understood what he did. He codes are very elegantly written
After the taking the input what we do is . we create 2 arrays adi[n] and add[n] . According to m restrictions, for every I\space L\space R we increment adi[L] and decrement adi[R] . we do this similiarly for add with D\space L\space R restrictions .
Next we create a array slope[N] . for i = 1 to n using adi[i] and add[i] we find whether elements have to increase i.e to slope[i] = 1 or decrease slope[i] = -1 or no restriction i.e slope[i] =0 . If array has colliding condition that is it has increment and decrement at the same time then it is simply not possible and ans is 0
now we will traverse in the array. We have 2 cases.
1)whether slope[i] is 0 that is no retriction on element . Here if the a[i] is -1 then simply multiply ans by k since k variations are possible .
- For blocks where slope[i] is not zero - we check we if there a constant there :-
if yes - then only one configuration is possible since the because of constant and fixed slope other elements will be also restricted and no change in ans . If that configuration is not possible that ans is 0
if no - start from 0 and see what is maximum and minimum possible values in block according to slope[i] . If the range of values for the block , that is is max-min+1 , is > k then also ans is 0 since it does fit in the restriction . Otherwise the range can slide in the window of width k in k-(max-min) variations and hence ans *= (k-(max-min))
In the end we finally print the ans . you can refer to this solution of above implementation
3 Likes
When the editorial will be posted?
1 Like