What is this kind of approach? (
[1])
I didn't understand this one.
[1]: https://www.codechef.com/viewsolution/19022775@mohitchandrak: Imagine a character s_i in the string that is in cell c (in the board) on the k-th step. Then the successor of that character s_{i+1} will be on the cell c in the k+1-th step, if it happens (call this an event). If s_i \ne s_{i+1}, then it requires one unit of power. Now the total power that is used over all operations can be thought of as a net effect of all such pairs (s_i, s_{i+1}), s_i \ne s_{i+1}. For each such pair, we can figure out on how many cells this event happens (it is K, except when the characters are among the first K or last K positions of the string, which is what the linked code considers).
2 Likes
my approach is kind of common sense approach.
first step–>>> As first we calculate maximum no. of transaction an element can do that is min( n-k , k).
max no of transaction an element can do
min of:-
1: k bcoz if we have a b c d e f then c can go 3 times transaction with d then d after that c will be gone .
a b c → b c d-> c d e-> d e f.
2: n-k bcoz if we have four element for ex a b c d , k=3 then a b c-> b c d; everyone has gone 1 transaction.
second step–>> then we calculate array of transaction element will do.
1: first element can do 1 transaction ; second can do either 2 or 1 if max limit is 1; third
element can do 3 transaction if max limit is not reached otherwise it will do transaction of max limit ;like this we build the array but
2: last element can do 1 transaction ; second last can do 2 only if max limit is not reached ; third last can do 3 if max limit is not reached else it will do that much transaction.
now ex to understand above approach
here k =3 ; just for understanding
elements; transaction array; max transaction can do;
a b c d;;;;;;;;;;;[1 1 1];;;;;;;;;;; 1
a b c d e;;;;;;;;;;;[1 2 2 1];;;;;;;;;;; 2
a b c d e f;;;;;;;;;;;[1 2 3 2 1];;;;;;;;;;;3
a b c d e f g;;;;;;;;;;;[1 2 3 3 2 1];;;;;;;;;;;3
if 8 elements then ;;;;;;[1 2 3 3 3 2 1];;;;;;;;;;;3
“similarly it go with any of k”
**third step->>>**now if s[i]!=s[i+1] then we just add the cost(count+=a[i]) as we know how many times it will go transaction with that element ; if s[i]==s[i+1] then no cost taken.
link for my code CodeChef: Practical coding for everyone
for better understanding please refere to link as code contain comments
11 Likes
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/19030972Can 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 
It had never occurred to me.
Thanks for this, never heard about prefix-sum before 
, 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
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.