Codeforces 466C Help

help
,
1

Can anyone help me with this problem.

My approach till now:

1.Make a prefix sum array from the input

2.In one single loop, find indices where pref[i] = total_sum/3, such indices will be my possible indices for first block

3.For every such index(say idx), iterate over from idx to n-1 (say i) to again check
if a[i]-a[idx] = total_sum/3 , if yes then it is a possible index for the ending of 2nd block and count such possibilities.

But deservedly its showing tle and i’ not sure how to optimise it. code

2

This a very good question in terms of prefix and suffix. Here are some hints for you:

hint1
  • The total sum should be multiple of 3 else answer is zero.
hint2
  • You are using a prefix sum array. Can you think the same as the suffix sum array? It can be used to optimize the part3 of your algorithm.
hint3
  • If we remove some prefix and suffix from the array such that both do not have any overlapping part and have the sum equal to total sum/3, then the middle array also has the same sum. We use this information to solve the question.
hint4
  • So, for 3rd part of your algorithm, for each prefix i that has sum equal to total sum/3, you can try to count the ways to remove a suffix of the original array with same sum and appears the right of the i-th prefix. Make sure that you are not left with the empty array in the middle.
3 Likes
3

if i’ll be doing it for every such prefix won’t it be n^2 in complexity?

4

Finally i got AC, thanks bro for helping. Took some time to understand but it was worth it :slight_smile:

5

Welcome!