Athreya1900's blog

Natsya and Rice
By Athreya1900, history, 5 years ago, In English

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

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

did this approach passes all the test cases ? because i too used this approach did'nt got accepted .please help.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes this approach passed all test cases . Maybe there was an error in your implementation ?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      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";} } }

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        This fails when $$$min < p < q < max$$$.

        Also, use code formatting.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        this is illegible. you should post the link to your submission instead

        → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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$$$:

1 1 1 1 1 <--- weight is n(a-b)
2 1 1 1 1
3 1 1 1 1
3 2 1 1 1
...
3 3 3 3 3 <--- weight is n(a+b)
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What?? Your first comment is absolutely correct.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply