Blogewoosh #1 translated

원본: https://codeforces.com/blog/entry/61205

Blogewoosh #1 - Codeforces

Radewoosh의 블로그에 올라온 신기한 트릭을 리뷰한다.

해결해야 할 원본 문제는 여기서 볼 수 있다. https://szkopul.edu.pl/problemset/problem/wTy-sxQCIKry0Ml-6RvM0L78/site/?key=statement

Zadanie Różne słowa (slo) - Problemset - SZKOpuł

문제 내용

ASCII 코드 48 - 122 (총 75개) 로 이루어진 길이 5 문자열 \(S_{1}, S_{2}, \dots, S_{n}\)이 있다.

이 때 두 문자열의 5개 인덱스가 모두 다르다면 두 문자열을 really different하다고 할 때, \(S_{i}, S_{j}\)가 really different한 \((i,j)\) 쌍을 구하자. 단, 답이 100,000보다 크다면 100,000개만 찾아도 인정된다.

Naive \(O(75^5)\)가 잘 안되고, 몇 가지 시도를 해봐도 really different라는 조건이 너무 까다롭다.

\(O(n^2/32)\)같은 bitset이 되는 것 같긴 한데 일단 논외.

 

Binary Hashing Trick

우선, 길이 5인 문자열을 새로운 데이터 (문자, 인덱스) 로 인코딩하자. 이렇게 하면 abcde와 bcdea 같은 예를 구분할 수 있다. 가능한 데이터의 종류는 75 * 5 = 225개가 된다.

이제, 225개의 정보 중 랜덤하게 절반 정도를 0으로, 나머지를 1로 바꾸면 각 문자열은 길이 5의 비트열로 바뀌고, 특히 정확히 반대인 두 비트열은 원래 really different한 문자열이었음을 알 수 있다. 따라서 문자열을 비트열로 바꾸고, 정확히 반대인 비트열을 갖는 두 인덱스들을 전부 set에 추가하면 된다.

 

다만 이 해싱은 정답을 굉장히 잘 놓친다. 서로 다른 두 데이터가 모두 0이 되거나 모두 1이 될 확률이 1/2이고, 그래서 really different한 두 문자열이 정확히 반대인 두 비트열이 될 확률은 \(\frac{1}{32}\)에 지나지 않는다. 즉, 이 알고리즘은 really different한 두 문자열 쌍을 \(\frac{31}{32} \approx 96\%\)의 확률로 놓친다.

 

하지만 96%? 어림도 없다 ㅋㅋ 이 알고리즘을 600번 정도 반복하자. 그럼 really different한 쌍을 놓칠 확률은 \((\frac{31}{32})^{600} \approx 5.33 \times 10^{-9}\)에 지나지 않는다. really different한 쌍을 모두, 또는 10만 개 이상 retrieve할 확률은 적어도 \(\displaystyle (1 - (\frac{31}{32})^{600})^{100000} \approx 0.9995\) 이상이다. enough!

 

시간 복잡도도 여유롭다. really different한 각 쌍이 여러 번 조회될 수 있는데, 평균적으로 \(d\)번 정도 조회된다고 하자. 그렇다면 시간복잡도는 \(O((d \cdot 100000 + 600n) \cdot (\log n) )\) 정도가 되는데 \(d \approx \frac{600}{32} < 20\)으로 ignorable하다. \(\log n\)은 set factor로, unordered_set을 쓰면 뗄 수 있다.

 

자세한 설명은 소스코드로.