# # Codeforces Round 669 (CF1407) Tutorial

## # Problem A - Ahahahahahahahaha (opens new window)

Since we can delete at most $N/2$ numbers, we can always choose to delete the one that occurs less. If $0$ and $1$ occur the same times, we choose to keep $0$ and delete $1$.

Note that if we choose to keep $1$, we need to check the parity and make a correction if needed.

Time complexity is $O(N)$.

Code (C++)
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
vector<int> a(n);
int z = 0;
for (int i = 0; i < n; ++i)
read(a[i]), z += (a[i] == 0);
int k = z, d = 0;
if (z < n - z) {
d = 1;
k = n - z;
if (k % 2 == 1)
k--;
}
printf("%d\n", k);
vector<int> ans(k, d);
for (int i : ans)
printf("%d ", i);
printf("\n");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}

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

## # Problem B - Big Vova (opens new window)

We can greedily take the element which makes the $GCD$ of it and current $GCD_t$ largest. If there are many, we can choose any of them, because the rest will be taken in the following rounds.

Time complexity is $O(N^2\log A)$, in which $A$ is the largest number in the array.

Code (C++)
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }

class Solution {
public:
void solve() {
int n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
vector<bool> vis(n);
vector<int> ans(n);
int g = 0;
for (int i = 0; i < n; ++i) {
int hi = -1, hidx = -1;
for (int j = 0; j < n; ++j) {
if (vis[j])
continue;
int gj = gcd(g, a[j]);
if (gj > hi) {
hi = gj;
hidx = j;
}
}
ans[i] = a[hidx];
vis[hidx] = true;
g = hi;
}
for (int i : ans)
printf("%d ", i);
printf("\n");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}

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

## # Problem C - Chocolate Bunny (opens new window)

Consider any $a, we have $b\mod a. That is to say, if we query $(i,j)$ and then $j_i$, we can determine the smaller one of $p_i$ and $p_j$, since $p$ is a permutation and there are no equal elements.

So we start from $p_1$ and $p_2$. Each time, we make two queries, determine the smaller one and keep the index of the larger one and continue queries. After $2(n-1)$ queries, we can determine all $p_i，and the current kept index $p_k=n$.

Time complexity is $O(N)$.

Code (C++)
#include <iostream>
#include <vector>

using namespace std;

class Solution {
vector<int> ans;

int query(int i, int j) {
int k;
cout << "? " << i << " " << j << endl;
cin >> k;
return k;
}

public:
void solve() {
int n;
cin >> n;
if (n == 1) {
cout << "! 1" << endl;
return;
}
ans = vector<int>(n + 1);
int a = query(1, 2), b = query(2, 1);
int m;
if (a > b) {
m = 2;
ans[1] = a;
} else {
m = 1;
ans[2] = b;
}
for (int i = 3; i <= n; ++i) {
int a = query(m, i), b = query(i, m);
if (a > b) {
ans[m] = a;
m = i;
} else {
ans[i] = b;
}
}
ans[m] = n;
cout << "! ";
for (int i = 1; i <= n; ++i)
cout << ans[i] << " ";
cout << endl;
}
};

int main() {
Solution solution = Solution();
solution.solve();
}
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

## # Problem D - Discrete Centrifugal Jumps (opens new window)

Valid moves can only be in one of the following situations:

• $h_j$ is the first non smaller than $h_i$ to its right
• $h_j$ is the first non greater than $h_i$ to its right
• $h_i$ is the first non smaller than $h_j$ to its left
• $h_i$ is the first non greater than $h_j$ to its left

Note that $i+1=j$ must have been included in the situations.

We can use monotonic stack to gather the information. After that, we just do a BFS.

Time complexity is $O(N)$.

Code (C++)
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {

public:
void solve() {
int n;
vector<int> h(n);
for (int i = 0; i < n; ++i)
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && h[i] <= h[st.top()]) {
st.pop();
}
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = 0; i < n; ++i) {
while (!st.empty() && h[i] >= h[st.top()]) {
st.pop();
}
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && h[i] <= h[st.top()]) {
st.pop();
}
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && h[i] >= h[st.top()]) {
st.pop();
}
st.push(i);
}
queue<int> q;
q.push(0);
vector<int> dist(n, -1);
dist[0] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == n - 1) {
printf("%d", dist[u]);
return;
}
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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
84
85
86
87
88
89
90
91
92
93
94

## # Problem E - Egor in the Republic of Dagestan (opens new window)

Think reversely and color greedily.

All edges $(u,v,t)$ are stored at $v$ side. We start BFS from $N$. Considering node $v$ and edge $(u,v,t)$. If $u$ has been colored to $t$, then this edge cannot be cut and we need to enqueue $u$. Otherwise we set $u$ to the opposite color of $t$ to cut this edge. This coloring strategy is optimal because a node visited earlier corresponds to a shorter distance to $N$.

If after the BFS we have not visited $1$, then it is possible to make $1$ and $N$ not connected. Otherwise $dist[1]$ is just the maximal shortest path distance we are required to find. The coloring has been determined during BFS. For those uncolored nodes, either color is OK.

Time complexity is $O(N+M)$.

Code (C++)
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {

public:
void solve() {
int n, m;
vector<vector<pair<int, int>>> in(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, t;
if (u == v)
continue;
t++;
in[v].emplace_back(u, t);
}

queue<pair<int, int>> q;
q.emplace(n, 0);
vector<int> close(n + 1);
vector<int> dist(n + 1);
vector<bool> vis(n + 1);
vis[n] = true;
while (!q.empty()) {
auto [v, d] = q.front();
dist[v] = d;
q.pop();
for (auto [u, t] : in[v]) {
if (vis[u])
continue;
if ((t == 1 && close[u] == 2) || (t == 2 && close[u] == 1)) {
vis[u] = true;
q.emplace(u, d + 1);
} else
close[u] = t;
}
}
if (!vis[1])
printf("-1\n");
else
printf("%d\n", dist[1]);
for (int i = 1; i <= n; ++i)
printf("%d", min(1, 2 - close[i]));
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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