TACHEMIS - Editorial

editorial
, , , , ,
12

I tried the same, but got WA for unknown reason. Going through your submission. :slight_smile:

13

In your solution, you calculate powers of 1e9+7 upto 200000 in an unsigned long long and also do the hash calculations in ULL. How is it that the ‘overflowed’ values don’t give an error and the algorithm still works ?

14

@sanchit_h because unsigned long long values automatically wraps around 2^64 on overflow.

1 Like
15

Oh. Thanks! Also, do you know why we need to a multiply the RHS value by a certain power(specifically 4*mid-2) while calculating the difference in the forward and reverse hash ?

16

Got my error. my hash function wasn’t good enough. using @mugurelionut’s hash func, got AC :confused:
@sanchit_h Haven’t seen that part of his code thoroughly. But I can guess that it is due to his nature of hash function. See my code if it makes any better for you.

17

@sanchit_h: My hash function considers that we have a sequence of 2N values: character1, count1, character2, count2, …, characterN, countN. That’s why I needed powers of P up to 2N basically (and not only up to N). Then, when computing the direct hash value for a substring (in my solution from i-mid+1 to i+mid-1) we need the “prefix” hash up to i+mid-1 from which we need to subtract the contribution of the “prefix” hash up to i-mid. But this contribution appears multiplied by P^(2 * length), where length=2*mid-1 (thus, 2 * length = 4 * mid - 2). The hash for the reverse string is similar.

2 Likes
18

My O(Klog(K)) solution got tle. Then, i solved it with manacher. May be because of using mods :frowning:

19

Change this :"(n*(n+1))/2" to “((long long) n*(n+1))/2” and you will get TLE.

1 Like
20

Your code would require O(10^9) memory, because it is trying to “expand” the compressed string.

1 Like
21

One reason is that arr is not valid after putting in all those '#'es. You should have updated arr as well.

22

We cannot help you to debug your code, please only ask something related to the solution in the editorial!

23

@tuananh93 don’t be rude, of course he can ask for help

First thing is I do not understand how its possible that your code works when you read c[i] twice:

for(i=0;i<k;i++) {
	scanf("%c",&c[i]);
	scanf("%c%d",&c[i],&n[i]);
	res=res+(n[i]*(n[i]+1)/2);
}

but the problem is in n[i]*(n[i]+1)/2, try this test case:

1
1
A 1000000
2 Likes
24

but it will be typecasted int64 since res is int64…or not?

25

and one c[i] is just to manange new line

26

@mugurelionut @nims11 : I have seen hashing being used for string related problems many times, but never understood how its being implemented to solve such problems. Can you provide a brief overview of the concept used in this problem and how hashing is used coupled with a binary search ? (or a link to something similar where this has been explained?)

27

No, it’s not casted to long long if result is big enought, result type is depends on arguments if those are ints, result is int.

1 Like
28

@mugurelionut : hi,could you please explain your approach in detail,how exactly you are applying hashing ?

29

But I have handle them too in this part :-

int l = i - 1 - P[i];
l = l/2 - 1;
int r = i+1+P[i];
r = r/2 - 1;

30

Or could you tell me a test case where my code gives a WA?

31

@sandeepandey: In this problem hashing is used to check if a substring of the given string is a palindrome. Let’s say we have the substring from position i to position j. Then we compute a hash h1 for the substring from i to j and a hash h2 for the reverse substring from j to i. If h1=h2 then we can assume that the string from i to j is a palindrome (of course, we could be wrong, but it very unlikely if the hash function is good). The important part is to be able to compute such hashes in O(1) time (after some initial preprocessing).

2 Likes