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

1

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.
→ Submission #75941303 - Codeforces

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.
→ Submission #75942879 - Codeforces

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.

2

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

3

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:

4

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

5

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 :Submission #75895071 - Codeforces

6

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

Code 
	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){
		s+=a[i];
		dp[i] = dp[i-1];
		if(m.find(s) != m.end())dp[i] = max(dp[i],m[s]);
		m[s] = i+1;
		ans+=(i-dp[i]);
	}
	cout << ans << "\n"
2 Likes
7

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

1 Like