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

×

Strings and Queries Help

I was trying this problem from Gym Contest. I don't know why I am getting WA on Test 2. Here's my code : Link.
I have used Hashing for checking number of palindromes and then Segment Tree to find the index for each query. Can anyone point out whats wrong in my code or give an alternate solution.
Thanks :)

asked 02 Jul '18, 13:54

dishant_18's gravatar image

5★dishant_18
61419
accept rate: 12%

1

why hashing?since length<30,u could just use an O(length^2) algorithm(stack)

edit:sorry not stack,dp

dp[i][j] denotes if substring s[i:j] is a palindrome

dp[i][j]=true if dp[i+1][[j-1] is true and s[i]==s[j]

(02 Jul '18, 14:00) vivek_19982996★

I tried with what you said.. Picked code from GFG xD. But it still shows WA :(
Here's the link : (https://ideone.com/mipoDA)
Am I doing something wrong still?

(02 Jul '18, 15:05) dishant_185★
1

It magically works now!!

(02 Jul '18, 15:14) dishant_185★

Thanks Vivek for suggesting alternate approach, but can you please point out where I am going wrong in Hashing?

(02 Jul '18, 15:34) dishant_185★

hashing does have countercases where it fails(collisions) :)

(02 Jul '18, 16:36) vivek_19982996★

But I don't think hashing can have collisions here as $4^{30}$ fits in long long( around $1.4 * 10^{18}$ ).

(02 Jul '18, 18:01) dishant_185★

Ur hash function is sum(4^i*(s[i]-'a'+1)) if i am not wrong

One countercase(collision) is:

string gd,ce

both strings have hash value 23

7+44=3+45=23

(02 Jul '18, 23:50) vivek_19982996★

Only 'a', 'b' and 'c' are allowed as letters :)

(03 Jul '18, 14:11) dishant_185★

OOh sorry!! I didnt read the question properly :(

(03 Jul '18, 14:21) vivek_19982996★
showing 5 of 9 show all
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:

×1,726
×655
×342

question asked: 02 Jul '18, 13:54

question was seen: 160 times

last updated: 05 Jul '18, 12:34