Natsya and Rice

Revision en3, by Athreya1900, 2020-04-25 18:24:45

Problem Statement

In short

You are given five integers $$$ n , a , b , c , d $$$ . You need to check if it is possible to form an array of $$$n$$$ elements such that each element's value is between $$$ a-b $$$ and $$$ a+b $$$ and the sum of the array is between $$$ c-d $$$ and $$$ c+d $$$

Initial Thoughts

My initial idea was to loop $$$ i $$$ from $$$ a-b $$$ to $$$ a+b $$$ and check if $$$ n * i $$$ lies in the range $$$ [ c-d , c+d ] $$$

But the problem with that is this assumes that all the array elements are same.

Counter Test

Let's have $$$ n = 4 , a = 2 , b = 1 , c = 7 , d = 1 $$$

This means that all the elements of the array we're trying to form is $$$ [ 1, 3 ] $$$ .

The sum we're trying to make is between $$$ [ 6 , 8 ] $$$

If we assume only same elements , the sum we can form are $$$ 3 , 6 , 9 $$$ ( All 3 elements are 1 or 2 or 3)

Intuition

Now in the previous case , this array is possible $$$ { 2 , 2 , 3 } $$$

How to generalize what sums are possible?

We know that the minimum sum possible is $$$ (a-b) * n $$$ (All elements are equal and are the smallest element)

The maximum sum possible is $$$ (a+b) * n $$$

Now are all the sums between $$$n * (a-b)$$$ and $$$n * (a+b)$$$ posssible ?

I took this example : $$$ n = 4 , a = 12 , b = 2 $$$

The goal is to prove that all sums from $$$ (a-b) * n $$$ to $$$ (a+b) *n $$$ are possible ie. between $$$ 40 $$$ and $$$ 56 $$$

Sum = $$$ 40 $$$ , Array = $$${ 10 , 10 , 10 , 10 } $$$

Sum = $$$ 41 $$$ , Array = $$${ 10 , 10 , 10 , 11} $$$ ...

Sum = $$$44 $$$ , Array = $$${ 10 , 10 , 10 , 14} $$$ or $$${11 , 11 , 11 , 11}$$$

Sum = $$$45$$$ , Array = $$${11 , 11 , 11 , 12} $$$

Sum = $$$46$$$ , Array = $$${11 , 11 , 11 , 13} $$$

Sum = $$$47$$$ , Array = $$${11 , 11 , 11, 14}$$$

Sum = $$$48$$$ , Array = $$${12 , 12 , 12 , 12}$$$

.....

Sum = $$$56$$$ , Array = $$${14 , 14 , 14 , 14}$$$

Doubts

My approach involved forming an array with $$$n-1$$$ equal elements and one same or different element , we can always from the sum $$$ n * (a-b) $$$ and $$$ n * (a+b) $$$

Do you try to prove such solutions especially if they're Div 2 , A

Is there an easy way to prove solutions

How to develop intuition ?

UPD Here is my attempt after reading Tzak's comment:

Proof

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Athreya1900 2020-04-25 18:24:45 116 Tiny change: 'comment:\n![ ](https://' -> 'comment:\n\n[Proof](https://'
en2 English Athreya1900 2020-04-24 07:56:55 4
en1 English Athreya1900 2020-04-24 07:56:20 2175 Initial revision (published)