SEERC 2019 C. Find the Array

문제 링크 (BOJ 17957)

 

위 문제는 정말 나를 멘붕에 빠뜨린 문제였다. ICPC 팀 연습에서 만났던 문제이고, 1시간 반 넘게 고민했지만 감도 못 잡고 풀지도 못했다. 연습이 끝나고 읽은 풀이가 정말 놀라워 정리해보았다.

 

Problem

이 문제는 Interactive 문제이다.

 

$N(1\leq N \leq 250)$개의 서로 다른 수로 이루어진 배열 $A$가 있다. 최종적으로 우리는 이 배열을 알아내야 한다. 그러기 위해 2가지 쿼리를 날릴 수 있다.

• 인덱스 $i$를 골라 $A[i]$를 얻는다.
• 인덱스 $k$개 $i_1, \cdots i_k$에 대해 $\binom{k}{2}$개의 $|A[i_l]-A[i_m]|$들을 얻는다.

두 종류를 합쳐 총 30개 이하로 쿼리를 날려야 한다. 

Discussion

우선, 당연히 $N$번의 쿼리로 길이 $N$의 배열을 알아낼 수 있다. 그런데 우리는 $N$번보다 줄여야 하므로 간단한 예제에서 쿼리의 수를 줄이는 생각 해보자. 길이 2인 배열을 1번의 쿼리만으로 알아낼 수 있을까? 당연히 불가능하다. 길이 3의 배열을 2번의 쿼리만으로 알아낼 수 있을까? 역시 불가능하다. 길이 4인 배열은 3번의 쿼리만으로 알아낼 수 있을까? 조금 생각해보면 불가능하다는 것을 알 수 있다. 그렇다면 접근방법을 조금 바꿔서 길이 5인 배열에서 3개의 값을 알고 있다고 했을 때 나머지 2개의 값을 1번의 쿼리로 알아낼 수 있을까? 이것 역시 불가능하다. 5나 3 같은 숫자를 바꿔봐도 횟수를 줄일 수 있는 방법은 잘 떠오르지 않는다. 이로써 inductive한 방법은 어렵다는 것을 알 수 있다. 여기까지가 내가 팀 연습에서 생각한 결과이고, 이 이상 나아가지 못했다. 

Solution

우리는 문제를 다시 살펴볼 필요가 있다. 배열의 수가 서로 다르다는 것을 이용해야 한다. 수들이 서로 다르다는 것은 최댓값과 최솟값이 유일하다는 것을 뜻한다. 그러므로 우선 이들을 찾아보자.

 

Step 1. 최댓값 or 최솟값 위치 찾기

1번 쿼리를 이용할 경우 $N$번이 걸리지만 2번 쿼리를 이용하면 보다 빠르게 할 수 있다. 먼저, 모든 인덱스를 골라 2번 쿼리를 날려보자. 배열의 수가 모두 다르므로 쿼리의 응답으로 오는 수들의 최댓값 역시 유일하고 그 값은 |최댓값 - 최솟값| 일 것이다. 이번에는 배열을 반으로 잘라 앞의 부분에 해당하는 인덱스들을 골라 2번 쿼리를 날려보자. 여기서도 응답으로 오는 수들의 최댓값이 유일할 것인데, 이 값이 아까의 최댓값과 같다면 배열의 절반 앞에 최댓값과 최솟값이 모두 포함되어 있다는 것을 의미한다. 만약 다르다면, 둘 중 하나는 뒤 절반에 있는 것이다. 이로써 우리는 Binary Search를 하여 최댓값과 최솟값 중 더 뒤에 있는 것의 위치를 알아낼 수 있다. 

쿼리 횟수: $\lceil \log_2 N \rceil+1$

 

이렇게 최댓값 또는 최솟값의 위치($p$)를 알아냈다면 우리는 새로운 배열 $B$를 다음과 같이 정의할 수 있다.

$$B[i] = |A[i] - A[p]|$$

이때 $B[i]$들은 모두 다르다는 것을 알 수 있다. 이제 배열 $B$를 구해보자.

 

Step 2. 배열 $B$ 구하기

$p\notin I$인 인덱스 집합 $I$에 대해 $\{B[i] : i \in I\}$를 구해보자. 임의의 인덱스 집합 $J$를 2번 쿼리로 날렸을 때 얻는 수들의 집합을 $Q_2(J)$라고 정의했을 때, $Q_2(I\cup\{p\}) \setminus Q_2(I)=\{B[i] : i \in I\}$임을 알 수 있다. 그런데 우리는 이 중에서 어떤 게 어느 위치에 있는지까지 알아내야 한다. 쉬운 설명을 위해 $I=\{1, 2, 3, 4\}$이라고 하고 Binary Tree를 그려보자. 

위에서 설명한 방법으로 우리는 $\{B[1], B[2], B[3], B[4]\}$를 알아낸 상태이다. 이때 $Q_2(I_1\cup\{p\}) \setminus Q_2(I_1)$을 통해 $\{B[1], B[2]\}$을 알아낸다면 우리는 두 집합을 빼 $\{B[3], B[4]\}$역시 알아낼 수 있다. 그 다음 과정이 매우 중요한데, $I_3$만 가지고 같은 과정을 반복하는 것이 아니라 $I_3\cup I_5$를 가지고 같은 과정을 반복해보자. 그렇다면 2번의 쿼리를 통해 $\{B[1], B[3]\}$을 알아낼 수 있을 것이다.

이때 $\{B[1], B[2]\} \setminus \{B[1], B[3]\} = \{B[2]\}$, $\{B[1], B[2]\} \setminus \{B[2]\} = \{B[1]\}$이므로 $B[1], B[2]$를 각각 알아낼 수 있다. 마찬가지로 $B[3], B[4]$ 또한 각각 알아낼 수 있다. 이 과정에서 우리는 Binary Tree의 한 depth마다 2번의 쿼리를 사용했고, Binary Tree의 depth는 $\lceil \log_2 N \rceil + 1$ 이므로 총 사용한 쿼리의 수는 아래와 같다.

쿼리 횟수: $2\lceil \log_2 N \rceil+2$

 

이렇게 $B$를 모두 구했다면 거의 다 왔다. Step 1에서 구한 $A[p]$가 최댓값인지, 최솟값인지 알아내면 $B$를 통해 $A$를 모두 구할 수 있기 때문이다. 

 

Step 3. 배열 $A$ 구하기

Step 2에서 구한 $B[i]$들 중 최댓값이 $B[q]$라 하자. (이는 유일하며, 왜인지 모르겠다면 위를 다시 보자.)

그렇다면 정의에 의해 $A[p], A[q]$중 하나는 최댓값이고, 하나는 최솟값일 것이다. 이때, 1번 쿼리를 사용하여 두 값을 직접 구하여 비교한다면 $A[p]$가 최댓값인지, 최솟값인지 알 수 있다. 만약 최댓값이라면 $A[i] = A[p] - B[i]$, 최솟값이라면 $A[i] = A[p] + B[i]$가 성립하여 배열 $A$를 구할 수 있다.

쿼리 횟수: $2$

 

Step 1, 2, 3에서 사용한 쿼리의 수는 총 $5+3\lceil \log_2 N \rceil$이다. 놀랍게도 $N$의 최댓값인 250을 대입해보면 29번이 나온다! 달리 말하면, 위 과정에서 조금이라도 어긋날 시 WA를 받을 수 있다. 구현 화이팅!

 

#include <bits/stdc++.h>

#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define allv(V) (V).begin(), (V).end()

using namespace std;

typedef pair<int, int> pii;

int n, pos, B[252];

int query1(int x)
{
    printf("1 %d\n", x);
    fflush(stdout);
    int ret = 0;
    scanf("%d", &ret);
    return ret;
}

vector<int> query2(vector<int> &v)
{
    printf("2 %d ", v.size());
    for(int i : v) printf("%d ", i);
    puts("");
    fflush(stdout);
    vector<int> ret;
    for(int i = 0; i < v.size() * (v.size() - 1) / 2; i++)
    {
        int x;
        scanf("%d", &x);
        ret.pb(x);
    }
    return ret;
}

vector<int> sub(vector<int> &v1, vector<int> &v2)
{
    sort(allv(v1));
    sort(allv(v2));
    vector<int> ret;
    int p = 0;
    for(int i : v1)
    {
        while(p < v2.size() && v2[p] < i) p++;
        if(p >= v2.size() || i != v2[p]) ret.pb(i);
        else p++;
    }
    return ret;
}

vector<int> getB(vector<int> &v)
{
    if(v.size() == 1)
    {
        vector<int> ret;
        ret.pb(abs(query1(pos) - query1(v[0])));
        return ret;
    }

    bool f = false;
    for(int &i : v)
    {
        if(i == pos)
        {
            f = true;
            swap(i, v.back());
            v.pop_back();
            break;
        }
    }

    if(v.size() == 1)
    {
        vector<int> ret;
        ret.pb(abs(query1(pos) - query1(v[0])));
        ret.pb(0);
        return ret;
    }
    
    vector<int> t1 = query2(v);
    v.pb(pos);
    vector<int> t2 = query2(v);
    if(f) t2.pb(0);
    return sub(t2, t1);
}

vector<int> v, aretv, T[1010];

vector<pii> idx;

int main()
{
    scanf("%d", &n);

    if(n <= 30)
    {
        int ans[33];
        for(int i = 1; i <= n; i++) ans[i] = query1(i);
        printf("3 ");
        for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
        return 0;
    }

    for(int i = 1; i <= n; i++) v.pb(i);
    aretv = query2(v);
    int M = 0;
    for(int i : aretv)
    {
        if(M < i) M = i;
    }
    int l = 2, r = n;
    while(l < r)
    {
        int mid = l + r >> 1;
        v.clear();
        for(int i = 1; i <= mid; i++) v.pb(i);
        vector<int> tmpv = query2(v);
        int tM = 0;
        for(int i : tmpv)
        {
            if(tM < i) tM = i;
        }
        if(tM == M) r = mid;
        else l = mid + 1;
    }
    pos = l;

    v.clear();
    for(int i = 1; i <= n; i++) if(i != pos) v.pb(i);
    vector<int> tmpv = query2(v);
    T[1] = sub(aretv, tmpv);
    T[1].pb(0);
    idx.eb(1, n + 1 >> 1);
    idx.eb((n + 1 >> 1) + 1, n);
    for(int dp = 1; ; dp++)
    {
        v.clear();
        for(int i = 0; i < idx.size(); i += 2)
        {
            for(int j = idx[i].fi; j <= idx[i].se; j++) v.pb(j);
        }
        if(!v.size()) break;
        vector<int> tmpv = getB(v);
        for(int i = (1 << dp); i < (1 << dp + 1); i += 2)
        {
            T[i + 1] = sub(T[i / 2], tmpv);
            T[i] = sub(T[i / 2], T[i + 1]);
            pii tmp1 = idx[i - (1 << dp)];
            pii tmp2 = idx[i - (1 << dp) + 1];
            if(tmp1.fi == tmp1.se) B[tmp1.fi] = T[i][0];
            if(tmp2.fi == tmp2.se) B[tmp2.fi] = T[i + 1][0];
        }
        vector<pii> idx2;
        for(pii &i : idx)
        {
            if(i.fi >= i.se)
            {
                idx2.eb(0, -1);
                idx2.eb(0, -1);
                continue;
            }
            idx2.eb(i.fi, i.fi + i.se >> 1);
            idx2.eb((i.fi + i.se >> 1) + 1, i.se);
        }
        idx = idx2;
    }
    int midx = 1;
    for(int i = 2; i <= n; i++) if(B[midx] < B[i]) midx = i;
    int vm = query1(midx);
    int vM = query1(pos);
    printf("3 ");
    if(vm < vM)
    {
        for(int i = 1; i <= n; i++) printf("%d ", vM - B[i]);
        puts("");
    }
    else
    {
        for(int i = 1; i <= n; i++) printf("%d ", vM + B[i]);
        puts("");
    }
    return 0;
}

References

http://acm.ro/2019/index.html > Problems > Problems Editorial