You are not logged in. Please login at www.codechef.com to post your questions!

×

SHIFTPAL- Editorial

9
2

PROBLEM LINK:

Div1
Div2
Practice

Setter- Hasan Jaddouh
Tester- Jakub Safin
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

Hashing (or precisely, Identifying Palindromic Sub-string using Hashing)

PROBLEM:

Given a string $S$ , tell how many $k-shifts$ of the string are palindromic. $k-shift$ of a string is, the string obtained on shifting every character right by $k$ positions (circularly).

QUICK EXPLANATION:

We know that we can obtain all cyclic shifts of an array by appending an array to itself and moving the $N-sized$ window over it (to get different cyclic shifts). We use this to avoid having to cyclically shift the string again and again. After that, we use the concept of hashing to check if the strings are palindrome or not.

EXPLANATION:

This editorial will have two parts. The first one will describe the cyclic-shift trick, and the other will describe the hashing part. It is expected that you have gone through the pre-requisites if concept of hashing is new to you. The basics of identifying palindrome string through hashing is given in the link under pre-requisites. Hence, the editorial will not explicitly describe on how to check that.

1.Cyclically Shifting Trick-

Whenever we are given the task to cyclically shift an array, or a string, we can use this trick to avoid having to actually cyclically shift the entire array again and again.

This trick says that, append the string/array to itself. Eg, if $S=abc$ then $S'=S+S=abcabc$. Now, consider the string from range $i$ to $i+N$ to obtain the $i'th$ cyclic shift of the string.

Eg-

alt text

Starting from $i=1$ $to$ $N$ ($1-based$ indexing) will give you $left$ cyclic shift of string, while decrementing from $i=N$ to $i=1$ will give you $right$ cyclic shifts of string. Now, I have one question to ask.

Why does this work? What is the foundation principle of this trick?

(Answer will be in Chef Vijju's corner)

2. Hashing the String-

You can refer to the setter's code here for the concept for now. Please note that the hash function and operations in it can vary from person to person. We will be discussing w.r.t. setter's solution first.

Now, we know the cyclic-shift trick. Using that, we can reduce the problem to "Find how many substrings (contiguous) of length $N$ are palindrome in the string $S'(=S+S)$"

If you've read the pre-requisite link, you would have got how we used the hash function of-

$h(x)= \sum_{i=0}^{i=n-1} ({101}^{i}*S_i)\%mod$ where $S_i=$ i'th character of the string.

Setter has used a similar hashing function of-

$H(X)= \sum_{i=0}^{i=n-1} ({31}^{i}*(S_i-`a'))\%mod$

The steps to check for palindrome are similar. At each step, he checks for a sub-string of length $N$, modifies the hash function according to what characters are present in the $N$ length window. This step involves, w.r.t. variable $hsh$ in his solution, removal of term with lowest power of ${31}^{i}$ and adding the term ${31}^{i}*(S_i-`a')$ to the function. (If you cannot make sense of this addition removal of lowest/highest power term, please refer again to link in pre-requisites). Can you try working out for $hsh2$ of setter's code? Answer will be in the tab below-

View Content

Now, what does this computation on hashing actually mean? At each step, $hsh$ is modified to represent the string shifted $left$ $(i+1)$ times, while $hsh2$ represents the reverse of string $S$ being cyclically shifted $right$ $(i+1)$ times. Compare them in the table below-

alt text

Can you actually tell the significance of ${31}^{i}$ in the hash function? As in, why should we take any constant, say $p$, and make hash function of type $H(X)=\sum_{i=0}^{i=n} {p}^{i}*S_i$. Why multiply with ${p}^{i}$ ?

The tester uses a similar concept, except that he tries to make his hash function even less error prone by introducing another prime number for $\%$ operation and making hash as $H(X)=H_1*p+H_2$ where $H_1$and $H_2$ and calculated similarly as described above. The tester explicitly uses our cyclic-shift trick. His $H$ represents the normal string $S$, which $H_i$ represents the reverse of string $S$. If hashes of these two are equal, then that means that the $N$ length sub-string, and its reverse are equal, which means that the string is palindrome. Hashes are updated in a manner, which is similar to "Sliding window", i.e. add contribution of new element, remove contribution of the oldest element (element to be removed).

A more formal description of tester's $H$ and $H_i$ function will be-

$H= \sum_{i=0}^{i=2N-1} {p}^ {i}*(S_i-`a ' + 1)$ for both $H_1$ and $H_2$ and

$H_i = \sum_{i=2N-1}^{i=0} {p}^{i}*(S_i-`a'+1)$, again, for both $H_{i1}$ and $H_{i2}$

In a gist, we "represent" the strings by hash function. If we find that the hash function of the string, and the reverse is equal, it means that the string is palindrome. The only thing to take care of is, your hash function must be good, and not have a high probability of error. Usually its acceptable if its probability of failing is $\le 0.001 \%$

SOLUTION:

For immediate availability of setter and tester's solution, they are also pasted in the tabs below. This is for your reference, and you can copy code from there to wherever you are comfortable reading them.

Setter

View Content

Tester

View Content

Editorialist's Solution will be put up on demand.

$Time$ $Complexity=$ $O(N)$ for setter and tester's solution.

CHEF VIJJU'S CORNER :D

1. Foundation of cyclic-shift principle-

View Content

2. Significance of ${p}^{i}$ in hash function.

View Content

3. A view on Hash functions-

View Content

4. Regarding any doubts which might arise after reading editorial :)

View Content

5. We did have a look at hashing solution of this problem. Does a solution without hashing exist? Its your task to find out! Check out the list of successful submissions :) . (I will update this section if there I am able to find a good solution without hashing).

6. An alternate perspective for understanding hash function.

View Content

7. Tester's Notes-

View Content

8. Some related problems on hashing-

This question is marked "community wiki".

asked 26 May, 04:05

vijju123's gravatar image

5★vijju123 ♦♦
15.1k11857
accept rate: 18%

edited 12 Jun, 17:26

admin's gravatar image

0★admin ♦♦
19.6k349497539

I have a doubt. If the function STRREV would have been available will this much of headache coding still be required?

(28 May, 21:06) byomkeshbakshy4★

Nice editorials @vijju123. I wish you could be editorialist for all rated contests :)

(29 May, 00:09) rj254★
2

OMG THAT WAS SO CUTEE!!

Its motivations like these that keep me going despite a few things <3

(29 May, 01:28) vijju123 ♦♦5★
1

@vijju123 nice job.

(08 Jun, 15:52) skyhavoc4★

Thank you @skyhavoc :)

(08 Jun, 16:21) vijju123 ♦♦5★

I solved this problem using Manacher's Algorithm. First I doubled the string and then used Manacher's Algorithm on the new string, so I only need to find out how many locations have a palindrome radius greater than length. And here is my solution: https://www.codechef.com/viewsolution/18664253

link

answered 27 May, 12:27

freeloop's gravatar image

6★freeloop
3443
accept rate: 47%

edited 27 May, 12:30

A nice alternative approach :)

(27 May, 15:06) vijju123 ♦♦5★

cool, that's really thinking out of the box :)

(28 May, 00:19) sorb19974★

I still dont understand why do we need to conider n+1 to 3*n-1 range and make increments of 2 while counting the ans ?

(06 Dec, 21:18) lmao_2★

If the characters are same, then the answer is equal to the length of string (e.g if s = "aaaa", answer is 4)

However, can the answer ever be greater than 2 if all characters aren't same?

If yes, can someone please provide an example. Thanks in advance.

link

answered 02 Jun, 08:29

i_luv_sumit001's gravatar image

4★i_luv_sumit001
04
accept rate: 0%

1

Good question...

(02 Jun, 09:28) l_returns4★
2

With "abaabaaba" the answer is 3 and with "abaabaabaabaaba" the answer is 5. Using more than three letters is also possible. With "cbabccbabccbabc" we get 3.

(02 Jun, 11:09) oconnor_robert4★

Thank you oconnor_robert :) I am terrible at coming up with test cases. How do you do it? Did you write a program to generate cases?

(02 Jun, 11:17) i_luv_sumit0014★
2

My first thought was "ababa". That fails because the a's at either end up next to each other. From that observation I realised that we need to double the other a's. Another way to think about it is using your observation. For s = "aaaa" we get 4. If we replace each 'a' with a palindrome, we will always get at least 4.

(02 Jun, 11:43) oconnor_robert4★

Nice work bro..

(02 Jun, 12:08) l_returns4★
1

"abbaabba" is also interesting and gives 4. This is different than my other examples because there are two unique palindromes that can be formed by shifting this one: "abbaabba" and "baabbaab".

(02 Jun, 12:09) oconnor_robert4★

wow, this is amazing! Thank you again :)

(02 Jun, 13:26) i_luv_sumit0014★
showing 5 of 7 show all
link

answered 27 May, 04:29

aryanc403's gravatar image

5★aryanc403
2.2k515
accept rate: 11%

edited 02 Aug, 16:26

I didn't read through your code very carefully, but it seems that you haven't accounted for the case when subtracting the two prefix sums, or two suffix sums makes it negative. You should add MOD to it in that case.

(27 May, 12:03) xrisk5★

You can check out my code here BTW I think I have written it quite clearly http://ix.io/1bvW

(27 May, 12:05) xrisk5★

My method of subtraction.

y=(a[1][k][2*l-i]-a[1][k][l-i]); y%=mod[k]; y=(y+mod[k])%mod[k];

(27 May, 14:36) aryanc4035★

Your code failed on sample case itself. What is the logic behind your hash function?

(27 May, 15:50) vijju123 ♦♦5★

Unable to format my comment.

This question was my first attempt with Hash. Yes, it also fails on sample test case.

m = some base. I took 26,101,1001 etc. But failed on all. There 3 for mod. All stored in modular airthmetic Hash for prefix s[0] s[0]*m+s[1] s[0]*m2+s[1]*m+s[2] s[0]*m3+s[1]*m2+s[2]*m+s[3]+....

similarly for s[2*l] s[2*l]*m+s[2*l-1] s[2*l]*m2+s[2*l-1]*m+s[2*l-2] s[2*l]*m3+s[2*l-1]*m2+s[2*l-2]*m+s[2*l-3]+....

for substring [i,j]

hash value (prefix[j]-prefix[i])*(modInv(m))^i //here i found error while writing this. Will try again and get back.

(27 May, 23:47) aryanc4035★
1

I formatted it for you. Time for a comfortable reading now :D

(28 May, 00:31) vijju123 ♦♦5★
showing 5 of 6 show all

Please tell why am I getting WA

https://www.codechef.com/viewsolution/18693156

Calulating cyclic shift strings using substring and checking with palindrome using reverse()

link

answered 29 May, 11:21

pro_porwalok's gravatar image

2★pro_porwalok
1
accept rate: 0%

I think the problem is that you forgot to add new lines. If there are multiple test cases, all of the results are printed one after another on the same line.

(31 May, 18:26) oconnor_robert4★
1

Ahhhh.. Such lame thing costed me 30-40 mins of contest time :( Thanks @oconnor_robert :)

(31 May, 22:08) pro_porwalok2★

This view content is excellent :D

link

answered 31 May, 17:30

rahul_iit's gravatar image

4★rahul_iit
111
accept rate: 0%

yeah it is.. :)
thanks to vijju...

(31 May, 18:32) l_returns4★

I am glad you liked it :) . It was written in a rush though XD

(31 May, 20:38) vijju123 ♦♦5★
View Content

can some one help me....thx in advance!!

link

answered 06 Jun, 23:45

praneeth18's gravatar image

2★praneeth18
1
accept rate: 0%

why you are writing so many #define in code? what is logic behind this?

Tester's solution

link

answered 09 Jun, 01:39

akash_92's gravatar image

2★akash_92
0
accept rate: 0%

2

Just to make our lives easier.

(10 Jun, 10:08) soham12346★

@vijju123

How to deal with the problem of rounding of powers of 'p' when the power value crosses mod value?

As in, when we are comparing hash and reverse hash, one hash is multiple of other hash(as given in prerequisite). But that holds true only if the power values round up at the same point for given string.

e.g consider string s=abbbbbba. ns = s+s = abbbbbbaabbbbbba

now if string under consideration is [2 7]. Suppose that while computing prefix array, power value rounds off at index 5. And suppose that while computing suffix array, power value rounds off at index 7.

So, the hash[2 7] using prefix array CANT BE EQUAL to hash[2 7] using suffix array.

How to deal with this problem?

link

answered 27 Jun, 15:31

sushu's gravatar image

1★sushu
11
accept rate: 0%

These factors depend strictly on your hash function. Check what the setter and tester have done, they did something different. They made it such that, instead of checking if $hsh$ is a multiply of $hsh2$ or not, they simply checked for $hsh1==hsh2$. Give a read to editorial if they havent. Try to get what is represented by the hash function, it will be easier to understand it.

(27 Jun, 17:15) vijju123 ♦♦5★

Editorial solution is expected to be put up so that we can relate with the editorial. Setter solution has been poorly explained and I couldn't get the logic behind the setter's code. Could you please tell me the logic behind setter's code?

(27 Jun, 18:39) sushu1★

What do you mean by "Setter solution has been poorly explained". What did you not understand?

I feel the concept is quite sufficiently explained and is easy to understand. Dry run a few iterations to understand.

Editorial solution is expected to be put up so that we can relate with the editorial.

-_- . The editorial explains setter's and tester's solution. What do I do then, copy paste setters code?

Could you please tell me the logic behind setter's code?

If such big editorial couldnt help you, I doubt my comment will. Please give more efforts before blaiming.

(27 Jun, 19:05) vijju123 ♦♦5★

Here is my clean hash solution : https://www.codechef.com/viewsolution/21761423 Manacher's Algorithm Solution : https://www.codechef.com/viewsolution/21760228

link

answered 07 Dec, 00:48

lmao_'s gravatar image

2★lmao_
312
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,677
×621
×341
×115
×98
×39

question asked: 26 May, 04:05

question was seen: 3,919 times

last updated: 07 Dec, 00:48