likecs's blog

Doubt in Div2 QB round #336
By likecs, history, 8 years ago, In English

I have doubt why my solution failed for QB for round #336 Div2 during system testing.

Here is my approach for the question.(Assuming 0-based indexing of strings everywhere.)

Let us assume len(a) = 3, len(b) = 10 and a = 101 and b = 1001001001. So the required sub-strings are 100, 001, 010, 100, 001, 010, 100, 001 which are to be checked with 101. Here hamming distance is simply the no of distinct characters between string a and given sub-string of b. So the hamming distances are respectively 1, 1, 3, 1, 1, 3, 1, 1 i.e. total answer is 12 for this case.

Initially I found the number of ones and zeros in string a till a given position. (this is stored in sec[i][0] and sec[i][1] in my code).

Next we see that the 0th position of b is compared with only 0th position of a in all cases. The 1st position is only compared with the 0th (in sub-string 2) and 1st (in sub-string 1) positions of string a. the 8th position in b is compared with 1st (in sub-string 8) and 2nd (in sub-string 7) positions of string a and finally 9th position in b is only compared with 2nd position in string a. Rest all the characters between 2nd and 7th positions (inclusive) are compared with all the character positions of string a once in the cases possible.

In general the first 0 to len(a)-1 characters are only compared with 0 to given index vales of string a and the reverse happens for the ending characters. they are compared with last characters of a. The remaining middle characters i.e. fro len(a)th position to (len(b)-len(a))th position are compared with all the characters of string a.

Here is my code for the above implementation. http://codeforces.com/contest/608/submission/14948872.

I am only able to understand why this logic fails.

PS: All the solutions seen till now by me have done the opposite i.e. stored the count of zeros and ones for string b and traversed on string a. But i want to understand what difference does it make if I do the reverse.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I have stored the count of ones for string a and traversed on string b. You can check my solution 14950584 .

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you so much, your code really helped me to debug my code for each iteration. My logic had a small glitch when there was a overlap of cases from starting and ending position i.e. when len(a)>=len(b)/2. I thinks the pretest had no such test when len(a)>=len(b)/2. So, my logic regarding start and end index was bit incorrect and pretest being weak, it passed easily. Thank you once again, especially for quick response.

    → Reply