PROBLEM LINK:
Division 1
Division 2
Practice
Author: Anton Trygub
Tester: Alexander Morozov
Editorialist: Colin Galen
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
