Help needed in Yalalovichik Strings (YVSTR) - December CookOff

general
1

Problem : https://www.codechef.com/problems/YVSTR

Can someone please help me find where is my


[1] failing. 

What I did was, firstly find the maximum contiguous subsequence of a particular character (stored in the vector cnt) (of course this subsequence is a substring), for ex. $"aabaabbb"$ has $cnt[a]$ = 2 and $cnt[b]$ = 3. These groups of substrings contribute a total of $\sum_{i=1}^{26} cnt[i]$ to the final result. Now, I partitioned the given string into groups such that each group contains only 2 different characters (these partitions, too are substrings as the groups considered are formed by contiguous indices of the string), and hashed the pair of frequencies of both the characters, then looked for the max frequency of the 1st character and corresponding max frequency of the 2nd and similarly for the 2nd character, taking care of subtracting the overlapping case.

Can someone please let me know if my logic is flawed or the implementation or there are some corner case I am missing. I've considered a lot of examples but no luck, only WA :(.


  [1]: https://www.codechef.com/viewsolution/22073116
2

Test cases,

frkeecbpdipufh - Answer = 26, yours = 25

uqunublmoiitnckle : Ans = 30, yours = 29

jataxgpdmyldx : Ans = 22, yours = 21

dggxbpvzwalxogufh : Ans = 32, yours = 31

esuboedrbhuqbauedghc: Ans = 30, yours = 29

EDIT, after correction

vrzgfwvrftwapdt : Ans = 23 , Yours = 24

3

Okay, corrected them all, still WA :frowning:

4

@kshitij_07 i’ve added another ts.

1 Like
5

I did same.My code is also running correctly on your test cases but getting WA after submission!

6

Hey!

By seeing your code, I guess that for different pairs of consecutive characters you are trying to give different Hash values (gamma in your code). But for strings like “aaayyyy” and “lleee” gamma obtains the same value (125 in this case). I think that is why your code is failing in the
**
input:

1

4

ayle

Your output: 6

Correct output: 7
**
If I am not wrong in interpreting your code you can remove this problem by setting “gamma = 27*alpha + beta”.

Still, the problem does not end here, I think there is one more problem in the last part of the code. Suppose the given string S has substrings “abbbb” “aabbb” and “aaabb” then the contribution by these substrings (ignoring contribution by substrings containing only a or only b) in the last part of your code is computed as 3*2 + 4*1 - 2*1 = 8 but their actual contribution is 9.

I hope this will be useful in debugging your code :stuck_out_tongue:

7

Thanks a lot for going through my code. As you mentioned, I fixed the hashing part and corrected the last segment too, but still getting WA. Btw, I compared my outputs for several random outputs from SPOJ Toolkit with some of the AC codes, all give the same answer :/. Anyway thanks a lot for commenting :slight_smile:

8

Here are a bunch of testcases for which your code fails: https://ideone.com/pKwvht The expected outputs are 4258, 3145, 5410, 4330 respectively