It took me nearly seven hours to solve the 6/7 problems. Some useful ideas can be found among them.

Reward Points

An easy problem.

Zigzag Array

An east problem. I accepted it by a method similar with two pointer.

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
#include <bits/stdc++.h>
using namespace std;

int minimumDeletions(vector < int > a){
// Complete this function
if (a.size() <= 2) return 0;
int ans = 0;
int flag = a[1] > a[0], st = 0, ed = 1;
for (int i = 2; i < a.size(); ++i) {
if (flag) {
if (a[i] > a[i - 1]) ed = i;
else {
flag = 0;
ans += max(0, ed - st + 1 - 2);
st = i - 1, ed = i;
}
} else {
if (a[i] < a[i - 1]) ed = i;
else {
flag = 1;
ans += max(0, ed - st + 1 - 2);
st = i - 1, ed = i;
}
}
}
ans += max(0, ed - st + 1 - 2);
return ans;
}

int main() {
int n;
cin >> n;
vector<int> a(n);
for(int a_i = 0; a_i < n; a_i++)cin >> a[a_i];
int result = minimumDeletions(a);
cout << result << endl;
return 0;
}

Maximal AND Subsequences

Given an arry with $n\leq 10^5$ long integers $A_{i}\leq 10^{18}$, try to find all the $k$-element subsequences of $A$ where the bitwise AND of the subsequence’s elements is maximal.

This problem is very common actually, and I lost my mind during that time.

We can use a greedy strategy, due to the truth that:
$$
2^{i} > 2^{i-1}+2^{i-2}+\cdots + 2^{0}
$$

We consider the bits in number two system from high to low. For each bit, we calculate the number of elements whose expression at the bit is 1. If the number is larger than or equal to $k$, then we need to delete all other elements whose expression at the bit is 0. That means the maximal AND value must result from those bit-1 elements. The elements left last make up a set from which we can choose $k$ elements.

I choose the data structure multiset to support the delete operation. But vector, list and so on are optional.

The time complexity is $O(n\log^2 n)$.

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>

typedef long long ll;
using namespace std;

const ll mod = (ll)(1e9 + 7);
const int MAX_N = 100010;

ll fac[MAX_N], ifac[MAX_N];

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;
}

ll C(int a, int b) {
if (a < 0 || b < 0 || a < b) return 0;
return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}

vector<ll> data, del;
multiset<ll> S;

void solve(int n, int k){
// Complete this function
S.clear();
for (ll x: data) if (x) S.insert(x);

ll ans = 0;
for (int i = 60; i >= 0; --i) {
int cnt = 0;
for (auto x : S) {
if ((x >> i) & 1) cnt++;
}
if (cnt < k) continue;

ans |= (1ll << i);
del.clear();
for (auto x : S) {
if (((x >> i) & 1) == 0) del.push_back(x);
}
for (ll x : del) S.erase(x);
}

if (ans == 0) cout << 0 << endl << C(n, k) << endl;
else cout << ans << endl << C(S.size(), k) << endl;
}

int main() {
fac[0] = 1;
for (int i = 1; i < MAX_N; ++i) fac[i] = fac[i - 1] * i % mod;
ifac[MAX_N - 1] = Qpow(fac[MAX_N - 1], mod - 2);
for (int i = MAX_N - 2; i >= 0; --i) ifac[i] = ifac[i + 1] * (i + 1) % mod;

int n, k;
cin >> n >> k;
data.resize(n);
for (int i = 0; i < n; ++i) cin >> data[i];
solve(n, k);

return 0;
}

Permutation Happiness

Try to think in dynamic programming, and thx to erikwei.

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
#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 = 3010;

ll ans[MAX_N][MAX_N];

inline void upd(ll& a, ll b) {
a = (a + b) % mod;
}

void init() {
ans[1][1] = 1;
for (int i = 2; i < MAX_N; ++i) {
for (int j = 1; j <= i; ++j) {
if (j * 2 - 1 <= i) upd(ans[i][j], 2 * j * ans[i - 1][j]);
int t = i - 2 * j;
if ((j + 1) * 2 - 1 <= i && t > 0) upd(ans[i][j + 1], t * ans[i - 1][j]);
}
}

for (int i = 1; i < MAX_N; ++i) {
for (int j = 1; j <= i; ++j) {
upd(ans[i][j], ans[i][j - 1]);
}
}
}

int main() {
init();
int Q, n, K;
cin >> Q;
while (Q--) {
cin >> n >> K;
cout << ans[n][n - K] << endl;
}
return 0;
}

Maximum Disjoint Subtree Product

This is a tree-dp problem with two times dfs. Be in a clear mind while coding this problem. I spent nearly two hours finishing it, and got accepted at the second sumbit (the first submit failed because I forgot to add one line code for dfs2() function).

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#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
typedef pair<ll, ll> PI;

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

int n;
ll ans;
vector<int> G[MAX_N];
int val[MAX_N];
PI link[2][MAX_N], nlink[2][MAX_N];

inline void updMax(ll& a, ll b) {
if (b > a) a = b;
}

inline void updMin(ll& a, ll b) {
if (b < a) a = b;
}

void dfs1(int u, int p) {
link[0][u].fi = link[0][u].se = val[u];
nlink[0][u].fi = nlink[0][u].se = 0;

for (int v: G[u]) if (v != p) {
dfs1(v, u);

updMax(nlink[0][u].fi, nlink[0][v].fi);
updMin(nlink[0][u].se, nlink[0][v].se);

if (link[0][v].fi > 0) link[0][u].fi += link[0][v].fi;
if (link[0][v].se < 0) link[0][u].se += link[0][v].se;
}
updMax(nlink[0][u].fi, link[0][u].fi);
updMin(nlink[0][u].se, link[0][u].se);

}

void dfs2(int u, int p) {
pair<PI, PI> Max, Min;
Max.fi = Max.se = mp(nlink[1][u].fi, u);
Min.fi = Min.se = mp(nlink[1][u].se, u);
PI sum = mp(0, 0);

for (int v: G[u]) if (v != p) {
if (link[0][v].fi > 0) sum.fi += link[0][v].fi;
if (link[0][v].se < 0) sum.se += link[0][v].se;

if (nlink[0][v].fi > Max.fi.fi) {
Max.se = Max.fi;
Max.fi = mp(nlink[0][v].fi, v);
} else if (nlink[0][v].fi > Max.se.fi) {
Max.se = mp(nlink[0][v].fi, v);
}

if (nlink[0][v].se < Min.fi.fi) {
Min.se = Min.fi;
Min.fi = mp(nlink[0][v].se, v);
} else if (nlink[0][v].se < Min.se.fi) {
Min.se = mp(nlink[0][v].se, v);
}
}

for (int v: G[u]) if (v != p) {
PI tmp = sum;
if (link[0][v].fi > 0) tmp.fi -= link[0][v].fi;
if (link[0][v].se < 0) tmp.se -= link[0][v].se;

link[1][v].fi = max(0ll, link[1][u].fi + tmp.fi + val[u]);
link[1][v].se = min(0ll, link[1][u].se + tmp.se + val[u]);

nlink[1][v] = link[1][v];

if (Max.fi.se == v) updMax(nlink[1][v].fi, Max.se.fi);
else updMax(nlink[1][v].fi, Max.fi.fi);

if (Min.fi.se == v) updMin(nlink[1][v].se, Min.se.fi);
else updMax(nlink[1][v].se, Min.fi.fi);

updMax(ans, 1ll * nlink[0][v].fi * nlink[1][v].fi);
updMax(ans, 1ll * nlink[0][v].se * nlink[1][v].se);

dfs2(v, u);
}
}

int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> val[i];
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
G[u].pb(v); G[v].pb(u);
}
dfs1(1, 0);

ans = 0;

link[1][0] = nlink[1][0] = mp(0, 0);
// link[1][1] = mp(val[1], val[1]);
// nlink[1][1] = mp(max(0, val[1]), min(0, val[1]));
link[1][1] = nlink[1][1] = mp(0, 0);

dfs2(1, 0);

cout << ans << endl;
return 0;
}

Node-Point Mappings

To be honest this is a old problem as it is the same meaning with CF196 C. I have seen it about one month before. So copy and paste may be a good choice. 23333.

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
#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 = 1510;

int n;
int sz[MAX_N], ans[MAX_N];
vector<int> G[MAX_N];
pair<ll, ll> ori;

struct Point {
ll x, y;
int id;
bool operator < (const Point& rhs) const {
return (y - ori.se) * (rhs.x - ori.fi) < (x - ori.fi) * (rhs.y - ori.se);
}
} P[MAX_N];

void dfs(int u, int p) {
sz[u] = 1;
for (int v: G[u]) if (v != p) {
dfs(v, u);
sz[u] += sz[v];
}
}

void dfs2(int u, int p, int st, int ed) {
int leftCorner = st;
ori.fi = ori.se = INF;
for (int i = st; i <= ed; ++i) {
if (P[i].x < ori.fi || (P[i].x == ori.fi && P[i].y < ori.se)) {
leftCorner = i;
ori.fi = P[i].x, ori.se = P[i].y;
}
}

swap(P[st], P[leftCorner]);
sort(P + st + 1, P + ed + 1);
// ans[P[st].id] = u;
ans[u] = P[st].id;

int count = 0;
for (int v: G[u]) if (v != p) {
dfs2(v, u, st + count + 1, st + count + sz[v]);
count += sz[v];
}
}

int main() {
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
G[u].pb(v); G[v].pb(u);
}
for (int i = 0; i < n; ++i) cin >> P[i].x >> P[i].y, P[i].id = i + 1;
dfs(1, -1);
dfs2(1, -1, 0, n - 1);
for (int i = 1; i <= n; ++i) {
cout << ans[i] << (i == n ? '\n' : ' ');
}
return 0;
}