[IOI 2016 Day 2] Unscrambling a Messy Bug (BOJ 20089) ★

별점 : 추천, [★★★☆★]

한국어 지문 : 링크, 번역이 구립니다

 

문제 요약

$n$-비트 정수 집합을 관리하는 자료구조가 있습니다. ($64$-비트 정수, $32$-비트 정수랑 같은 맥락이고 역시 $n$은 $2$의 거듭제곱) 이 자료구조에 일련의 정수 삽입 후, 컴파일을 거친 뒤, 일련의 정수 조회를 할 수 있습니다.

 

이때 컴파일 과정에서 버그가 발생합니다. 버그는 $n$ 비트의 순서가 어떤 순열에 따라 치환되는 형식으로 나타납니다.

 

정수 삽입을 $w$(write)번 이내, 정수 조회를 $r$(read)번 이내로 하여 버그가 갖는 순열을 알아내세요.

 

부분문제 1 (20점)

문제를 제대로 이해했는지 확인하는 부분문제입니다.

 

다음의 $8$개 정수를 삽입하면 최대 두 곳의 순열이 뒤바뀐 위치에서 비트 $1$의 개수가 달라지게 됩니다. 이 부분을 잘 포착하면 버그 순열을 쉽게 찾을 수 있습니다.

 

$1 0 0 0\ 0 0 0 0$

$1 1 0 0\ 0 0 0 0$

$1 1 1 0\ 0 0 0 0$

$1 1 1 1\ 0 0 0 0$

$1 1 1 1\ 1 0 0 0$

$1 1 1 1\ 1 1 0 0$

$1 1 1 1\ 1 1 1 0$

$1 1 1 1\ 1 1 1 1$

 

#include "messy.h"
#include <bits/stdc++.h>
using namespace std; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
    
vi restore_permutation(int n, int w, int r) {
    assert(n==8);
    rep(i,1,8) {
        add_element(string(n-i,'0')+string(i,'1'));
    }
    compile_set();
    vi p(n); iota(all(p),0);
    vi idx;
    int a=-1, b=-1;
    rep(i,0,7) {
        if (check_element(string(i,'0')+string(n-i,'1'))) {
            a = i;
        } else break;
    }
    rep(i,a+1,7) {
        if (!check_element(string(i,'0')+string(n-i,'1'))) {
            b = i;
        } else break;
    }
    if (a != -1 and b != -1) swap(p[a],p[b]);
    return p;
}

 

부분문제 2 (18점)

부분문제 1과 같은 $8$개 정수를 삽입했을 때, 구체적으로 결과가 어떻게 나타날지 예상해 봅시다.

 

$1 0 0 0\ 0 0 0 0$ → $0 0 0 0\ 0 \color{red}1 0 0$ : $p_5=0$

$1 1 0 0\ 0 0 0 0$ → $0 0 \color{red}1 0\ 0 \color{blue}1 0 0$ : $p_2=1$

$1 1 1 0\ 0 0 0 0$ → $0 0 \color{blue}1 0\ 0 \color{blue}1 0 \color{red}1$ : $p_7=2$

$1 1 1 1\ 0 0 0 0$ → $\color{red}1 0 \color{blue}1 0\ 0 \color{blue}1 0 \color{blue}1$ : $p_0=3$

$1 1 1 1\ 1 0 0 0$ → $\color{blue}1 0 \color{blue}1 0\ 0 \color{blue}1 \color{red}1 \color{blue}1$ : $p_6=4$

$1 1 1 1\ 1 1 0 0$ → $\color{blue}1 0 \color{blue}1 \color{red}1\ 0 \color{blue}1 \color{blue}1 \color{blue}1$ : $p_3=5$

$1 1 1 1\ 1 1 1 0$ → $\color{blue}1 0 \color{blue}1 \color{blue}1\ \color{red}1 \color{blue}1 \color{blue}1 \color{blue}1$ : $p_4=6$

$1 1 1 1\ 1 1 1 1$ → $\color{blue}1 \color{red}1 \color{blue}1 \color{blue}1\ \color{blue}1 \color{blue}1 \color{blue}1 \color{blue}1$ : $p_1=7$

 

위와 같이 순열에 의해 새롭게 나타나는 비트를 통해 버그 순열을 찾을 수 있습니다.

 

부분문제 2는 이 과정을 $32$-비트에서 진행하면 되겠습니다. check_element는 $32+31+\cdots+2+1 = 528$ 정도의 상한으로 호출하게 됩니다.

 

#include "messy.h"
#include <bits/stdc++.h>
using namespace std; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
    
inline vi flip(vi v, int k) { v[k] ^= 1; return v; }
inline string str(vi v) {
    string r;
    for (const auto &e : v) r += '0'+e;
    return r;
}
    
vi restore_permutation(int n, int w, int r) {
    rep(i,1,n) add_element(string(i,'1')+string(n-i,'0'));
    compile_set();
    vi p(n), b(n), ch(n);
    rep(i,0,n-1) {
        rep(j,0,n-1) if (!ch[j]) {
            if (check_element(str(flip(b,j)))) {
                ch[j] = 1;
                p[j] = i;
                b[j] = 1;
                break;
            }
        }
    }
    return p;
}

 

부분문제 5: Full task

$896$이 우선 $128 \times \log_2 128$이라는 걸 눈치채야 합니다. (전 어디서 이 수가 튀어나온건지 한참 헤매었네요)

 

편의상 $q=p^{-1}$이라 합시다.

 

생각 1. 부분문제 2에서 $n+(n-1)+\cdots+1 = O(n^2)$의 스케일이었습니다. 이건 새로운 비트 하나가 어디에 위치했는지 다 돌아보기 때문에 발생하는 계산량입니다. 이걸 해결해야 합니다.

 

생각 2. 그렇다면 비트 개수가 $1$인 경우를 잘 활용해야 합니다. 비트 개수가 $2$개인 것들만 해도 $\binom n 2$이라 $O(n^2)$ 스케일이기 때문이죠.

 

관찰 1. 다음 $4$개의 정수를 삽입하면 무엇을 알 수 있을까요?

 

$1 0 0 0\ 0 0 0 0$

$0 1 0 0\ 0 0 0 0$

$0 0 1 0\ 0 0 0 0$

$0 0 0 1\ 0 0 0 0$

 

바로 $\{q_0,q_1,q_2,q_3\}$과 $\{q_4,q_5,q_6,q_7\}$을 알 수 있습니다!

 

생각 3. 그렇다면 이렇게 알고 있는 집합의 범위를 잘 활용하며 문제를 해결할 수 있지 않을까요?

 

$\{q_0,q_1,q_2,q_3\}$에서 $\{q_0,q_1\}$와 $\{q_2,q_3\}$로 범위를 구분짓는 방법을 생각해 봅시다.

 

$1 0 0 0\ 1 1 1 1$

$0 1 0 0\ 1 1 1 1$

 

관찰 1과 같은 원리로 $\{q_0,q_1\}$과 $\{q_2,q_3\}$를 파악할 수 있네요.

 

마찬가지로, $\{q_4,q_5,q_6,q_7\}$은 다음 두 정수를 삽입하여 $\{q_4,q_5\}$, $\{q_6,q_7\}$로 구분할 수 있습니다.

 

$1 1 1 1\ 1 0 0 0$

$1 1 1 1\ 0 1 0 0$

 

이를 재귀적으로 수행하면 전체 문제도 풀 수 있습니다.

 

그럼 $w$, $r$ 제한이 맞아 들어가는지 확인해 봅시다.

• 삽입 횟수를 확인합시다. $4+(2+2)+(1+1+1+1)$이 됩니다. 즉, $(n/2) \times \log _2 n$이 됩니다.
• 조회 횟수를 확인합시다. $8+(4+4)+(2+2+2+2)$가 됩니다. 즉, $n\log_2 n$이 됩니다.

모든 부분문제가 $w\ge n\log_2 n$, $r\ge n \log_2 n$을 만족하므로 100점을 받을 수 있습니다.

 

#include "messy.h"
#include <bits/stdc++.h>
using namespace std; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) begin(x), end(x)

void step1(string s, int l, int r) {
    if (l+1 == r) return;
    int m = (l+r)/2;
    rep(i,l,m-1) s[i] = '1', add_element(s), s[i] = '0';
    rep(i,l,m-1) s[i] = '1';
    step1(s,m,r);
    rep(i,l,m-1) s[i] = '0';
    rep(i,m,r-1) s[i] = '1';
    step1(s,l,m);
}

vi p;
void step2(string s, int l, int r, vi idxs) {
    if (l+1 == r) {
        p[idxs[0]] = l;
        return;
    }
    int m = (l+r)/2;
    vi front, back;
    for (auto i : idxs) {
        s[i] = '1';
        if (check_element(s)) front.push_back(i);
        else back.push_back(i);
        s[i] = '0';
    }
    for (auto i : front) s[i] = '1';
    step2(s,m,r,back);
    for (auto i : front) s[i] = '0';
    for (auto i : back) s[i] = '1';
    step2(s,l,m,front);
}

vi restore_permutation(int n, int w, int r) {
    step1(string(n,'0'),0,n);
    compile_set();
    vi idxs(n); iota(all(idxs),0);
    p.resize(n);
    step2(string(n,'0'),0,n,idxs);
    return p;
}