[일반] F어케품?

[익명(182.231)]

merge sort tree에 이분 탐색 깔면 로그 세제곱 되서 터질 것 같은데 머지소트트리로 푼 사람들 어케한거지

PST는 공부하기 싫은데

[대학원오지마세요(publfl)]

내가 딱 그렇게 풀었음. 다만 차이라면 난 머지소트트리 안쓰고 버킷을 써서 시간이 sqrt(N) logn이 나왔다는점?

[익명(182.231)]

근데 숫자들 다른 수로 매칭시켜서 xor했을 때 0될 확률 낮추는 아이디어는 어케 떠올리는거임? 고인물들 웰노운인가

[대학원오지마세요(publfl)]

웰노운이지. 당장 올해 Meta Hacker Cup Round3의 C문제가 저런식으로 숫자 해싱해서 구간 XOR 혹은 구간합 생각하는 문제였는데

[익명(182.231)]

숫자 하나를 다른 숫자 하나로 해싱하는건 첨보네

[대학원오지마세요(publfl)]

정말 유명한 해싱응용 테크닉중 하나임. 알아두는거 추천

[익명(182.231)]

딴문제 다 개노잼이었는데 이거 하나 얻어가네 ㅋㅋ