Help in COOKOFF 2018. Question: Chef Restores an Array link: asked 19 Mar '18, 22:25
converted to question 19 Mar '18, 22:30

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 . 2) 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 maxmin+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(maxmin) variations and hence ans *= (k(maxmin)) In the end we finally print the ans . you can refer to this solution of above implementation answered 20 Mar '18, 16:43
