April Circuits’17 contest link

Fredo and Game

An easy problem. However, there is a trick that If Fredo reaches the last obstacle, he is said to reach the end of path.

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
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
#define mp make_pair
#define fi first
#define se second
#define pb push_back

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = (ll)(1e9 + 7);
const int MAX_N = 100010;

int T, n, st;
int data[MAX_N];

void solve() {
for (int i = 1; i <= n; ++i) {
if (data[i] == 0) st -= 1;
else st += 2;
if (st == 0 && i != n) {
printf("No %d\n", i);
return;
}
}
printf("Yes %d\n", st);
}

int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &st, &n);
for (int i = 1; i <= n; ++i) scanf("%d", &data[i]);
solve();
}
return 0;
}

Help Fredo

Give you an array $A$ containing $N\leq 10^5$ postive integers. You need to find the minimum positive integer $x$ subjecting to $x^{n} > \prod_{i=1}^{n} A[i]$.

We can replace multiply operation with logarithm operation to avoid big integers, even though there is a little precision loss. Additionaly, the answer is monotonous, so we can use binary search.

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
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
#define mp make_pair
#define fi first
#define se second
#define pb push_back

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = (ll)(1e9 + 7);
const int MAX_N = 100010;

int n;
long double sum;
double data[MAX_N];

bool check(ll x) {
return log(x) * n > sum;
}

int main() {
scanf("%d", &n);
sum = 0;
for (int i = 1; i <= n; ++i) {
scanf("%lf", &data[i]);
sum += log(data[i]);
}
ll low = 2, high = (ll)(1e10 + 5), mid, ans;
while (low <= high) {
mid = (low + high) >> 1;
if (check(mid)) ans = mid, high = mid - 1;
else low = mid + 1;
}
printf("%lld\n", ans);
return 0;
}

Worse MST (unsolved)

too difficult :(

Fredo and Maths

Given three numbers $x, k$ and $m$, you need ot find the value of $x^{x^{x^{.^{.^{.^{x}}}}}} % m$ where number of x’s in the expression are k.

$T\leq 10^5, m\leq 10^7, k\leq 10^{18}, m< x \leq 10^8, x$is always a prime number.

My idea is based on the formula of exponential reduction. That is to say, $x^p % m$ is equal to $x ^{p \% \phi(m) + \phi(m)} % m$ while $p \geq \phi(m)$, where $\phi(m)$ is Euler’s totient function of $m$. Further more, iterative search is an efficient method.

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
#define mp make_pair
#define fi first
#define se second
#define pb push_back

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = (ll)(1e9 + 7);
const int MAX_N = 1000010;

int prime_cnt = 0;
int prime[MAX_N], vis[MAX_N], phi[MAX_N];

void init() {
phi[1] = 1;
for (int i = 2; i < MAX_N; ++i) {
if (!vis[i]) prime[prime_cnt++] = i, phi[i] = i - 1;
for (int j = 0; j < prime_cnt && i * prime[j] < MAX_N; ++j) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
phi[i * prime[j]] = prime[j] * phi[i];
break;
}
phi[i * prime[j]] = (prime[j] - 1) * phi[i];
}
}
}

inline int getPhi(int x) {
if (x < MAX_N) return phi[x];
else {
int ret = 1;
for (int i = 0; prime[i] * prime[i] <= x; ++i) {
if (x % prime[i] == 0) {
ret *= (prime[i] - 1);
x /= prime[i];
while (x % prime[i] == 0) {
x /= prime[i];
ret *= prime[i];
}
}
}
if (x > 1) ret *= (x - 1);
return ret;
}
}

inline int Qpow(int a, int b, int c) {
int ret = 1;
while (b) {
if (b & 1) ret = 1ll * ret * a % c;
a = 1ll * a * a % c;
b >>= 1;
}
return ret;
}

int dfs(int x, ll depth, int mmod) {
int t = getPhi(mmod);
if (depth == 1 || t == 1) return x % mmod;
return Qpow(x, dfs(x, depth - 1, t), mmod);
}

int main() {
init();

int T, x, m;
ll K;
scanf("%d", &T);
while (T--) {
scanf("%d%lld%d", &x, &K, &m);
if (x == 2) {
assert(m == 1);
puts("0");
} else printf("%d\n", dfs(x, K, m));
}
return 0;
}

Filler Game

This is a basic problem. We just need to preprocess and state compression dp. For each query, We onnly need $O(1)$ to give answer.

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
65
66
67
68
#include <bits/stdc++.h>
#include <stdlib.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
#define mp make_pair
#define fi first
#define se second
#define pb push_back

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = (ll)(1e9 + 7);
const int MAX_N = 100010;
const int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

int n, m;
int state[1 << 22];

void init() {
int top = n * m;
memset(state, -1, sizeof (state));
for (int s = 0; s < (1 << top); ++s) {
state[s] = 0;
for (int i = 0; i < top; ++i) {
if (!(s & (1 << i))) continue;
int row = i / m, col = i % m;

int find = 0;
for (int j = 0; j < 4; ++j) {
int nrow = row + dir[j][0], ncol = col + dir[j][1];

if (nrow < 0 || ncol < 0 || nrow >= n || ncol >= m) continue;
int p = nrow * m + ncol;
find |= (s & (1 << p));
}

if (find && state[s ^ (1 << i)] == 0) {
state[s] = 1;
break;
}
}
// printf("state[%d] = %d\n", s, state[s]);
}
}

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

for (int i = 0; i < Q; ++i) {
char str[25];
int pos = 0, s = 0;
for (int j = 0; j < n; ++j) {
scanf("%s", str);

for (int k = 0; k < m; ++k) {
if (str[k] == '0') s += (1 << pos);
pos++;
}
}

printf("%d\n", state[s] ^ 1);
}
return 0;
}

Number Summation

We define $F(x, y)$ as the sum of numbers that divide both $x$ and $y$, i.e., sum of the common divisors of $x$ and $y$. Given the value of $n\leq 10^{15}$, calculate the value of:
$$
\sum_{i=1}^{n}\sum_{j=i}^{n}F(i, j) \% (10^{9}+ 7)
$$

Actually, this is a pretty good problem, I think.

I would just talk about how to solve:
$$
\sum_{i=1}^{n}\sum_{j=1}^{n}F(i, j) \% (10^{9}+ 7)
$$
which is a little bit different from the
original question. But the core algorithm is same and you just need to subtract the repetitive options.

You can calculate the contribution of every common divisor i(from 1 to n) for answer. Concretely, for i = 1, the contribution is (n / 1) * (n / 1) * 1; for i = 2, the contribution is: (n/2) * (n/2) * 2…… and so on. You will find, the contribution of common divisior i is : (n/i) * (n/i) * i. However, the value of n is 10^{15}, which is so large. We need to accelerate this process.

You can find that during the process above, for some i = i1 and i = i2, (n/i1) = (n/i2). For example, 23/4 =23/5, 100/21 = 100/25. The interesting thing comes that: n / i = n/(n/i), so we don’t need to enumerate each i (for i = 1 to n).

The total time complexity can be reduced to $O(\sqrt n)$, and this is enough for this problem.

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
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
#define mp make_pair
#define fi first
#define se second
#define pb push_back

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = (ll)(1e9 + 7);
const int MAX_N = 100010;

inline ll Qpow(ll a, ll b) {
a = (a % mod + mod) % mod;
ll ret = 1;
while (b) {
if (b & 1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}

int main() {
ll n, sum = 0, same = 0;
cin >> n;
for (ll i = 1; i <= n;) {
ll p = n / i;
ll q = n / p;

ll a = i + q, b = q - i + 1;
if (a & 1) b /= 2;
else a /= 2;

a %= mod, b %= mod;
ll t = a * b % mod;

sum = (sum + (p % mod) * (t % mod) % mod * (p % mod) % mod) % mod;
same = (same + (p % mod) * (t % mod) % mod) % mod;
i = q + 1;

assert(sum >= 0 && same >= 0);
}

ll ret = ((sum - same) + mod) % mod * Qpow(2, mod - 2) % mod + same;
cout << ret % mod << endl;
return 0;
}

Dexter’s Random Generator

Ths is a problem about tree and xor.

Firstly, I discussed with erikwei that dfs order and segment tree with trie may solve this problem regardless of space complexity.(2333) Laterly, erikwei telled me replacing segment tree with Mo’ Algorithm may work. Nice!

To be honest, the code is not very easy to complete perfectly.

And the time complexity is $O(n\sqrt {n} \log n)$ with a lttle large constant. So it got TLE on two test cases. We only got 93/100 scores. :(

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
#define mp make_pair
#define fi first
#define se second
#define pb push_back

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = (ll)(1e9 + 7);
const int MAX_N = 100010;
const int NUM = 2;

struct Trie {
    int child[MAX_N * 20][NUM], cnt[MAX_N * 20];
    int root, tot;

    void init() {
        root = tot = 1;
        child[1][0] = child[1][1] = 0;
        cnt[1] = 1;
    }
    void insert(const int x) {
        int* cur = &root;
        for (int i = 29; i >= 0; --i) {
            cur = &child[*cur][(x >> i) & 1];
            if (*cur == 0) {
                *cur = ++tot;
                child[tot][0] = child[tot][1] = 0;
                cnt[tot] = 0;
            }
            cnt[*cur]++;
        }
    }

    void remove(const int x) {
        int *cur = &root;
        for (int i = 29; i >= 0; --i) {
            cur = &child[*cur][(x >> i) & 1];
            cnt[*cur]--;
        }
    }

    int query(int x) {
        int ret = 0;
        int* cur = &root;
        for (int i = 29; i >= 0; --i) {
            int now = (x >> i) & 1, store = *cur;
            if (now == 0) {
                cur = &child[*cur][1];
                if (cnt[*cur] > 0) ret += (1 << i);
                else cur = &child[store][0];
            } else {
                cur = &child[*cur][0];
                if (cnt[*cur] > 0) ret += (1 << i);
                else cur = &child[store][1];
            }
        }
        return ret;
    }
} trie;

const int B = 300;

int n, Q;
int A[MAX_N], Left[MAX_N], Right[MAX_N], be[MAX_N * 2];
int fa[MAX_N][20], depth[MAX_N], ans[MAX_N], vis[MAX_N], pos[MAX_N * 2];
vector<int> edge[MAX_N];

struct Query {
    int a, b, anc, L, R, id;

    bool operator < (const Query& rhs) const {
        return pos[L] == pos[rhs.L] ? R < rhs.R : pos[L] < pos[rhs.L];
    }
} ques[MAX_N];

void dfs(int u, int p, int& k, int d) {
    Left[u] = ++k, depth[u] = d;
    be[k] = u;
    for (int i = 1; i < 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = 0; i < edge[u].size(); ++i) {
        int v = edge[u][i];
        if (v == p) continue;
        fa[v][0] = u;
        dfs(v, u, k, d + 1);
    }
    Right[u] = ++k;
    be[k] = u;
}

inline int LCA(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int i = 0; i < 20; ++i) {
        if (((depth[v] - depth[u]) >> i) & 1) v = fa[v][i];
    }
    if (u == v) return v;
    for (int i = 19; i >= 0; --i) {
        if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; 
    }
    return fa[u][0];
}

inline void update(int id) {
    if (id < 1 || id > n) return;
    if (vis[id]) trie.remove(A[id]);
    else trie.insert(A[id]);
    vis[id] ^= 1; 
}

struct FastIO {
    static const int S = 1000000;
    int wpos, pos, len;
    char wbuf[S];
    FastIO(): wpos(0) {}
    inline int xchar() {
        static char buf[S];
        if (pos == len) pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) return -1;
        return buf[pos++];
    }
    inline int xint() {
        int c = xchar(), x = 0;
        while (c <= 32 && ~c) c = xchar();
        if (c == -1) return -1;
        for (; c >= '0' && c <= '9'; c = xchar()) x = x * 10 + (c - '0');
        return x;
    }
} io;

int main() {    
//    scanf("%d%d", &n, &Q);
    n = io.xint(); Q = io.xint();
    for (int i = 1; i <= n; ++i) {
        A[i] = io.xint();
        //scanf("%d", &A[i]);
        edge[i].clear();
    }
    for (int i = 1;  i < n; ++i) {
        int u, v;
//        scanf("%d%d", &u, &v);
        u = io.xint(); v = io.xint();
        edge[u].pb(v);
        edge[v].pb(u);
    }

    for (int i = 1; i <= 2 * n; ++i) pos[i] = i / B;

    int K = 0;
    fa[1][0] = 1;
    dfs(1, -1, K, 1);

    for (int i = 1; i <= Q; ++i) {
//        scanf("%d%d", &ques[i].a, &ques[i].b);
        ques[i].a = io.xint(); ques[i].b = io.xint();
        ques[i].id = i;

        int u = ques[i].a, v = ques[i].b, p;
        ques[i].anc = p = LCA(u, v);      
        if (p == u || p == v) {
            ques[i].L = min(Left[u], Left[v]);
            ques[i].R = max(Left[u], Left[v]);
        } else {
            ques[i].L = min(Right[u], Right[v]);
            ques[i].R = max(Left[u], Left[v]);
        }
    }
    sort(ques + 1, ques + 1 + Q);

    memset(vis, 0, sizeof (vis));
    trie.init();
    int ret = 0, L = 1, R = 0;

    for (int i = 1; i <= Q; ++i) {
        while (R > ques[i].R) {
            update(be[R]);
            --R;
        }
        while (R < ques[i].R) {
            ++R;
            update(be[R]);
        }

        while (L < ques[i].L) {
            update(be[L]);
            ++L;
        }
        while (L > ques[i].L) {
            --L;
            update(be[L]);
        }

        if (ques[i].a == ques[i].b) ans[ques[i].id] = 0;
        else if (be[L] == ques[i].anc || be[R] == ques[i].anc) {
            ans[ques[i].id] = max(trie.query(A[be[L]]), trie.query(A[be[R]]));
        } else {
            trie.insert(A[ques[i].anc]);
            ans[ques[i].id] = max(trie.query(A[be[L]]), trie.query(A[be[R]]));
            trie.remove(A[ques[i].anc]);
        }
    }

    for (int i = 1; i <= Q; ++i) printf("%d\n", ans[i]);

    return 0;
}

XOR queries(unsolved)

too difficult…
What I can do only is to make a brute force solution.