Problem C- Eugene and an array | Codeforces Round 632 (Div 2)

Hello. I was trying to solve Problem C, and used the following approach.
Using dynamic programming,
for all dp(i, j) such that i, j >= 1
if dp(i, j-1) = 0 || dp(i+1, j) = 0 || sum from index i to j = 0, then dp(i, j) = 0
else dp(i, j) = 1

This is my solution, but it is giving me MLE for pretest 3.

I then changed the 2-dim array dp[][] to 1-dim and used this approach.
dp[i] = 0, if dp[i-1] = 0 or d[i] = 0, or sum from i to j = 0

Again I was getting correct output for all my testcases, but pretest 3 is giving me TLE
This is my solution using this approach.

Can someone please help me with this problem? Is the dp approach that I’m using correct?
The problem is that in pretest 3, the value of N = 2 x 10^5. Please help.

my approach was also same, please help with this problem.

Number of subarrays with 0 sum is a common problem, and has a simple O(N) (O(NlogN) worst case) solution. Here’s the basic idea:

This question is a lot different then total subarrays with 0 sum.

What i did was i calculated ans like how many subarrays ending at ith index have a subsegment with sum=0,so all those for each index i-I calculated the largest index j(j<=i) such that sum(j,i)=0,so we cant include the subarrays with starting point <=j ,if there is no subarrys ending at ith position having sum=0,then we just add the maximum value of starting index occured previously because
since we have calculated ans for subarrays ending at [1,i-1] if for current index i we cant include those with starting index<=max starting index uptil now so just add ans+=(max starting index uptil now),if(there is a subarray ending at ith position having sum 0 and starting at pos=j){
if(max starting index<j)ans+=j,max starting index=j;
else ans+=max starting index
and finally ans=n*(n+1)/2 - ans
my solution :

I used sub array approach only using maps. This is my code, see if you can find where you went wrong.

	map<ll,ll> m;
	ll s = 0,ans=0,n;
	cin >> n;
	V<ll> a(n+1,0),dp(n+1,0);
	loop(i,1,n+1)cin >> a[i];
	m[0] = 1;
	for(int i = 1 ; i <= n; ++i){
		dp[i] = dp[i-1];
		if(m.find(s) != m.end())dp[i] = max(dp[i],m[s]);
		m[s] = i+1;
	cout << ans << "\n"


Hey can you comment the purpose of variables used in your code so that it becomes more clearer to understand. Thanks

1 Like