×

# Help in Chef Restores an Array

 0 Help in COOK-OFF 2018. Question: Chef Restores an Array link: https://www.codechef.com/COOK92A/problems/CO92REST asked 19 Mar '18, 22:25 30●2 accept rate: 0% 15.4k●1●20●66

 3 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 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 answered 20 Mar '18, 16:43 4★sonu_628 345●8 accept rate: 8%
 1 When the editorial will be posted? answered 21 Mar '18, 17:27 76●5 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,718
×2,172
×1,070
×892
×847
×178

question asked: 19 Mar '18, 22:25

question was seen: 707 times

last updated: 21 Mar '18, 17:27