WATMELON - Editorial

[-1,-2,10] sum=7
we can also do like that
[-1, -2, 7 ]–> [-1,-4,7]–> [-1,-6,7] sum=0

no operation =3 (if we have find to min operation)

i already got that bro

can anyone tell. if we can subtract one element only once. then how this problem will be solved ??

@sourav_singh29 Well in that case you can subtract atmost : n * ( n + 1 ) / 2 from your sum so we will simply check

if( sum >= 0 && sum <= n*(n+1)/2 )
       cout << "YES\n" ;
else
      cout << "NO\n" ;
1 Like

logic ???

@akshy_8 With numbers 1 , 2 , 3 , 4 , 5 , . . . . . , n , we can make every possible sum between [ 1 , n*(n+1)/2 ] , Here n*(n+1)/2 is sum of first n natural numbers.

You can prove it this way using induction

Thankyou

1 Like

why the problem name was watermelon?? :thinking: :thinking: :thinking:

its super easy index sum the element @2,3,4,5 their total be 28. take 1st index to -28 ,by decreasing it by 1 each time you get 0 as totalsum now

I was thinking the question in this way…so I got wa

Thanks for the effort man

1 Like

@akshy_8 That also helped me in getting good idea of induction .

Thankyou

Yes!! I’m totally agree with you.

I think question is not clearly mention what’s it saying,
According to Question:-
choose some i, and reduce the value of a[i] by i. Find out if it’s possible to make the sum of all the integers equal to 0.
A/c to me solution is like this

int t;
cin>>t;

while(t--)

{

    int n;

    cin>>n;

    int a[n];

    for(int i=1;i<=n;i++)

    {

        cin>>a[i];

    }

   int sum=0;

    for(int i=1;i<=n;i++)

    {

        sum += a[i];

        sum -= i;

    }

    if(sum)  cout<<"NO\n";

    else    cout<<"YES\n";

}

So please can anyone help me out of it.

My solution got accepted
What I found is that if the summation of all the elements is positive then there might be or I think must be a way to make the sum zero but if the sum is negative then there’s absolutely no way.

Every position has a weight of its own like in
[2,3,5] element 2 has weight 1 ie. we can only subtract 1 from the first element, element 3 has weight 2 and 5 has weight 3
That means every element has a predefined weight which is its position.

Here is what I did. I didnt use an array I simply summed up the elements and passed the total sum to function “check”
Check function tries to make a newsum using the weights equal to the sum passed to it.

#include <bits/stdc++.h>
#include <math.h>
using namespace std;

bool check(int num, int size)
{
int Sum = 0, temp = num;
num = abs(num);
for (int i = size; i >= 1; i–)
{
Sum += i * (num / i);
num %= i;
}
return (Sum == temp);
}

int main()
{
int T; cin>>T;
while(T–)
{
int N; cin >> N;
int sum = 0;
int size = N;
while (N–)
{
int a; cin >> a;
sum += a;
}
if (check(sum, size))
cout << “YES” << endl;
else
cout << “NO”<<endl;
}

return 0;

}

Lets take the input [2,3,5]
Sum is 10
I call check(num, size) // size is 3 and num is 10
check function will try to make a newsum equal to 10 by using the weights of the elements

First iteration:
Newsum += 3*(10/3) = 9 # just remember 10/3 = 3
new num = 10%3 = 1
Newsum += 2*(1/2) #j ust remember 1/2 =0
new num = 1%2 = 1
Newsum += 1*(1/1) # just remember 1/1 = 1
new num += 1%1 = 0

So now what does that 3 0 1 mean
[2,3,5]
From 5 subtract its weight (3) 3 times ie 5 becomes 5-9 = -4
From 3 subtract its weight (2) 0 times ie 3 becomes 3-0 = 3
From 2 subtract its weight (1) 1 time ie 2 becomes
2-1 = 1

Sum the numbers = -4 + 3 + 1 =0
Therefore ans is “YES”
.
.I hope this helps out
If somethings wrong with my idea or code please do tell me.