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:
did this approach passes all the test cases ? because i too used this approach did'nt got accepted .please help.
Yes this approach passed all test cases . Maybe there was an error in your implementation ?
can you please have a look at my code?
include<bits/stdc++.h>
using namespace std; int main(){ int t; cin>>t; while(t--){ int n,a,b,c,d,min,max,p,q; cin>>n>>a>>b>>c>>d; min=n*(a-b); max=n*(a+b); p=c-d; q=c+d; if((p<=min && min<=q) || (p<=max && max<=q)){ cout<<"Yes"<<"\n"; } else{cout<<"No"<<"\n";} } }
This fails when $$$min < p < q < max$$$.
Also, use code formatting.
this is illegible. you should post the link to your submission instead
There is an easier way:
1.Calculate (a-b)*n, (a+b)*n, c-d, and c+d;
2.If there's a point between (a-b)*n and (a+b)*n and between c-d and c+d, print Yes, otherwise print No.
my solution
In my programme, a=(a+b)*n, b=(a-b)*n, c=c+d, d=c-d.
1 3 0 1 0 if you run this by your logic,then it fails..
a=3, b=3, c=1, d=1,and it will output "NO".
nah bro b=3?? what i have wrote is:- n=1 a=3 b=0 c=1 d=0
written*
You can hack me.
I don't know whether you can.
Suppose that you have all grains initially with weight $$$(a-b)$$$, so the weight is $$$n(a-b)$$$. If you can show that there is a way to increment the weights of the grains one by one until you reach a total weight of $$$n(a+b)$$$, then you show that you can reach every weight in $$$[n(a-b), n(a+b)]$$$.
It's not hard to find a way to do this, one possible way is to increment each grain until it reaches the weight $$$(a+b)$$$. For example, with $$$n=5$$$, $$$a=2$$$, $$$b=1$$$:
Oops, I just realized that I misread your question entirely. $$$n=10$$$, $$$a=2$$$, $$$b=1$$$ disproves your claim that you can make anything from $$$n(a-b)$$$ to $$$n(a+b)$$$ using $$$n-1$$$ equal elements and one other element. For example, try making 15 using your method under these constraints.
What?? Your first comment is absolutely correct.
Hey, thanks for those comments! Helped me to gain the necessary knowledge to attempt to arrive at a proof. When I find such problems, I try to find why they're correct, is that the right way? Also it would be a help if you looked through my attempt and confirm it's correctness and share your insights on approaching problems. (My attempt is in the UPD section of blog)
I don't think I exactly get what you're trying to accomplish in the proof, but if it helps you with your understanding, that's good. It looks correct as far as I can tell.
Not much to say about approaching problems, it's not like there's a checklist that I do a rundown of. Do more problems I guess?