SUMPOWER - Editorial

Input Test Case for overflow:
1
100000 50000
abcdefghijklmnopqrstuvwxyzabcde…(till 100000 characters)

Output
2500000000

Which will overflow and not fit in integer datatype

2 Likes

How do we check the answer will overflow? I really don’t know why the answer exceed int. Thank you

Can anybody help me with this approach?


[1]


  [1]: https://www.codechef.com/viewsolution/19030972

Can somebody point out why I’m Getting Wrong Answer


(https://www.codechef.com/viewsolution/19025299).

I cannot understand the solution, how prefix sum is used to get the answer, can someone please elaborate the intuition behind the author’s solution?

1 Like

Thanks for telling about the O(1) space complexity approach :slight_smile: It had never occurred to me.

Thanks for this, never heard about prefix-sum before :stuck_out_tongue:, however, I tried solving this question using segment tree, although it ended up giving TLE error on subcase #2,
my approach was to build an array ‘ARR’ of size N-1, and each index i of this array is either 1 or 0

ARR[i] = 1 denotes that string’s i-th and i+1 th character are different
and so ARR[0] denotes that i th and i+1 th character are same
so if

string is : a a b b c c

then

ARR is : 0 1 0 1 0

then using this array, build a sum-query based segment tree
ended up being *O((N-K)log(N))

This solution is also in o(1) space complexity and o(n) time complexity. Plzz check it out.
check here

2 Likes

Thanks for ur approach @gyanendra371

1 Like

anyone can explain the logic behind prefix array & sliding_window used in this question?

basic approach is just to cal no of transaction bw i and i+1 that is through transaction array i created and ping me if anyone had problem

2 Likes

The answer will exceed int as the count will be more than the maximum no. that can be stored in the int datatype. This will lead to generation of random nos.

The author’s solution is same as sliding window. Instead of maintaining the prefix sum, he calculates it on the fly. Can you explain what part is not clear in the prefix sums one? BTW, do you know what is prefix sum and how it is used?

You can see author’s implementation for it.

The solution with segment trees should also fit in time limit, though being slower. I went through your code and there was a problem in the query function which can take O(N) complexity as you are not using the fact that sum for range has been calculated and you end up traversing each node till the end/ I suggest you to go through this easy tutorial first: My Experience: Segment Trees and lazy propagation and then reimplement the solution using segment trees to get better understanding.

Your logic seems complicated and tough to understand. Can you please go through the editorial and understand where your approach is different.

The logic is same as author’s solution where instead of maintaining the prefix sums in an array, we calculate them on the fly using sliding window concept.

The complexity is O(n^2) as you are building the whole sub-string again (StringBuilder function is called n times).

Okay Thanks, i had read somewhere that appending as well as deleting from 0th index would only take o(1). Can you point you whats wrong with the algo as it gave WA in the contest? or any edge cases i’m not considering.

After thinking foe a while, I get it now!
@likecs thanks for the reply.