WATMELON - Editorial

PROBLEM LINK:

Division 1
Division 2
Practice

Author: Anton Trygub
Tester: Alexander Morozov
Editorialist: Colin Galen

(My) video
Official video

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic Math, Observations

PROBLEM:

You’re given a sequence of n integers a_1, a_2, \dots, a_n. You may perform some number (possibly zero) of the following operation: 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.

QUICK EXPLANATION:

Main solution

It’s possible if the initial sum is at least 0, otherwise impossible.

EXPLANATION:

Main solution

Notice that the operations you do can only decrease the overall sum. So if the overall sum is initially less than 0, there’s no way to bring that sum up to 0 using the operations.

Otherwise, say the sum is x, where x \geq 0. You can do the operation on the first element and decrease a_1 by 1, x times. Thus, it’s always possible if x \geq 0.

TIME COMPLEXITY:

Main solution

O(n) for reading in the input and computing the sum.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
 
using namespace std;
 
void solve()
{
    int n;
    cin>>n;
    int sum = 0;
    int tmp;
    for (int i = 0; i<n; i++)
    {
        cin>>tmp; sum+=tmp;
    }
    if (sum>=0) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
 
    int t;
    cin>>t;
    while (t--) solve();
}
Tester's Solution
#include <bits/stdc++.h>
 
using namespace std;
using nagai = long long;
 
int main() {
	 cin.tie(0);
	 ios::sync_with_stdio(false);
	 int t;
	 cin >> t;
	 while(t--){
		 int n;
		 cin >> n;
		 int s =0;
		 for(int i=0;i<n;++i){
			 int x;
			 cin >> x;
			 s += x;
		 }
		 cout << (s < 0 ? "NO" : "YES") << '\n';
	 }
	 return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
typedef long long ll;
 
void solve(int tc = 0) {
	ll n;
	cin >> n;
	
	ll s = 0, x;
	for (ll i = 0; i < n; i++) {
		cin >> x;
		s += x;
	}
	
	cout << (s >= 0 ? "YES\n" : "NO\n");
}
 
int main() {
	send help
	
	int tc = 1;
	cin >> tc;
	for (int t = 0; t < tc; t++) solve(t);
}  

Video Editorial(s)

My video: CodeChef September Lunchtime 2020 - All Solutions (Div. 1 + Div. 2) - YouTube
Official video: - YouTube

9 Likes

If any one need Hindi Editorial Video -LINK

3 Likes

It is giving WA
https://www.codechef.com/viewsolution/38261499

bro value of A[i] can be greater than i so the upper bound of sum that you have fixed to n(n+1)/2 will not work . Read the question carefully it states that you can perform operation as many times you want ,not one operation on each index.

But how will we generate 0 for this array
[-1,-2,10]
Total sum =7
If we start decreasing 10 then it will be 7, again decrease 4.
4-2-1=1, now we can’t decrease. So can anyone please explain me this.

3 Likes

Yeah got it…thanks

bro decrease the first element , in one operation you can decrease by one , so we will decrease first element 7 more times so array becomes -8 ,-2 ,10

2 Likes

@confession123 FOR The Array [-1,-2,10] we will decrease the element 10 by 1 for seven times. Now the array is [-1,-2,3] and sum is 0. Why 7 times or how 7 times? Since the question says decrease the element by i which is the index (here:1) by any number of times(here:7)

Yeah man shit i missed that.

what if all the numbers in the arrays some prime number like [7,7,7,7,7]…how can we make sum as 0?

1 Like

No, you cant decrease 10 by 1, question says, decrease Ai by i. That means arr[3]=arr[3]-3.(if indexing starts from 1).
So, you cant

I knew that because I did same mistake in starting . I loved the questions of this contest.

Oh, oops. Understood.

1 Like

Add all, it will be 35, decrease arr[0] by 1(35 times)
So new array will be [-28,7,7,7,7] hence we get 0

2 Likes

anyone pls help me.

thanks bro.

2 Likes

Go through the question carefully. Its given that choose some i, and reduce the value of ai by i. You can perform this operation any number of time on any element of the array.

i think the question is not totally clear

4 Likes

We can reduce it to [ -1, -1, 1, 1]. We can reduce 17-4-4-4-4= 16, 1-2=-1 and 1-1-1=-1