Blogewoosh #1 translated

2020. 1. 14. 16:57CS 이론/알고리즘

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

 

Blogewoosh #1 - Codeforces

 

codeforces.com

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

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

 

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

Congratulations, you solved it! The problemset isn't perfect, but we always aim to make it better. To do that we need your help. Please, fill this form and leave your proposals for alogorithm and difficulty tags for this problem. Thank you! Thank you for y

szkopul.edu.pl

문제 내용

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을 쓰면 뗄 수 있다.

 

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

 

1 2 3 4 5