Codeforces Round 875 (Div. 1)

https://codeforces.com/contest/1830

 

1D가 상당히 어렵게 나왔다.

1B에 TLE, MLE를 각각 한 번씩 받고, 1C를 정직하게(?) 구현해서 너무 늦게 제출했다.

사실 어지간히 B, C를 빠르게 AC 받았어도 곧바로 레드는 못 갔기에 그렇게까지 억울하지는 않긴 하다.

 

1A. Copil Copac Draws Trees

 

루트가 정해진 트리이기에 u - v라는 간선은 cur - par간의 간선이라고 생각해도 된다.

각각의 정점 i에 대해 chk[i]를 i가 트리에 추가된 회차라고 하자.

1) cur - par 간선이 par - (parent of par)보다 먼저 나온다면 -> chk[cur] = chk[par] + 1

2) cur - par 간선이 더 나중에 나온다면 -> chk[cur] = chk[par]

따라서 루트 노드인 0번 노드부터 dfs를 돌면서 chk을 위에서부터 순서대로 채워주면 모든 chk값을 얻을 수 있다.

chk값의 최댓값이 답이 된다.

 

1B. The BOSS Can Count Pairs

 

관찰 : 왜 굳이 a[i], b[i] 제한을 N으로 잡았을까?

 

a[i] * a[j] = b[i] + b[j]

1) a[i]가 SQRT보다 크다 : b[i] + b[j] <= 2N이므로 a[j] <= 2SQRT이다.

-> 정해진 a[i]에 대해서 b[j] = a[i] * a[j] - b[i]여야만 (i, j) 쌍이 가능하다.

-> 따라서 모든 a[j] <= 2SQRT인 j에 대해서 chk[a[j]][b[j]]++를 해두었다고 가정하자.

-> 그러면 a[i] >= SQRT인 i에 대해서 0 ~ 2SQRT인 x에 대해서 ans += chk[x][a[i] * x - b[i]] 를 하면 된다.

 

2) a[i]가 SQRT보다 작다 : 어떤 a[j]에 대해서 SQRT보다 작은 모든 a[i]를 고려해주면 된다.

-> 정해진 a[j]에 대해서 b[i] = a[i] * a[j] - b[j]여야만 (i, j) 쌍이 가능하다

-> 따라서 모든 a[i] <= SQRT인 i에 대해서 chk[a[i]][b[i]]++를 해두었다고 가정하자

-> 그러면 모든 j에 대해서 0~SQRT인 x에 대해서 ans += chk[x][x *  a[j] - b[j]]를 하면 된다.

 

모든 i, j에 대해서 최대 2SQRT 정도의 iteration을 거치므로  NsqrtN의 복잡도를 가지게 된다.

 

C. Hyperregular Bracket strings

 

Bracket 질을 할 때의 기본은

a) 길이 2N인 Bracket sequence의 종류는 Catalan(N)이다.

b) '(' = 1, ')' = -1이라고 했을 때 각각의 지점에 대해 prefix sum을 구할 수 있다. -> 이때 psum[i] >= 0, psum[2N] = 0

 

event 1) 어떤 [L, R), [l, r)에 대해서 L <= l <= R <= r로 겹친다고 가정하자  (뒤쪽이 열린 구간임에 유의)

-> 만일 psum[l] > psum[R]이라면 [l, r]은 psum[R] - psum[l] < 0이기에 regular bracket이 될 수 없다.

-> 만일 psum[l] < psum[R]이라면 [L, R]은 psum[l] - psum[L] (=psum[R]) < 0이기에 regular bracket이 될 수 없다.

-> 따라서 반드시 psum[L] = psum[l] = psum[R] = psum[r]이 된다.

-> 그러면 경우의 수는 Catalan((l - L) / 2) * Catalan((R - l) / 2) * Catalan((r - R) / 2)가 된다.

 

event 2) 만일 [L, R), [l, r)에 대해서 L <= l <= r <= R로 겹친다고 가정하자

-> 그렇다면 [l, r)에서 따로 regular bracket을 만들고 [L, l) + [r, R)이 regular bracket을 만들면 된다.

-> 그러면 경우의 수는 Catalan( (R - L) / 2 - (r - l) / 2) * Catalan((r - l) / 2)가 된다.

-> 이때 이것은 [L, L + r - l), [L + r - l, R)과 값이 동일하다.

 

event 2과 event 2를 통해서 구간들을 잘 관리하면 되겠다는 생각을 할 수 있다.

 

Sol1) 멍청하고 정직한 풀이 (내 풀이)

Stack처럼 구간들(set으로 관리)을 쌓아간다는 생각을 하자.

예를 들어 만일 set1에 {x1, x2, x3, x4}가 있다면 psum[x1] = psum[x2] = psum[x3] = psum[x4]이라는 뜻이다.

그러면 이것보다 위에 또 다른 set2 {y1, y2, y3, y4}가 stack되어 있다고 가정하자.

-> 그렇다면 이것은 set2의 y1~y4가 x[i] <= y[1] < y[4] < x[i + 1]로 하나의 구간에 함께 포함된다는 의미이다.

 

이렇게 Stack을 정의했다면 구간 [u, v)를 순서대로 정렬해서 넣기 시작하자.

1) 새로운 구간 [u, v)가 들어왔을 때 [u, v)가 y[i] <= u < v <= y[i + 1]을 만족한다.

-> 그렇다면 [u, v)는 하나의 구간 내에 함께 포함되므로 위쪽에 set3 = {u, v}를 하나 더 stack시키면 된다

2) 새로운 구간 [u, v)가 들어왔을 때 y[i] <= u <= y[i + 1] < v를 만족한다.

-> 이러면 u, v가 set2에 포함된다는 뜻이다.

-> 따라서 set2에 추가하여 {y1, y2, y3, y4, u, v}가 된다.

-> 이때 만약에 x[i] <= u <= x[i + 1] < v를 만족한다면 set2와 set1이 겹쳐지므로 event 1에 의해서 모두 psum이 같아진다.

-> 따라서 set1에 set2가 병합되어 set1 = {x1, x2, x3, x4, y1, y2, y3, y4, u, v}가 된다.

3) 새로운 구간 [u, v)가 들어왔을 때 Max(y) < u를 만족한다.

 -> 구간들은 모두 정렬되어 있었으므로 set2에 더 이상 추가될 수 있는 구간들이 없다.

-> event 2에 의해서 우리는 [L, R), [l, r)은 [L, L + r - l), [L + r - l, R)과 계산값이 동일함을 확인할 수 있다.

-> 따라서 set 2의 원소들이 x1 <= y[1] <= y[4] < x[i + 1]이라고 가정한다면

-> set 1 = {x1, y2 - y1 + x1, y3 - y1 + x1, y4 - y1 + x1, x2, x3, x4}로 바꾸어버려도 계산값이 동일하다.

-> 이때 y4 - y1 + x1 <= y4이기에 x1 ~ y4 - y1 + x1은 후에 다른 구간들에 영향을 끼치지 않으니 이래도 된다.

 

맨 처음에 [0, N)을 stack의 바닥에, 맨 마지막에 [N + 2, N + 2)라는 가상의 구간을 넣으면 마지막에 set이 하나 남는다.

맨 마지막의 set에 {z1, z2, ... zk}라면 답은 Catalan((Z2 - Z1)/2) * Catalan((Z3 - Z2)/2) * ...이 될 것이다.

위의 풀이를 보면 set을 합치는 과정이 여럿 보이는데, 작은거 큰거 테크닉을 써야 TLE를 받지 않을 것이다.

사실 애초에 정해가 이게 아니다 보니 저격 테케가 있을지는 잘 모르겠다.

https://codeforces.com/contest/1830/submission/207653111

결과물만 놓고 보면 그렇게까지 구현이 더럽지는 않다.

 

Sol2) XOR hashing을 통한 이쁜 구현 (정해)

위의 관찰을 보면 다음과 같은 생각을 할 수 있다.

event 1)에서는 [L, l), [l, R), [R, r)이 각각 하나의 구간을 이루고

event 2)에서는 [L, l) + [r, R)이 하나의 구간을, [l, r)이 하나의 구간을 이룬다고 생각을 할 수 있다.

 

그러면 적당히 랜덤한 숫자 x1을 L, R에, x2를 l, r에 부여한다고 생각하자.

-> 이후 prefix_XOR[i]을 통해서 각 숫자 1 ~ N에 대해서 적절한 해시값을 구할 수 있다.

-> 만약 prefix_XOR[i] = prefix_XOR[j]라면, i와 j가 같은 하나의 구간에 속한다고 생각을 할 수 있다.

len[i] = (prefix_XOR[j] = i인 j의 개수)라고 정의한다면

ans = Catalan(len[0] / 2) * Catalan(len[1] / 2) * ...의 방식으로 답을 구할 수 있다.

https://codeforces.com/contest/1830/submission/207713705

 

사실 XOR hashing이라는 것을 알지도 못했지만 

1) [L, l) + [r, R)이라고 생각하는게 아니라 [L, L + r - l), [L + r - l, R)으로 바꾸는 생각했다는 점

2) l, r < n이라는 조건을 굳이 주었다는 점

을 전혀 인지하지 못한 것도 큰 것 같다.

사실 내 풀이도 Catalan(N = 1e9)은 빠르게 구할 수 없기 때문에 l, r이 커지면 답을 못 구하는 것은 매한가지긴 하다.

 

1D. Mex Tree

 

보자마자 당연히 해볼만한 생각은 연결된 u - v에 대해서 반드시 val[u] != val[v]가 되도록 배정하는 것이다.

관찰을 해보면 이렇게 되면 (val[i] = 0인 i의 개수) + n * (n - 1)이 됨을 알 수 있다. (= 예제는 이 값이 답이다)

그러면 이제 val[u] = val[v]로 만들어서 MEX(u, v)를 희생시키는 생각을 할 수 있다.

예를 들어 (1, 3), (1, 4), (1, 5), (1, 6), (1, 2), (2, 7), (2, 8), (2, 9), (2, 10) 정도면 val[1] = val[2] = 1을 주는게 이득이다.

 

이것을 조금만 더 일반화 한다면

dp[cur][i][j] = (cur의 val값은 i이고, cur에서 부터 val이 i값인 노드들로만 연결된 노드의 개수가 j일 때 최댓값)이면

A - B를 연결시킨다고 가정했을 때 dp[A] 값과 dp[B] 값을 합쳐서 새로운 dp[A]를 구할 수 있다.

-> ex) nxt_dp[0][i + j + 1] = dp[A][0][i] + dp[B][0][j] - (i + 1) * (j + 1) + subtree[A] * subtree[B]

이것을 단순히 하면 A - B 연결은 N번, nxt_dp를 만드는 과정은 subtree[A] * subtree[B]이니 대충 O(N^3)이다.

ㅡㅡㅡ콘테 중 생각한 부분

 

자 저 풀이는 완벽하게 맞고 optimization을 하면 된다.

0) 위의 풀이는 이미 O(n^2)이다.

sub[i] = (i의 subtree의 크기), calc[i] = (i보다 아래의 tree dp를 하면서 한 계산의 횟수)라고 가정하면 위의 dp에서는

calc[cur] <= calc[child1] + calc[child2] + .. + sum( sub[cur] * sub[child] )가 된다.

 

가정) calc[i] <= sub[i] ^ 2 : 일단 calc[leaf] = 0이니 처음에는 성립한다.

-> calc[child1] <= sub[child1] ^ 2이므로 위의 식을 다시 쓰면

-> calc[cur] <= sub[child1]^2 + ... + sum (sub[cur] * sub[child] ) <= (sub[c1] + sub[c2] + ...) ^ 2 = sub[cur]^2 

따라서 위의 tree dp에서의 계산은 O(n^2) 이하이다.

https://codeforces.com/blog/entry/100910 의 #7 참고

 

1) 관찰 : 만일 같은 값인 노드들이 sqrt(n)개가 함께 연결되어 있다고 가정하자

-> 그렇다면 이미 여기에서 sqrt(n) * sqrt(n) = n 정도의 손해를 봤기 때문에 답이 벌써 n^2 보다 작다

-> 따라서 dp[cur][i][j]에서 j 값이 sqrt(n)을 넘지 않는다는 것이다.

-> 이게 시간 복잡도를 O(NsqrtN)으로 바꾸어 줄거라는 믿음의 도약을 하면 TLE를 받지 않는다.

 

엄밀한지는 모르겠는 증명

a) 어떤 A, B의 subtree가 합쳐질 때 A, B 중 subtree가 하나라도 sqrt보다 큰 경우 (WLOG A > sqrt)

-> 이때 어차피 A와 B가 합쳐지면 사이즈가 sqrt로 유지되니까 B는 그냥 사라진다고 생각할 수 있다.

-> 모든 원소는 딱 한 번만 사라질 수 있다.

-> 따라서 최대 N번 사라질 수 있고, 최대의 계산은 NsqrtN이다.

b) A, B가 모두 sqrt보다 작은 경우

-> 최초로 어떤 subtree의 크기가 SQRT가 되는 상황을 생각해보자.

-> 그렇다면 당연히 이게 만들어질 대 subtree가 1개씩 커지는 것이 계산량이 제일 많다.

-> 즉 calc[cur] <= sub[cur] + (sub[cur] - 1) + .. + 1 <= (sub[cur])^2 <= N 이다.

이때 최초로 subtree가 sqrt보다 커지는 상황은 sqrt번 이하이고, 따라서 b의 계산도 NsqrtN 이하.

 

2) 문제의 MLE limit이 256MB이다.

-> 위쪽의 관찰을 보면 j값은 항상 subtree[cur]보다 작다는 것을 알 수 있다.

-> 따라서 전위 순회를 하였을 때 주는 값이 in이라고 가정한다면

-> dp[cur][i][j]로 저장하는 대신에 dp[i][ in[cur] + j ]에 저장하더라도 아무 문제가 생기지 않는다.

-> cur과 child가 같은 메모리를 공유하지만 child가 cur에게 합쳐지고 나서야 그 메모리를 사용하기에 상관없다.

 

이상 간단한 Tree dp인데 잘 최적화시키는 문제였다.

https://codeforces.com/contest/1830/submission/207718827

위의 코드는 정말 대충 만들어서 왜 통과하는지는 모르지만 통과한다.