1644.md (4221B)
1 Source: https://codeforces.com/blog/entry/100227 2 3 [1644A - Doors and Keys](/contest/1644/problem/A "Educational Codeforces Round 123 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 s = input() 16 for (d, k) in zip("RGB", "rgb"): 17 if s.find(d) < s.find(k): 18 print("NO") 19 break 20 else: 21 print("YES") 22 ``` 23 24 [1644B - Anti-Fibonacci Permutation](/contest/1644/problem/B "Educational Codeforces Round 123 (Rated for Div. 2)") 25 26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (Neon)** 33 34 ``` 35 #include <bits/stdc++.h> 36 37 using namespace std; 38 39 int main() { 40 int t; 41 cin >> t; 42 while (t--) { 43 int n; 44 cin >> n; 45 for (int i = 1; i <= n; ++i) { 46 cout << i; 47 for (int j = n; j > 0; --j) if (i != j) 48 cout << ' ' << j; 49 cout << '\n'; 50 } 51 } 52 } 53 ``` 54 55 [1644C - Increase Subarray Sums](/contest/1644/problem/C "Educational Codeforces Round 123 (Rated for Div. 2)") 56 57 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 58 59 **Tutorial** 60 61 Tutorial is loading... 62 63 **Solution (awoo)** 64 65 ``` 66 INF = 10**9 67 68 for _ in range(int(input())): 69 n, x = map(int, input().split()) 70 a = list(map(int, input().split())) 71 mx = [-INF for i in range(n + 1)] 72 mx[0] = 0 73 for l in range(n): 74 s = 0 75 for r in range(l, n): 76 s += a[r] 77 mx[r - l + 1] = max(mx[r - l + 1], s) 78 ans = [0 for i in range(n + 1)] 79 for k in range(n + 1): 80 bst = 0 81 for i in range(n + 1): 82 bst = max(bst, mx[i] + min(k, i) * x) 83 ans[k] = bst 84 print(" ".join([str(x) for x in ans])) 85 ``` 86 87 [1644D - Cross Coloring](/contest/1644/problem/D "Educational Codeforces Round 123 (Rated for Div. 2)") 88 89 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 90 91 **Tutorial** 92 93 Tutorial is loading... 94 95 **Solution 1 (awoo)** 96 97 ``` 98 #include <bits/stdc++.h> 99 100 #define forn(i, n) for (int i = 0; i < int(n); i++) 101 102 using namespace std; 103 104 const int MOD = 998244353; 105 106 int main() { 107 int t; 108 scanf("%d", &t); 109 forn(_, t){ 110 int n, m, k, q; 111 scanf("%d%d%d%d", &n, &m, &k, &q); 112 vector<int> xs(q), ys(q); 113 forn(i, q) scanf("%d%d", &xs[i], &ys[i]); 114 int ans = 1; 115 set<int> ux, uy; 116 for (int i = q - 1; i >= 0; --i){ 117 bool fl = false; 118 if (!ux.count(xs[i])){ 119 ux.insert(xs[i]); 120 fl = true; 121 } 122 if (!uy.count(ys[i])){ 123 uy.insert(ys[i]); 124 fl = true; 125 } 126 if (fl){ 127 ans = ans * 1ll * k % MOD; 128 } 129 if (int(ux.size()) == n || int(uy.size()) == m){ 130 break; 131 } 132 } 133 printf("%d\n", ans); 134 } 135 return 0; 136 } 137 ``` 138 139 **Solution 2 (awoo)** 140 141 ``` 142 from sys import stdin, stdout 143 144 MOD = 998244353 145 146 ux = [] 147 uy = [] 148 for _ in range(int(stdin.readline())): 149 n, m, k, q = map(int, stdin.readline().split()) 150 while len(ux) < n: 151 ux.append(False) 152 while len(uy) < m: 153 uy.append(False) 154 xs = [-1 for i in range(q)] 155 ys = [-1 for i in range(q)] 156 for i in range(q): 157 x, y = map(int, stdin.readline().split()) 158 xs[i] = x - 1 159 ys[i] = y - 1 160 cx = 0 161 cy = 0 162 ans = 1 163 for i in range(q - 1, -1, -1): 164 fl = False 165 if not ux[xs[i]]: 166 ux[xs[i]] = True 167 cx += 1 168 fl = True 169 if not uy[ys[i]]: 170 uy[ys[i]] = True 171 cy += 1 172 fl = True 173 if fl: 174 ans = ans * k % MOD 175 if cx == n or cy == m: 176 break 177 for i in range(q): 178 ux[xs[i]] = False 179 uy[ys[i]] = False 180 stdout.write(str(ans) + "\n") 181 ``` 182 183 [1644E - Expand the Path](/contest/1644/problem/E "Educational Codeforces Round 123 (Rated for Div. 2)") 184 185 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 186 187 **Tutorial** 188 189 Tutorial is loading... 190 191 **Solution (awoo)** 192 193 ``` 194 def calc(s, n): 195 ld = s.find('R') 196 res = ld * (n - 1) 197 y = 0 198 for i in range(len(s) - 1, ld - 1, -1): 199 if s[i] == 'D': 200 res += y 201 else: 202 y += 1 203 return res 204 205 for _ in range(int(input())): 206 n = int(input()) 207 s = input() 208 if s.count(s[0]) == len(s): 209 print(n) 210 continue 211 ans = n * n 212 ans -= calc(s, n) 213 ans -= calc(''.join(['D' if c == 'R' else 'R' for c in s]), n) 214 print(ans) 215 ``` 216 217 [1644F - Basis](/contest/1644/problem/F "Educational Codeforces Round 123 (Rated for Div. 2)") 218 219 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 220 221 **Tutorial** 222 223 Tutorial is loading...