# Educational Codeforces Round 97 (CF1437) Tutorial

# Problem A - Marketing Scheme (opens new window)

Hint

What will happen if r2lr\geq2l?

Solution

Suppose that r2lr\geq2l, then at least we need to cover [l,2l][l,2l]. Obviously, we must have a>la>l, since the length of the segment is already longer than ll. Now if l<a2ll<a\leq2l, there are at most ll modules of aa which are no less than a2\frac{a}{2}, which cannot cover the segment whose length is l+1l+1. But if a>2la>2l, then ll cannot be a good value.

On the contrary, if r<2lr<2l, we can always choose a=2la=2l which will be a valid answer.

So this problem can be simplified to judging whether r<2lr<2l holds.

Time complexity is O(1)O(1).

Code (Python 3)
def read_int():
    return int(input())


def read_ints():
    return map(int, input().split(' '))


t = read_int()
for case_num in range(t):
    l, r = read_ints()
    print('YES' if l * 2 > r else 'NO')
1
2
3
4
5
6
7
8
9
10
11
12

# Problem B - Reverse Binary Strings (opens new window)

Hint

How many 0000 or 1111 pairs can be reduced within one reverse?

Solution

We can reduce the number of 0000 or 1111 pairs by at most 22 within one reverse. So we can simply count the total number of such pairs, and get the answer.

Time complexity is O(N)O(N).

Code (Python 3)
def read_int():
    return int(input())


def read_ints():
    return map(int, input().split(' '))


t = read_int()
for case_num in range(t):
    n = read_int()
    s = input()
    tot = 0
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            tot += 1
    print((tot + 1) // 2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Problem C - Chef Monocarp (opens new window)

Hint
  1. We will never use numbers larger than 2n2n.
  2. The original sequence of the array does not matter.
Solution

We will never put out an oven at t>2nt>2n, because a[i]na[i]\leq n, so even if we put out the first oven at t=nt=n, we can put out the last oven at t=2n1t=2n-1. Thus in any case that we put out an oven at t>2nt>2n, we can always reduce the total unpleasant values by replacing it with a smaller timestamp. Actually, the upper limit can be further squeezed, but 2n2n is fine enough.

We can sort the array first, then do simple dynamic programming, with dp[t]dp[t] meaning the total unpleasant values if the last oven is put out at tt.

Since time is monotonic, when we consider the next oven, we can only transit from smaller timestamps. For the ii-th oven, we will update dp[t]dp[t] with mint<t(dp[t])+ta[i]\min_{t'<t}(dp[t'])+|t-a[i]|. In order to save time, we can maintain a prefix minimum lolo during the iteration.

Total time complexity is O(N2)O(N^2), which is enough to pass the time limit.

Code (Python 3)
def read_int():
    return int(input())


def read_ints():
    return map(int, input().split(' '))


inf = int(1e9)
t = read_int()
for case_num in range(t):
    n = read_int()
    a = list(read_ints())
    a.sort()
    dp = [0 for _ in range(n * 2 + 1)]
    for t in a:
        ndp = [inf for _ in range(n * 2 + 1)]
        lo = inf
        for i in range(n * 2):
            lo = min(lo, dp[i])
            ndp[i + 1] = min(ndp[i + 1], lo + abs(i + 1 - t))
        dp = ndp
    print(min(dp))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Problem D - Minimal Height Tree (opens new window)

Hint

Just go greedy.

Solution

We can arrange the nodes greedily. Unless the current number is smaller than the last one, we will keep connecting the numbers to the current parent node. Otherwise, we will move to the next parent node (which might be at the next level).

Time complexity is O(N)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;
    read(n);
    int height = 0;
    vector<int> level = {1};
    int col = 0, first, last = 0;
    read(first);
    for (int i = 0; i < n - 1; ++i) {
      int u;
      read(u);
      if (u < last) {
        col++;
        if (col == level[height]) {
          height++;
          col = 0;
        }
      }
      if (level.size() <= height + 1)
        level.emplace_back(0);
      level[height + 1]++;
      last = u;
    }
    printf("%d\n", (int)level.size() - 1);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(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

# Problem E - Make It Increasing (opens new window)

Hint
  1. We can add two sentinel elements at either end of aa and bb. Then the original problem will be split into several subtasks.
  2. For each subtask, we actually need to find the longest increasing subsequence.
Solution

The first step is to split the original problem into subtasks. Each subtask has four parameters, ll and rr for the start and the end of the interval, and lolo and hihi for the minimum valid value of the left end, and the maximum valid value of the right end.

Then for each subtask, we have three situations:

  • l>rl>r, which means the interval is empty. The answer is 00.
  • l=rl=r, which means the length of the interval is 11. The answer depends on whether a[l]a[l] fits in [lo,hi][lo,hi].
  • l<rl<r. In this case, we need to find the longest increasing subsequence. However, there are two differences compared to the classical LIS problem. One is that, if the current number does not fit in its valid range (which can be calculated using lolo, hihi, and ii), it cannot be used in the LIS. The other difference is that we cannot use a[i]a[i] directly. Considering the following case, [2,5,3,1][2,5,3,1]. Can we make an LIS with [2,3][2,3]? In this problem, we cannot, because there will be no room for the middle elements. How can we take the distance into consideration? We can use a[i]ia[i]-i instead of a[i]a[i], and now we will find the longest non-decreasing subsequence instead of the longest increasing subsequence.

The algorithm for LIS is a classical DP enhanced with binary search, which takes O(LlogL)O(L\log L) time for an interval of length LL.

So we have the total time complexity of O(NlogN)O(N\log N).

Code (C++)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define INF 0x3f3f3f3f

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, k;
    read(n), read(k);
    vector<int> a(n + 2), b(k + 2);
    a[0] = -INF, a[n + 1] = INF;
    b[0] = 0, b[k + 1] = n + 1;
    for (int i = 1; i <= n; ++i)
      read(a[i]);
    for (int i = 1; i <= k; ++i) {
      read(b[i]);
      if (a[b[i]] - a[b[i - 1]] < b[i] - b[i - 1]) {
        printf("-1");
        return;
      }
    }
    int ans = 0;
    auto handle = [&](int l, int r, int lo, int hi) {
      if (l > r)
        return 0;
      if (l == r)
        return (a[l] >= lo && a[l] <= hi) ? 0 : 1;
      vector<int> LIS;
      for (int i = l; i <= r; ++i) {
        int clo = lo + i - l, chi = hi - r + i;
        if (a[i] < clo || a[i] > chi)
          continue;
        int pos = upper_bound(LIS.begin(), LIS.end(), a[i] - i) - LIS.begin();
        if (pos >= LIS.size())
          LIS.emplace_back(a[i] - i);
        else
          LIS[pos] = a[i] - i;
      }
      return r - l + 1 - (int)LIS.size();
    };
    for (int i = 1; i <= k + 1; ++i)
      ans += handle(b[i - 1] + 1, b[i] - 1, a[b[i - 1]] + 1, a[b[i]] - 1);
    printf("%d", ans);
  }
};

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

# Problem F - Emotional Fishermen (opens new window)

Hint

When the current maximum value is aa, what is the maximum possible value of the second-largest number?

Solution

An important observation is that, if the current maximum is maxmax, then the current second-largest number secondsecond must follow 2second<max2second<max.

First, we will sort the numbers. Then we can find pre[i]pre[i] for each ii, which means the largest index that can be included in the set when the largest number is a[i]a[i] (after sorting).

After that, we will do dynamic programming, where dp[i]dp[i] means the number of valid permutations when the current largest number is a[i]a[i]. There are two types of transitions:

  1. From dp[i]dp[i] to dp[i]dp[i]. This requires that we choose a number a[j]a[j] where jpre[i]j\leq pre[i]. The possible choices can be determined from the current size of the set, since all numbers except a[i]a[i] that are in the set right now must have indices i\leq i.
  2. From dp[j]dp[j] to dp[i]dp[i], where jpre[i]j\leq pre[i]. To calculate this type of transition quickly, we can calculate the prefix sum of the dpdp array after each iteration.

The original state is dp[i]=1dp[i]=1, which means the set contains a[i]a[i] only.

The total time complexity is O(N2)O(N^2).

Code (C++)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define MOD 998244353

using namespace std;
typedef long long ll;

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;
    read(n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
      read(a[i]);
    sort(a.begin(), a.end());
    if (a[n - 2] * 2 > a[n - 1]) {
      printf("0");
      return;
    }

    vector<int> pre(n, -1);
    int l = n - 2;
    for (int r = n - 1; r >= 0; --r) {
      while (l >= 0 && a[l] * 2 > a[r])
        l--;
      if (l >= 0)
        pre[r] = l;
    }

    ll ans = 0;
    vector<ll> dp(n, 1), S(n + 1);
    for (int i = 1; i <= n; ++i)
      S[i] = i;
    for (int i = 1; i < n; ++i) {
      vector<ll> ndp(n, 0);
      for (int j = 0; j < n; ++j) {
        // Case 1: j to j
        int left = pre[j] == -1 ? 0 : pre[j] + 1;
        left -= i - 1;
        if (left > 0)
          ndp[j] = (ndp[j] + dp[j] * left % MOD);

        // Case 2: smaller to j
        if (pre[j] != -1)
          ndp[j] = (ndp[j] + S[pre[j] + 1]) % MOD;
      }
      for (int j = 1; j <= n; ++j)
        S[j] = (S[j - 1] + ndp[j - 1]) % MOD;
      dp = move(ndp);
    }
    printf("%lld", S[n]);
  }
};

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

# Problem G - Death DBMS (opens new window)

Hint

We need to find the occurrences of all names in a given string. Aha-Corasick Automaton is just made for this.

Solution

This is a very typical ACA problem. Since there might be duplicate names, we can use a set for each name in order to maintain the largest value of this name.

For each query, we need to travel up the trie following the fail pointers, in order to collect all the valid names we have met, and find the maximum value.

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

using namespace std;
struct Node {
  int idx = -1, fail = 0, children[26]{};
};

int main() {
  int n, q;
  cin >> n >> q;

  vector<string> names(n + 1);
  unordered_map<string, int> dict;
  unordered_map<int, int> id_dict;
  vector<set<pair<int, int>, greater<>>> heaps;
  vector<int> suspicion(n + 1);
  suspicion[0] = -1;
  vector<Node> nodes = {Node{}};
  int idx = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> names[i];
    if (dict.count(names[i])) {
      heaps[dict[names[i]]].emplace(0, i);
      id_dict[i] = dict[names[i]];
      continue;
    }
    dict[names[i]] = idx;
    id_dict[i] = idx;
    heaps.push_back({{0, i}});
    int p = 0;
    for (char c : names[i]) {
      if (!nodes[p].children[c - 'a']) {
        nodes[p].children[c - 'a'] = nodes.size();
        nodes.emplace_back(Node{});
      }
      p = nodes[p].children[c - 'a'];
    }
    nodes[p].idx = idx++;
  }

  queue<int> que, visited;
  vector<bool> vis(nodes.size());
  for (int u : nodes[0].children)
    if (u)
      que.push(u);
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (int i = 0; i < 26; ++i) {
      auto &v = nodes[u].children[i];
      if (v) {
        nodes[v].fail = nodes[nodes[u].fail].children[i];
        que.push(v);
      } else
        v = nodes[nodes[u].fail].children[i];
    }
  }

  string output;

  auto query = [&](string &s) {
    int ans = -1;
    int p = 0;
    int idx = 0;
    while (idx < s.size()) {
      char c = s[idx];
      if (nodes[p].children[c - 'a']) {
        p = nodes[p].children[c - 'a'];
        if (!vis[p]) {
          vis[p] = true;
          que.push(p);
        }
        idx++;
      } else {
        p = nodes[p].fail;
        if (!p)
          idx++;
      }
    }
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      visited.push(u);
      if (nodes[u].idx != -1)
        ans = max(ans, heaps[nodes[u].idx].begin()->first);
      if (nodes[u].fail && !vis[nodes[u].fail]) {
        vis[nodes[u].fail] = true;
        que.push(nodes[u].fail);
      }
    }
    while (!visited.empty()) {
      vis[visited.front()] = false;
      visited.pop();
    }
    output += to_string(ans) + "\n";
  };

  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int i, x;
      cin >> i >> x;
      heaps[id_dict[i]].erase({suspicion[i], i});
      suspicion[i] = x;
      heaps[id_dict[i]].emplace(suspicion[i], i);
    } else {
      string s;
      cin >> s;
      query(s);
    }
  }

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