PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Testers: Jatin Garg, Tejas Pandey
Editorialist: Devendra Singh
DIFFICULTY:
1340
PREREQUISITES:
None
PROBLEM:
For an array A of length N, let F(A) denote the sum of the product of all the subarrays of A. Formally,
For example, let A = [1, 0, 1], then there are 6 possible subarrays:
- Subarray [1, 1] has product = 1
- Subarray [1, 2] has product = 0
- Subarray [1, 3] has product = 0
- Subarray [2, 2] has product = 0
- Subarray [2, 3] has product = 0
- Subarray [3, 3] has product = 1
So F(A) = 1+1 = 2.
Given a binary array A, determine the value of F(A).
EXPLANATION:
Since the array consists of zeroes and ones only the product of a subarray can only be 1 or 0. The product of a subarray is 1 if and only if it consists of all ones. Each such subarray consisting of all ones contributes 1 to the final the answer. Therefore the problem is reduced to finding number of subarrays that consists of all ones. The answer for an array of length len consisting of only ones is (len\cdot \frac{(len+1)}{2}). Each array (maybe empty) between every pair of two adjacent array indices which are equal to 0 can be treated as an independent array consisting of only ones and its contribution to the final answer can be calculated as given above by its length. The total of all these individual contributions is the answer to the problem
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Setter's solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sumN=0;
void solve()
{
int n=readInt(1,100000,'\n');
sumN+=n;
assert(sumN<=200000);
int A[n+1]={0};
for(int i=1;i<=n;i++)
{
if(i==n)
A[i]=readInt(0,1,'\n');
else
A[i]=readInt(0,1,' ');
}
ll ans=0;
for(int i=1;i<=n;i++)
{
ll len=0;
int j;
for(j=i;j<=n;j++)
{
if(A[j]==0)
break;
len++;
}
i=j;
ans+=((len*(len+1))/2);
}
cout<<ans<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=readInt(1,1000,'\n');
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
ll n, ans = 0;
cin >> n;
vll v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
for (int i = 0; i < n; i++)
{
if (v[i] == 0)
continue;
int j = i;
while (j < n && v[j])
j++;
ll len = j - i;
ans += (len * (len + 1)) / 2;
i = j - 1;
}
cout << ans << '\n';
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}