You are not logged in. Please login at www.codechef.com to post your questions!

×

Help in Chef Restores an Array

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

link:

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

asked 19 Mar '18, 22:25

ashudeshwal's gravatar image

3★ashudeshwal
302
accept rate: 0%

converted to question 19 Mar '18, 22:30

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066


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

link

answered 20 Mar '18, 16:43

sonu_628's gravatar image

4★sonu_628
3458
accept rate: 8%

edited 20 Mar '18, 18:59

When the editorial will be posted?

link

answered 21 Mar '18, 17:27

akash_321's gravatar image

4★akash_321
765
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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