Codeforces 1840G In Search of Truth

Posted on 繁/简： set

题目来自 Codeforces Round #878 (Div.3) G。link (easy), link (hard)


  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!


Problem Description

一个转盘分为 \(n\) 块 (\(1\leq n\leq 10^6\)) ，上面的数字是 \(1-n\) 的一个排列。你并不知道 \(n\) 的值。

初始时，指针指向数字 \(x\)。你可以向评测机询问从当前状态顺时针 (\(+\)) 或逆时针 (\(-\)) 旋转 \(k\) 块后，指针指向的数字是多少。你可以询问至多 \(2023\) (easy version) 或 \(1000\) (hard version) 次。

你需要确定 \(n\) 的值。


Tutorial

最朴素的解法：初始 \(a_1=x\)，以步长为 \(1\) 询问，直到找到某个 \(a_t=a_1=x\)。此时易知 \(t=n\)。然而这个方法需要 \(O(n)\) 次询问，远远超过限制的询问次数。

观察到询问次数 \(\approx \sqrt{n}\)，考虑应用根号分块思想。(块的大小 \(\sqrt{n}=1000\))

Easy Version (G1)

初始 \(a_1=x\)，以步长为 \(1\) 询问 \(999\) 次得到第一个块 \(b_1=\{a_1,a_2,...,a_{1000}\}\)。接下来，由 \(a_{1000}\) 开始，以步长为 \(1000\) 继续询问，直到发现某个数 \(a_t\in b_1\) (在第一个块中出现过)，至此找到了一个长度为 \(n\) 的循环。

可以证明，当 \(1000\leq n\leq 10^6\) 时，直到找到重复元素所作的询问次数不会超过 \(1000\) 次。所以找到 \(n\) 所需的总询问次数为 \(999+1000=1999\leq 2023\)。

以步长为 \((+)1000\) 进行询问实际上是遍历所有块的块尾元素。这里分块思想的单调性体现在，若块尾元素并未在 \(b_1\) 中出现过，则该块尾元素所在块的所有元素均不会在 \(b_1\) 中出现。

Hard Version (G2)

Hard version 的处理就有点 tricky 了；需要应用随机化改进 G1 中的算法。

初始 \(a_1=x\)，以随机步长询问 \(k\) 次，得到一系列 \(n_1,n_2,...,n_k\in[1,n]\)。令 $m=(n_1,n_2,...,n_k) $， 其与 \(n\) 之间的距离 \(d=n-m\)。

假设当前的位置为 \(p\) (即上一次询问 \(n_k\) 所对应的位置)，先以步长为 \(1\) 询问 \(t\) 次 ( \(t\) 为块的大小 sz)，返回 \(p\) 后再将转盘顺时针旋转 \(m\) \((+m)\)。这里的巧妙之处在于，顺时针旋转 \(m\) 相当于逆时针旋转 \(d\) \((-d=-n+m)\)。此时我们再应用 G1 中的方法求得长度 \(d\)。最后计算 \(n=m+d\)。

重点在于，如何平衡 \(k\) 与 \(t\) 的值，使得总询问次数不能超过 \(1000\)，同时得到 \(n\) 的概率足够大。需要满足：

  • \(k+2t\leq 1000\) (对于块长 \(t\)，执行 G1 中的算法需要 \(2t\) 次询问)
  • \(t^2\geq d\) (根据 G1 中的算法，对于某个待求长度 \(d\)，需要块长 \(t\geq \sqrt{d}\))

因此，对于某个 \(k\)，存在最优 \(d=(\frac{1000-k}{2})^2\)。也就是说，在随机取得的 \(n_1,n_2,...,n_k\) 中最大的 \(m\)，应该有相当大的概率落在 \([n-d,n]\) 即 \([n-(\frac{1000-k}{2})^2,n]\) 中。易知概率为 \(\Pr[\mathtt{valid}]=1-(\frac{n-d}{n})^k\)。

取 \(n=10^6\)，\(k\in[200,400]\) (以 \(k=200\) 为例)，\(\Pr[\mathtt{valid}]=1-7.2\times 10^{-16}\)，是一个相当大的概率了。


Code Implementation

Easy Version (G1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>

using namespace std;

const int MAX_N = 1e6 + 10;
const int sz = 1000;

int pos[MAX_N];

int main() {

    int x;
    cin >> x;

    pos[x] = 1;
    for (int i = 2; i <= sz; ++i) {
        cout << "+ 1" << endl;
        cout.flush();
        int x;
        cin >> x;
        if (pos[x]) {               // cases when n < 1000
            cout << "! " << i - pos[x] << endl;
            cout.flush();
            return 0;    
        }
        pos[x] = i;
    }

    int index = 1000;
    for (int i = 1; i <= sz; ++i) {
        cout << "+ 1000" << endl;
        index += 1000;
        cout.flush();
        int x;
        cin >> x;
        if (pos[x]) {
            cout << "! " << index - pos[x] << endl;
            cout.flush();
            break;
        }
    }

    return 0;
}

Hard Version (G2)

事实证明，随机性确实影响有点大；这与理论计算相悖，因为根据理论，取 \(k\in[200,400]\)，成功的概率都十分逼近 \(1\)。可能是伪随机在作祟，也有可能是其他奇奇怪怪的原因。

经简单测试，取 \(k=400\)，块长 (sz) \(t=\frac{1000-k}{2}=300\) 正确率最高。

3组,每组提交2次,由上至下分别是 k=400,k=300,k=200 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <random>
#include <chrono>
 
using namespace std;
 
const int MAX_N = 1e6 + 7;
const int sz = 400;
const int k = 300;
 
int pos[MAX_N];
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
inline int rnd() { return rng() % MAX_N; }
 
int main() {
 
    int x;
    cin >> x;
    
    int m = 0;
    for (int i = 1; i <= k; ++i) {
        cout << "+ " << rnd() << endl;
        cout.flush();
        cin >> x;
        m = max(x, m);
    }
 
    pos[x] = 1;     // position p
    for (int i = 2; i <= sz; ++i) {
        cout << "+ 1" << endl;
        cout.flush();
        cin >> x;
        if (pos[x]) {   // cases when n is small
            cout << "! " << i - 1 << endl;
            cout.flush();
            return 0;
        }
        pos[x] = i;
    }
    cout << "- " << sz - 1 << endl;
    cout.flush();
    cin >> x;
    cout << "+ " << m << endl;  // +m <=> -d
    cout.flush();
    cin >> x;
 
    int d = 0;
    for (int i = 1; i <= sz; ++i) {
        d += sz;
        cout << "+ " << sz << endl;
        cout.flush();
        cin >> x;
        if (pos[x]) {
            d -= (pos[x] - 1);
            cout << "! " << m + d << endl;
            cout.flush();
            break;
        }
    }
 
    return 0;
}


-----------------------------------そして、次の曲が始まるのです。-----------------------------------