A. Mahmoud and Ehab and the even-odd game
먼저 내가 숫자 $n$을 선택하고, 상대방 부터 1보다 크거나 같고 $n$보다 작거나 같은 숫자 하나를 말해서 $n$에 뺀다. 나는 홀수만, 상대방은 짝수만 뺄 수 있는데, $n$에 뺄 숫자를 말 할 수 없는 경우 진다. 모두가 최선을 다해서 게임을 할 때 누가 이기는지 구하는 문제다.
$n$이 홀수면 상대방먼저 얘기할 수 있으므로 $n$보다 작은 짝수를 뺄 것이다. 그러면 홀수가 남을 것이고, 내가 그 수를 빼버리면 0이 되어 상대방은 더 이상 수를 뺄 수 없으므로 내가 이긴다.
$n$이 짝수면 상대방먼저 얘기할 수 있으므로 $n$을 얘기하면 바로 내가 진다. 따라서 $n$이 홀수면 내가, 짝수면 상대방이 이긴다.
B. Mahmoud and Ehab and the message
상대방에게 문자를 보낼건데 문자의 내용은 총 $m$개의 서로 다른 단어로 이루어져있다. 그리고 단어마다 문자의 비용이 각각 다르다. 그리고 각 단어들은 같은 뜻을 가진 다른 단어로 바꿀 수 있다. 문자로 보낼 문장의 단어를 같은 뜻을 가진 단어로 바꾸어서 문자를 보내는 최소의 비용을 구하는 문제다.
전체 단어들을 map<string, int>의 index에 저장하고 그 비용들을 map<string, int>의 value에 저장하자. 그리고 같은 뜻을 가진 단어들의 group이 주어지면 그 그룹에 속하는 단어들의 최소 비용을 구해서 map[단어]에 update하면 map에는 최소 비용이 저장되어 있을 것이다.
C. Mahmoud and Ehab and the wrong algorithm
어떤 친구가 트리에서 최소버텍스커버를 구하는 알고리즘을 고안해왔다. 깊이가 짝수인 노드의 개수와 홀수인 노드의 개수 중 작은 값이 최소버텍스커버라고 생각했다(root의 깊이는 0). 그런데 이 알고리즘은 틀린 알고리즘이다. 이 알고리즘이 틀렸다는 예시의 트리를 하나 출력하고, 이 알고리즘을 적용시켰을 때 맞는 트리를 하나 출력하는 문제다. 즉, 최소버텍스커버가 깊이가 짝수인 노드의 개수와 홀수인 노드의 개수 중 작은 값이 아닌 트리 하나와 깊이가 짝수인 노드의 개수와 홀수인 노드의 개수 중 작은 값인 트리 하나를 출력하는 문제다.
이 알고리즘이 맞는 트리를 구하는건 간단하다. 트리를 list처럼 쭉 연결시키거나 root에 나머지 노드를 모두 붙히거나 아무렇게나 해도 된다.
이 알고리즘이 틀린 트리를 구하는 것도 간단한데, 예제에 힌트가 있다.
예제에선 노드가 8개인 그래프를 주었는데 필요 없는 부분을 잘라내면 딱 6개가 나온다. 5개 이하로는 절대로 알고리즘의 예외인 케이스를 만들 수가 없다. 왜 그렇냐면... 나도 모르겠다. 예제를 보고 필요없는 부분을 잘라내서 가다듬으니 이런 형태가 나왔고, 5개 이하로는 아무리 만들어도 케이스가 안 나왔다.
아무튼, 이런 형태의 그래프를 구성해도록 6개의 노드를 소모하고, 나머지는 이 그래프의 root 위에 list처럼 주르르륵 연결시키면 된다.
솔직히 예제를 안 줬으면 엄청 오래 걸렸을 문제다. 다행히 예제를 보고 잘 캐치해내서 나름 빠르게 풀었다.
D. Mahmoud and Ehab and another array construction task
코드포스 풀면서 본 최악의 문제
배열 $A$가 있는데, 똑같은 길이의 배열 $B$를 만드려한다. $B$는 사전순으로 $A$보다 크거나 같아야하며, $B$의 각 원소는 2 이상의 정수이며 $B$의 모든 원소의 gcd는 1이다. 사전순으로 가장 작은 $B$를 구하는 문제다.
다시풀어라해도 못 풀 문제고 안 풀 문제고 안 볼 문제기때문에 코드따라 읽어나가겠다.
먼저 200만까지 모든 수를 소인수 분해해서 저장해두자. 그리고 set에 2부터 200만까지 모든 수를 insert하자.
$B$의 각 원소를 for문으로 앞에서부터 결정해 나갈건데, 사전순으로 $A$보다 크거나 같아야 하므로 $i$번째 원소를 결정할 때, 이전의 원소가 $A$의 값 보다 컸다면 $i$번째 원소는 $A$의 $i$번째 원소보다 크거나 같을 필요가 없다. 따라서, 그런 경우에는 set의 제일 작은 값을 $i$번째 원소로 결정하며, 아닌 경우에는 set에서 $A$의 $i$번째 원소보다 크거나 같은 값 중 가장 작은 값을 $i$번째 원소로 결정한다.
결정을 했으면, $b_i$의 소인수들의 배수들을 set에서 전부 제외시켜버리자. $b_{i + 1}$원소를 결정할 때 gcd가 1인 원소만 set에 있게 될것이다.
그런데 왜 10만이 아니라 200만이냐면, $b_i$는 적어도 $a_i$보다 크거나 같고 가장 작은 소수를 고르는데, 만약 $n$이 10만이며, $a_i$도 모두 10만이라면 최악의 경우 10만보다 큰 10만개의 소수를 고르게 될것이다. 그런데 소수의 간격은 대략 $logn$이므로 $10^5 * log 10^5 2 * 10 \simeq 2*10^6$이다.
tutorial엔 왜 200만인지 설명도 언급도 없으며 3초 제한인데 tutorial코드 그대로 돌려도 2.5초가 나오며 조금만 잘 못 만져도 2950ms가 나온다. 풀이를 보고 화난 건 처음이기때문에 다른 의미로 정말 두고두고 기억될 문제다.
E. Mahmoud and Ehab and the xor-MST
$n$개의 노드를 갖는 그래프를 만드는데 노드의 index는 $[0, n - 1]$이다. 이 그래프는 complete graph인데, 각 edge의 cost는 두 노드의 index의 xor연산을 한 값이다. 여기서 mst를 구하는 문제다.
그래프를 모두 그려놓고 mst를 만드려고 생각하면 복잡하다. 0과 1의 노드를 갖는 base graph에 2와 3 ... $n - 1$노드를 순서대로 추가한다고 생각해보자. 그리고 새로운 노드를 추가할 때 기존의 모든 노드와 edge를 연결시킨다고 생각해보자. 왜 이렇게 생각해도 되냐면 base graph는 그 자체로 mst가 될것이고, mst의 정의에 따라 새로 그래프에 추가시킬 노드를 mst에 추가시켜야 하기 때문에 그래프에 노드를 추가하면서 생긴 edge들 중 가장 작은 cost를 갖는 edge를 mst에 추가시켜도(또는 추가시켜야) mst가 되기 때문이다.
그럼 이제 알아야할 것은 새로운 노드를 그래프에 추가시킬 때 마다 mst에는 어느 엣지를(얼마의 cost를) 추가시켜야 하는지 알아야한다. 조금 주먹구구식의 방법이지만, base graph에 노드를 하나하나 추가시켜나가며 mst에 추가할 cost를 계산해보면 아래와 같다.
우선, 관찰해보면 홀수 index를 가진 노드가 추가되면 minCost는 1이다. 즉, mst에 추가될 cost는 1이다. 그리고 짝수 index를 가진 노드가 추가되면 규칙이 없어보이는 값들이 minCost가 되는데, 한 가지 주목할 점은 2의 제곱수가 되는 경우에는 index가 minCost가 된다는 점이다. 여기에 착안해서 2의 제곱수를 갖는 값들을 기준으로 짝수 index의 합을 구해보자. $sum([1, 2]) = 2, sum([3, 4]) = 4, sum([5, 8]) = 10, sum([9, 16]) = 24, sum[17, 32] = 56$이 된다. 규칙이 없는 것 처럼 보이지만.. $sum([2^{k - 1} + 1, 2^k]) = 2^k + (2^{k - 2} * (k - 2))$가 된다. 물론 k가 2 이상일 때만이다.
이 규칙을 이용해서 dp배열을 아래와 같이 정의해보자. $dp[k]$는 $[0, 2^k]$까지의 mst의 값. 그러면 $dp[0] = 1, dp[1] = 3$이 되며 $dp[i] = dp[i - 1] + 2^i + (2^{i - 2} * (i - 2)) + (2^i - 2^{i - 1}) / 2)$가 될것이다. 뒤에 추가된 $(2^i - 2^{i - 1}) / 2$는 홀수 index의 값들의 합이다.
이제 2의 제곱수에 대해 dp를 모두 채웠다. 2의 제곱수들의 합으로 모든 숫자를 다 만들 수 있으므로, 주어진 $n$보다 작거나 같으면서 가장 큰 2의 제곱수의 dp배열 값을 ans에 더하고 $n$에 그 제곱수를 빼주는 작업을 $n$이 0이 될 때 까지 반복하면 답을 구할 수 있다.
dp점화식이 거북하면 map을 이용해서 2의 제곱수를 index로 바로 저장하면 좀 더 간단해 보이고 구현도 쉬워진다.
아이디어는 바로 캐치해냈지만 저 점화식을 얻어내기까지 엄청난 시간이 걸렸다. 문제를 푼 1시간 20분을 저 점화식을 구하는데 썼다고 해도 과언이 아니다.
먼저 xor연산의 특성상 bit의 msb의 값이 커질 때 마다 index의 값 그대로 들어간다는 것을 발견했고 따라서 2의 제곱수마다 2의 제곱수가 더해진다는 점을 발견했다. 또, 2의 제곱수들 사이의 수는 가장 큰 bit를 지우는게 최선이기때문에 minCost는 가장 큰 2의 제곱수의 index가 추가된 후부터 추가된 index들에게만 영향을 받는다는 점을 알아냈다.
따라서 2의 제곱수가 실마리라 생각하고 2의 제곱수를 기준으로 점화식을 세우기 시작했는데 점화식을 계산할 때 1도 같이 생각하면서 계산하려하니 도저히 답이 안 나와 짝수 index만 계산하고 홀수 index는 개수만 세어주면 되니 짝수 index만 계산했다. 다행히 고등수학에서 자주보았던 순열의 형태였기때문에 금방 캐치할 수 있었다.
F. Mahmoud and Ehab and yet another xor task
$n$길이의 배열과 $q$개의 query가 주어진다. qeury에는 $l$과 $x$가 주어지는데, $[0, l - 1]$의 subArray의 subSequence들 중 원소들의 xor의 결과가 $x$인 subSequence의 개수를 요구하는 query다. subSequence는 연속되지 않아도 되는 원소들의 배열이다.
$l$을 0부터 $n - 1$까지 1씩 늘려가며 subArray의 subSequence의 xor의 결과들을 모두 구해놓으면 $l, x$ query에 대해 $[0, l]$의 subArray의 subSequence의 xor의 결과 값이 $x$인 subSequnce의 개수를 모두 알 수 있다. $i$번째 원소까지가 subArray의 범위일 때 $j$값을 갖는 subSequence의 개수는 $dp[i][j] = dp[i - 1][j] + dp[i - 1][j XOR j]$로 구할 수 있다. 하지만 $j$가 최대 약 100만 이므로 dp테이블을 이런식으로 구성할 수 없다.
따라서 dp테이블을 최적화 시켜야하는데, 그러기 위해선 두 가지 사실을 알아야한다.
첫 번째로, $[0, l]$범위에 subSequence들의 xor의 결과들의 set에 $x$와 $y$가 존재한다면 $x XOR y$도 그 set에 존재하게된다.
두 번째로, $x$가 set에 있으나 $y$가 없으면 $x XOR y$도 없다. (증명은 tutorial에)
