Help in Chef Restores an Array

help
array
combinatorics
cookoff
dynamic-programming
wa

#1

Help in COOK-OFF 2018. Question: Chef Restores an Array

link:

https://www.codechef.com/COOK92A/problems/CO92REST


#2

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* and add* we find whether elements have to increase i.e to slope* = 1 or decrease slope* = -1 or no restriction i.e slope* =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* is 0 that is no retriction on element . Here if the a* is -1 then simply multiply ans by k since k variations are possible .

  1. For blocks where slope* 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* . 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

When the editorial will be posted?