1536.md (41198B)
1 Source: https://codeforces.com/blog/entry/91520 2 3 We hope you liked the problems! If you’re curious about the two different problem formats, initially [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani"), [malachi_toney_goat](/profile/malachi_toney_goat "Master malachi_toney_goat"), [qlf9](/profile/qlf9 "Candidate Master qlf9") and I were working on Omkar 3 with [antontrygubO_o](/profile/antontrygubO_o "International Grandmaster antontrygubO_o") while [gotexans](/profile/gotexans "Master gotexans") was working on a separate round with [isaf27](/profile/isaf27 "International Grandmaster isaf27"). We eventually decided to join forces and combine the rounds, resulting in the current Omkar 3. 4 5 # [1536A - Omkar and Bad Story](/contest/1536/problem/A "Codeforces Round 724 (Div. 2)") 6 7 Idea: [rabaiBomkarBittalBang](/profile/rabaiBomkarBittalBang "Candidate Master rabaiBomkarBittalBang") 8 9 Preparation: [rabaiBomkarBittalBang](/profile/rabaiBomkarBittalBang "Candidate Master rabaiBomkarBittalBang"), [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani"), [qlf9](/profile/qlf9 "Candidate Master qlf9") 10 11 [Video editorial](https://www.youtube.com/watch?v=GZeihS2xTSc) 12 13 **Hint** 14 15 Consider what happens when $a$ contains a negative number. 16 17 **Solution** 18 19 We first claim that if any negative number exists in $a$, then no solution exists. Denote $p$ as the smallest number in $a$ and $q$ as another arbitrary number in the array (as $n \geq 2$, $q$ always exists). Clearly, $|q - p| = q - p \gt 0$. However, because $p$ is negative, $q - p \gt q$. As such, adding $q - p$ to the output array would create the pair $(q - p, p)$ with difference $q - 2p \gt q - p$. We have the same problem as before; thus, it is impossible to create a *nice* array if there exists a negative number in $a$. 20 21 After we deal with this case, we now claim that $b = [0, 1, 2, ..., 100]$ is a valid *nice* array for any $a$ that contains no negative numbers. It is easy to verify that this is a valid *nice* array. And since in this case, every element of $a$ is nonnegative and distinct, it is always possible to rearrange and add elements to $a$ to obtain $b$. 22 23 **Implementation in Java by rabaiBomkarBittalBang** 24 25 ``` 26 //DecimalFormat f = new DecimalFormat("##.00"); 27 28 import java.util.*; 29 import java.io.*; 30 import java.math.*; 31 import java.text.*; 32 public class OmkarAndBadStory { 33 public static void main(String[] omkar) throws Exception 34 { 35 BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); 36 StringTokenizer st = new StringTokenizer(in.readLine()); 37 StringBuilder sb = new StringBuilder(); 38 int cases = Integer.parseInt(st.nextToken()); 39 for(int i = 0; i < cases; i++) 40 { 41 solve(in, st, sb); 42 } 43 System.out.print(sb); 44 } 45 public static void solve(BufferedReader in, StringTokenizer st, StringBuilder sb) throws Exception 46 { 47 int k = Integer.parseInt(in.readLine()); 48 String s = in.readLine(); 49 st = new StringTokenizer(s); 50 boolean hasneg = false; 51 int max = 0; 52 int x; 53 int[] arr = new int[k]; 54 for(int i = 0; i < k; i++) 55 { 56 x = Integer.parseInt(st.nextToken()); 57 arr[i] = x; 58 if(x < 0) 59 { 60 hasneg = true; 61 } 62 else 63 { 64 max = Math.max(max, x); 65 } 66 } 67 if(hasneg) 68 { 69 sb.append("NO\n"); 70 } 71 else 72 { 73 sb.append("YES\n"); 74 sb.append((max+1)+"\n"); 75 for(int i = 0; i < max; i++) 76 { 77 sb.append(i + " "); 78 } 79 sb.append(max+""); 80 sb.append("\n"); 81 } 82 } 83 84 } 85 ``` 86 87 **Implementation in Kotlin by Tlatoani** 88 89 ``` 90 fun main() { 91 for (c in 1..readLine()!!.toInt()) { 92 val n = readLine()!!.toInt() 93 val numberballs = readLine()!!.split(" ").map { it.toInt() } 94 if (numberballs.min()!! < 0) { 95 println("nO") 96 } else { 97 println("yEs") 98 println(numberballs.max()!! + 1) 99 println((0..numberballs.max()!!).joinToString(" ")) 100 } 101 } 102 } 103 ``` 104 105 **Implementation in C++ by kefaa2** 106 107 ``` 108 #ifdef DEBUG 109 #define _GLIBCXX_DEBUG 110 #endif 111 #pragma GCC optimize("O3") 112 #include <bits/stdc++.h> 113 114 using namespace std; 115 typedef long double ld; 116 typedef long long ll; 117 int n; 118 int main() { 119 ios_base::sync_with_stdio(false); 120 cin.tie(nullptr); 121 // freopen("input.txt", "r", stdin); 122 int tst; 123 cin >> tst; 124 while (tst--) { 125 int n; 126 cin >> n; 127 bool f = false; 128 for (int i = 1; i <= n; i++) { 129 int x; 130 cin >> x; 131 if (x < 0) f = true; 132 } 133 if (f) { 134 cout << "NO\n"; 135 } 136 else { 137 cout << "YES\n"; 138 cout << 101 << '\n'; 139 for (int i = 0; i <= 100; i++) cout << i << " "; 140 cout << '\n'; 141 } 142 } 143 return 0; 144 } 145 ``` 146 147 **Implementation in Haskell by Tlatoani** 148 149 ``` 150 import Data.List (intercalate) 151 import Control.Monad (replicateM) 152 153 main = do t <- read <$> getLine 154 replicateM t solve 155 156 solve = do getLine 157 xs <- (map read . words) <$> getLine 158 putStrLn (if any (< 0) xs then "nO" else ("yEs\n101\n" ++ intercalate " " (map show [0..100]))) 159 ``` 160 161 # [1536B - Prinzessin der Verurteilung](/contest/1536/problem/B "Codeforces Round 724 (Div. 2)") 162 163 Idea: [gotexans](/profile/gotexans "Master gotexans") 164 165 Preparation: [gotexans](/profile/gotexans "Master gotexans") 166 167 [Video editorial](https://www.youtube.com/watch?v=--_QUTD7t94) 168 169 **Hint 1** 170 171 Pigeonhole principle 172 173 **Hint 2** 174 175 What is the longest the answer can be? 176 177 **Solution** 178 179 Let’s brute force check all substrings of length <= 3 and print the lexicographically smallest one that doesn’t appear as a substring in the input. We can guarantee that we will come across the answer due to the pigeonhole principle. There are at most $n+n-1+n-2 = 3n-3$ possible substrings of length 3 or shorter in the input. There exist $26+26^2+26^3 = 18278$ total substrings of length 3 or shorter. It is impossible for the input to contain all $18278$ substrings, as $3n-3 \lt 18278$ for $n \leq 1000$. 180 181 Final runtime looks something like $O(18278n)$ or $O(n)$ depending on how you implement substring checking. 182 183 **Implementation in Java by hu_tao** 184 185 ``` 186 //stan hu tao 187 //come to K-expo!!! 188 //watch me get carried in nct ridin 189 import static java.lang.Math.max; 190 import static java.lang.Math.min; 191 import static java.lang.Math.abs; 192 import static java.lang.System.out; 193 import java.util.*; 194 import java.io.*; 195 import java.math.*; 196 197 public class FischlPog 198 { 199 public static void main(String hi[]) throws Exception 200 { 201 ArrayList<String> ls = new ArrayList<String>(); 202 for(int a=0; a < 26; a++) 203 ls.add(get(a)+""); 204 for(int a=0; a < 26; a++) 205 for(int b=0; b < 26; b++) 206 ls.add(get(a)+""+get(b)); 207 for(int a=0; a < 26; a++) 208 for(int b=0; b < 26; b++) 209 for(int c=0; c < 26; c++) 210 ls.add(get(a)+""+get(b)+""+get(c)); 211 Collections.sort(ls, (x,y) -> { 212 int len1 = x.length(); 213 int len2 = y.length(); 214 if(len1 != len2) 215 return len1-len2; 216 return x.compareTo(y); 217 }); 218 //assume multitests exist 219 BufferedReader infile = new BufferedReader(new InputStreamReader(System.in)); 220 StringTokenizer st = new StringTokenizer(infile.readLine()); 221 int T = Integer.parseInt(st.nextToken()); 222 StringBuilder sb = new StringBuilder(); 223 while(T-->0) 224 { 225 int N = Integer.parseInt(infile.readLine()); 226 String input = infile.readLine(); 227 HashSet<String> substrings = new HashSet<String>(); 228 for(int len=1; len <= 3; len++) 229 for(int i=0; i < N-len+1; i++) 230 substrings.add(input.substring(i, i+len)); 231 for(int i=0; i < ls.size(); i++) 232 if(!substrings.contains(ls.get(i))) 233 { 234 sb.append(ls.get(i)+"\n"); 235 break; 236 } 237 } 238 System.out.print(sb); 239 } 240 public static char get(int a) 241 { 242 return (char)(a+'a'); 243 } 244 } 245 ``` 246 247 **Implementation in Kotlin by Tlatoani** 248 249 ``` 250 fun main() { 251 repeat(readLine()!!.toInt()) { 252 val n = readLine()!!.toInt() 253 val s = readLine()!! 254 for (length in 1..n) { 255 var mex = "" 256 var answer: String? = null 257 fun recur() { 258 if (mex.length == length) { 259 if (mex !in s) { 260 answer = mex 261 } 262 } else { 263 for (chara in 'a'..'z') { 264 mex += chara 265 recur() 266 if (answer != null) { 267 return 268 } 269 mex = mex.substring(0 until mex.lastIndex) 270 } 271 } 272 } 273 recur() 274 if (answer != null) { 275 println(answer) 276 break 277 } 278 } 279 } 280 } 281 ``` 282 283 **Implementation in C++ by 1-gon** 284 285 ``` 286 #include <bits/stdc++.h> 287 288 #define ll long long 289 #define sz(x) ((int) (x).size()) 290 #define all(x) (x).begin(), (x).end() 291 #define fi first 292 #define se second 293 #define vi vector<int> 294 #define pii pair<int, int> 295 #define rep(i, a, b) for(int i = (a); i < (b); i++) 296 using namespace std; 297 template<typename T> 298 using minpq = priority_queue<T, vector<T>, greater<T>>; 299 300 void solve() { 301 int n; 302 string s; 303 cin >> n >> s; 304 set<string> se; 305 rep(i, 0, n) { 306 string ss; 307 for(int k = 0; k < 5 && i + k < n; k++) { 308 ss.push_back(s[i + k]); 309 se.insert(ss); 310 } 311 } 312 rep(len, 1, 6) { 313 string t(len, 'a'); 314 while(true) { 315 if(se.count(t) == 0) { 316 cout << t << '\n'; 317 return; 318 } 319 int idx = len - 1; 320 while(idx >= 0 && t[idx] == 'z') { 321 t[idx] = 'a'; 322 idx--; 323 } 324 if(idx < 0) break; 325 t[idx]++; 326 } 327 } 328 } 329 330 int main() { 331 ios::sync_with_stdio(false); 332 cin.tie(0); 333 int te; 334 cin >> te; 335 while(te--) solve(); 336 } 337 ``` 338 339 **Implementation in Haskell by Tlatoani** 340 341 ``` 342 import Data.List (intercalate, tails, isPrefixOf, head) 343 import Control.Monad (replicateM) 344 import Data.Maybe (fromJust, listToMaybe, catMaybes) 345 346 main = do t <- read <$> getLine 347 replicateM t solve 348 349 solve = do getLine 350 s <- getLine 351 putStrLn (leastNonSubstring s) 352 353 leastNonSubstring s = head $ catMaybes [leastOfLength l | l <- [1..]] 354 where leastOfLength l = helper "" l 355 helper prefix 0 | isSubstring prefix s = Nothing 356 | otherwise = Just prefix 357 helper prefix l = listToMaybe $ catMaybes [helper (prefix ++ [letter]) (l - 1) | letter <- ['a'..'z']] 358 359 isSubstring s t = any id (map (isPrefixOf s) (tails t)) 360 ``` 361 362 # [1536C - Diluc and Kaeya](/contest/1536/problem/C "Codeforces Round 724 (Div. 2)") 363 364 Idea: [gotexans](/profile/gotexans "Master gotexans") 365 366 Preparation: [gotexans](/profile/gotexans "Master gotexans") 367 368 [Video editorial](https://www.youtube.com/watch?v=00TBpmgCwe4) 369 370 **Hint 1** 371 372 Turn into geometry problem 373 374 **Hint 2** 375 376 Represent every prefix as $(x, y)$ point in cartesian plane where $x$ = frequency of ‘D’ and $y$ = frequency of ‘K’. Draw a polyline connecting these points in order of increasing length of prefix. 377 378 **Hint 3** 379 380 Draw a line from origin to point. What can we say about intersections of poly-line with this line? 381 382 **Solution** 383 384 For each prefix, label it with a pair $(a, b)$ where $a$ = frequency of ‘D’ in this prefix and $b$ = frequency of ‘K’ in this prefix. Divide $a$ and $b$ by $gcd(a, b)$. If we iterate over all prefixes from to left, we can notice that the answer for the prefix equals the # of occurrences of this pair we have seen so far! This can be visualized by drawing a poly-line as mentioned in the hints. 385 386 As for implementation, you can use a map in C++ or a HashMap in Java to achieve $O(n \log n)$ or $O(n)$ runtime. 387 388 **Implementation in Java by hu_tao** 389 390 ``` 391 //stan hu tao 392 //come to K-expo!!! 393 //watch me get carried in nct ridin 394 import static java.lang.Math.max; 395 import static java.lang.Math.min; 396 import static java.lang.Math.abs; 397 import static java.lang.System.out; 398 import java.util.*; 399 import java.io.*; 400 import java.math.*; 401 402 public class DilucKaeyaModel 403 { 404 public static void main(String hi[]) throws Exception 405 { 406 BufferedReader infile = new BufferedReader(new InputStreamReader(System.in)); 407 StringTokenizer st = new StringTokenizer(infile.readLine()); 408 int T = Integer.parseInt(st.nextToken()); 409 StringBuilder sb = new StringBuilder(); 410 while(T-->0) 411 { 412 st = new StringTokenizer(infile.readLine()); 413 int N = Integer.parseInt(st.nextToken()); 414 char[] arr = infile.readLine().toCharArray(); 415 HashMap<String, Integer> map = new HashMap<String, Integer>(); 416 int dc = 0; 417 int kc = 0; 418 for(char c: arr) 419 { 420 if(c == 'D') 421 dc++; 422 else 423 kc++; 424 int a = dc; 425 int b = kc; 426 if(a == 0) 427 b = 1; 428 else if(b == 0) 429 a = 1; 430 else 431 { 432 int gcd = gcd(a, b); 433 a /= gcd; b /= gcd; 434 } 435 String key = a+":"+b; 436 push(map, key); 437 sb.append(map.get(key)+" "); 438 } 439 sb.append("\n"); 440 } 441 System.out.print(sb); 442 } 443 public static int gcd(int a, int b) 444 { 445 if(a > b) 446 { 447 int t = a; 448 a = b; 449 b = t; 450 } 451 if(a == 0) 452 return b; 453 return gcd(b%a, a); 454 } 455 public static void push(HashMap<String, Integer> map, String k) 456 { 457 if(!map.containsKey(k)) 458 map.put(k, 1); 459 else 460 map.put(k, map.get(k)+1); 461 } 462 } 463 ``` 464 465 **Implementation in Kotlin by Tlatoani** 466 467 ``` 468 import java.util.* 469 fun main() { 470 repeat(readLine()!!.toInt()) { 471 readLine() 472 val freq = mutableMapOf<Pair<Int, Int>, Int>() 473 var d = 0 474 var k = 0 475 val joiner = StringJoiner(" ") 476 for (chara in readLine()!!) { 477 when (chara) { 478 'D' -> d++ 479 'K' -> k++ 480 } 481 val g = gcd(d, k) 482 val r = Pair(d / g, k / g) 483 freq[r] = (freq[r] ?: 0) + 1 484 joiner.add(freq[r]!!.toString()) 485 } 486 println(joiner) 487 } 488 } 489 490 fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b) 491 ``` 492 493 **Implementation in C++ by smax** 494 495 ``` 496 #include <bits/stdc++.h> 497 using namespace std; 498 499 #ifdef LOCAL 500 #define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__) 501 #else 502 #define DEBUG(...) 6 503 #endif 504 505 template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";} 506 template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr> 507 ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";} 508 template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";} 509 template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else 510 if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << s.substr(0, i) << " = " << x << " | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}} 511 512 pair<int, int> getRatio(int a, int b) { 513 int g = __gcd(a, b); 514 a /= g; 515 b /= g; 516 return {a, b}; 517 } 518 519 int main() { 520 ios_base::sync_with_stdio(false); 521 cin.tie(NULL); 522 523 int t; 524 cin >> t; 525 while (t--) { 526 int n; 527 string s; 528 cin >> n >> s; 529 530 int d = 0, k = 0; 531 map<pair<int, int>, int> mp; 532 for (char c : s) { 533 if (c == 'D') d++; 534 else k++; 535 cout << ++mp[getRatio(d, k)] << " "; 536 } 537 cout << "\n"; 538 } 539 540 return 0; 541 } 542 ``` 543 544 **Implementation in Haskell by Tlatoani** 545 546 ``` 547 import Data.List (intercalate) 548 import Control.Monad (mapM, replicateM) 549 import Data.Ratio ((%)) 550 import Data.Map (empty, findWithDefault, insert) 551 552 main = do t <- read <$> getLine 553 replicateM t solve 554 555 solve = do getLine 556 s <- getLine 557 putStrLn (intercalate " " (map show (maxBlocks s))) 558 559 maxBlocks s = helper s empty 0 0 560 where helper "" _ _ _ = [] 561 helper (c:s) prev d k = x : helper s prev' d' k' 562 where (d', k') | c == 'D' = (d + 1, k) 563 | c == 'K' = (d, k + 1) 564 r | k' == 0 = 69000000 % 1 565 | otherwise = d' % k' 566 x = (findWithDefault 0 r prev) + 1 567 prev' = insert r x prev 568 ``` 569 570 # [1536D - Omkar and Medians](/contest/1536/problem/D "Codeforces Round 724 (Div. 2)") 571 572 Idea: [rabaiBomkarBittalBang](/profile/rabaiBomkarBittalBang "Candidate Master rabaiBomkarBittalBang") 573 574 Preparation: [rabaiBomkarBittalBang](/profile/rabaiBomkarBittalBang "Candidate Master rabaiBomkarBittalBang"), [Tlatoani](/profile/Tlatoani "International Grandmaster Tlatoani") 575 576 [Video editorial](https://www.youtube.com/watch?v=JyOFalVJaEc) 577 578 **Solution** 579 580 For some $k \lt n$, assume $b_1, b_2, \cdots, b_{k}$ is the *OmkArray* of some $a_1, a_2, \cdots, a_{2k-1}$, and we want to see what values of $a_{2k}, a_{2k+1}$ we can add so that $b_1, b_2, \cdots, b_{k+1}$ is the *OmkArray* of $a_1, a_2, \cdots, a_{2k+1}$. Let $c_1, c_2, \cdots, c_{2k-1}$ be $a_1, a_2, \cdots, a_{2k-1}$ sorted in ascending order. 581 582 If $b_{k+1} \geq b_k$, note that $b_{k} = c_k$ and there are $k-2$ elements of $a$ $\geq c_{k+1}$, so no matter how large $a_{2k}, a_{2k+1}$ are there will be at most $k$ elements larger than $c_{k+1}$ in $a_1, a_2, \cdots, a_{2k+1}$. This gives $b_{k+1} \leq c_{k+1}$. We can use a similar argument to show $b_{k+1} \geq c_{k-1}$. Now we want to bound $c_{k+1}$ and $c_{k-1}$. Note that each distinct value among $b_1, b_2, \cdots, b_k$ must appear at least once in $a_1, a_2, \cdots, a_{2k-1}$. Therefore, if $i$, $j$ satisfy that $b_i$ is the largest value of $b_i\leq b_k$ and $i \neq k$, and $b_j$ is the smallest value of $b_j \geq b_k$, $j \neq k$, then we have $c_{k+1} \leq b_j$, $c_{k-1} \geq b_i$, and so $b_i \leq b_{k+1} \leq b_j$. If no such largest/smallest values exist, then we can assume $b_{k+1}$ is not bounded above/below. 583 584 Therefore, if $b$ has an *OmkArray*, it is necessary that for all $i$, there does not exist a $j\leq i$ such that $b_j$ is between $b_i$ and $b_{i+1}$, exclusive. I claim this is also sufficient. We can construct such an array $a$ using the following algorithm: 585 586 * Let $a_1 = b_1$. 587 * If $b_{i+1}=b_j$ for some $b_j \lt b_i$ with $j \lt i$, let $a_{2k-2}, a_{2k-1} = -\infty$ (we can replace $-\infty$ with some sufficiently small constant at the end of our array creation process). 588 * Otherwise, if $b_{i+1} \lt b_i$ then let $a_{2k-2} = -\infty$, $a_{2k-1} = b_{i+1}$. 589 * If $b_{i+1}=b_j$ for some $b_j \gt b_i$ with $j \lt i$, let $a_{2k-2}, a_{2k-1} = \infty$ (we can replace $\infty$ with some sufficiently large constant at the end of our array creation process). 590 * Otherwise, if $b_{i+1} \gt b_i$ then let $a_{2k-2} = \infty$, $a_{2k-1} = b_{i+1}$. 591 * Finally, if $b_{i+1} = b_i$, let $a_{2k-2} = -\infty$, $a_{2k-1} = \infty$. 592 593 This means that an equivalent condition to having an *OmkArray* is for all $i$, there does not exist a $j\leq i$ such that $b_j$ is between $b_i$ and $b_{i+1}$, exclusive. There are multiple ways to check this for an array $b$, but one clean way would be to keep some TreeSet $s$, and check if $b_{i+1}$ is between \t{s.ceil($b_i$)} and \t{s.floor($b_i$)} for all $i$, and then adding $b_{i+1}$ to $s$ if it is not already added. 594 595 **Linear time implementation in Java by rabaiBomkarBittalBang** 596 597 ``` 598 //Praise our lord and saviour qlf9 599 import java.util.*; 600 import java.io.*; 601 import java.math.*; 602 import java.text.*; 603 public class C{ 604 public static void main(String[] omkar) throws Exception 605 { 606 BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); 607 StringTokenizer st = new StringTokenizer(in.readLine()); 608 StringBuilder sb = new StringBuilder(); 609 int cases = Integer.parseInt(st.nextToken()); 610 for(int i = 0; i < cases; i++) 611 { 612 solve(in, st, sb); 613 } 614 System.out.print(sb); 615 } 616 public static void solve(BufferedReader in, StringTokenizer st, StringBuilder sb) throws Exception 617 { 618 int n = Integer.parseInt(in.readLine()); 619 int[] arr = readArr(n, in, st); 620 Node currNode = new Node(arr[0]); 621 int currVal; 622 Node temp; 623 for(int i = 1; i < n; i++) 624 { 625 currVal = arr[i]; 626 if(currVal < currNode.value) 627 { 628 if(currNode.prev != null && currVal < currNode.prev.value) 629 { 630 sb.append("NO\n"); 631 return; 632 } 633 if(currNode.prev == null || currNode.prev.value < currVal) 634 { 635 temp = new Node(currVal); 636 temp.prev = currNode.prev; 637 temp.next = currNode; 638 if(currNode.prev != null) 639 { 640 currNode.prev.next = temp; 641 } 642 currNode.prev = temp; 643 currNode = temp; 644 } 645 else 646 { 647 currNode = currNode.prev; 648 } 649 } 650 else if(currVal > currNode.value) 651 { 652 if(currNode.next != null && currVal > currNode.next.value) 653 { 654 sb.append("NO\n"); 655 return; 656 } 657 if(currNode.next == null || currNode.next.value > currVal) 658 { 659 temp = new Node(currVal); 660 temp.next = currNode.next; 661 temp.prev = currNode; 662 if(currNode.next != null) 663 { 664 currNode.next.prev = temp; 665 } 666 currNode.next = temp; 667 currNode = temp; 668 } 669 else 670 { 671 currNode = currNode.next; 672 } 673 } 674 } 675 sb.append("YES\n"); 676 } 677 public static int[] readArr(int N, BufferedReader in, StringTokenizer st) throws Exception 678 { 679 int[] arr = new int[N]; 680 st = new StringTokenizer(in.readLine()); 681 for(int i=0; i < N; i++) 682 arr[i] = Integer.parseInt(st.nextToken()); 683 return arr; 684 } 685 static class Node 686 { 687 int value; 688 Node prev; 689 Node next; 690 public Node(int v) 691 { 692 value = v; 693 prev = null; 694 next = null; 695 } 696 } 697 } 698 ``` 699 700 **Implementation in Kotlin by Tlatoani** 701 702 ``` 703 import java.io.BufferedReader 704 import java.io.InputStreamReader 705 import java.util.* 706 707 fun main() { 708 val jin = BufferedReader(InputStreamReader(System.`in`)) 709 val out = StringBuilder() 710 for (c in 1..jin.readLine().toInt()) { 711 val n = jin.readLine().toInt() 712 val tokenizer = StringTokenizer(jin.readLine()) 713 var mid = tokenizer.nextToken().toInt() 714 val treeSet = TreeSet<Int>() 715 treeSet.add(Int.MIN_VALUE) 716 treeSet.add(mid) 717 treeSet.add(Int.MAX_VALUE) 718 var answer = true 719 for (j in 2..n) { 720 val next = tokenizer.nextToken().toInt() 721 if (next < treeSet.lower(mid)!! || next > treeSet.higher(mid)!!) { 722 answer = false 723 break 724 } 725 mid = next 726 treeSet.add(mid) 727 } 728 out.appendln(if (answer) "yEs" else "nO") 729 } 730 print(out) 731 } 732 ``` 733 734 **Implementation in C++ by kefaa2** 735 736 ``` 737 #ifdef DEBUG 738 #define _GLIBCXX_DEBUG 739 #endif 740 #pragma GCC optimize("O3") 741 #include <bits/stdc++.h> 742 743 using namespace std; 744 typedef long double ld; 745 typedef long long ll; 746 int n; 747 const int maxN = 2e5 + 10; 748 int a[maxN]; 749 750 int main() { 751 ios_base::sync_with_stdio(false); 752 cin.tie(nullptr); 753 // freopen("input.txt", "r", stdin); 754 int tst; 755 cin >> tst; 756 while (tst--) { 757 int n; 758 cin >> n; 759 for (int i = 1; i <= n; i++) { 760 cin >> a[i]; 761 } 762 set<int> s; 763 s.insert(a[1]); 764 bool ok = true; 765 for (int i = 2; i <= n; i++) { 766 int prv = a[i - 1]; 767 if (prv != a[i]) { 768 if (prv < a[i]) { 769 auto it = s.upper_bound(prv); 770 if (it != s.end() && (*it < a[i])) { 771 ok = false; 772 break; 773 } 774 } 775 if (prv > a[i]) { 776 auto it = s.lower_bound(prv); 777 if (it != s.begin() && (*(--it) > a[i])) { 778 ok = false; 779 break; 780 } 781 } 782 } 783 s.insert(a[i]); 784 } 785 if (ok) cout << "YES\n"; 786 else cout << "NO\n"; 787 } 788 return 0; 789 } 790 ``` 791 792 **Implementation in Haskell by Tlatoani** 793 794 ``` 795 import Data.List (intercalate) 796 import Data.Set (singleton, lookupLT, lookupGT, insert) 797 import Control.Monad (mapM, replicateM) 798 799 main = do t <- read <$> getLine 800 replicateM t solve 801 802 solve = do getLine 803 xs <- (map read . words) <$> getLine 804 putStrLn (if isOmkArray xs then "yEs" else "nO") 805 806 isOmkArray :: [Int] -> Bool 807 isOmkArray (x:xs) = helper xs x (singleton x) 808 where helper [] _ _ = True 809 helper (x:xs) prev allPrev | maybe False (x <) (lookupLT prev allPrev) || maybe False (x >) (lookupGT prev allPrev) = False 810 | otherwise = helper xs x (insert x allPrev) 811 ``` 812 813 # [1536E - Omkar and Forest](/contest/1536/problem/E "Codeforces Round 724 (Div. 2)") 814 815 Idea: [gotexans](/profile/gotexans "Master gotexans") 816 817 Preparation: [gotexans](/profile/gotexans "Master gotexans") 818 819 [Video editorial](https://www.youtube.com/watch?v=cqzBCjXIUwA) 820 821 **Hint 1** 822 823 Consider forcing some set of ‘#’ positions to be $0$ and the rest to be positive integers. 824 825 **Hint 2** 826 827 Multisource BFS 828 829 **Solution** 830 831 Imagine picking some subset of ‘#’ and making them $0$. Then there is exactly one way to make all the remaining ‘#’ positive integers. To see why, imagine multisource BFS with all $0$ as the sources. After the BFS, each ‘#’ will be equal to the minimum distance from itself to any $0$ cell. Difference between adjacent cells will be at most $1$. Proof can be shown by contradiction: if two cells with difference $\geq 2$ existed, then the larger of these cells is not labeled with the shortest distance to a source (since the distance from the smaller cell $+ 1$ will be a better choice). Because of the nature of BFS, we can also ensure the second condition is also satisfied, since the only cells that have no neighbor strictly smaller will be the source cells. This is the only valid assignment because if we make any number larger, there will exist a pair of cells with difference $\geq 2$. If we try to make any number smaller, there will exist a cell with positive karma that has no strictly smaller neighbor. 832 833 If we let $k$ equal to the frequency of ‘#’ in the input, then the answer is $2^k$. Keep in mind of the special case where the input is all ‘#’, in which case you have to subtract $1$. This is because a possible arrangement must contain at least one cell with karma of $0$. 834 835 Obviously the solution runs in $O(nm)$ time. 836 837 **Implementation in Java by hu_tao** 838 839 ``` 840 //Model Solution 2, uses fast expo 841 import static java.lang.Math.max; 842 import static java.lang.Math.min; 843 import static java.lang.Math.abs; 844 import static java.lang.System.out; 845 import java.util.*; 846 import java.io.*; 847 import java.math.*; 848 849 public class OmkarAndForestModel2 850 { 851 static final long MOD = 1000000007L; 852 public static void main(String hi[]) throws Exception 853 { 854 BufferedReader infile = new BufferedReader(new InputStreamReader(System.in)); 855 StringTokenizer st = new StringTokenizer(infile.readLine()); 856 int T = Integer.parseInt(st.nextToken()); 857 StringBuilder sb = new StringBuilder(); 858 while(T-->0) 859 { 860 st = new StringTokenizer(infile.readLine()); 861 int N = Integer.parseInt(st.nextToken()); 862 int M = Integer.parseInt(st.nextToken()); 863 int cnt = 0; 864 for(int i=0; i < N; i++) 865 { 866 String row = infile.readLine(); 867 for(char c: row.toCharArray()) 868 if(c == '#') 869 cnt++; 870 } 871 long res = power(2, cnt, MOD); 872 if(cnt == N*M) 873 res = (res-1+MOD)%MOD; 874 sb.append(res+"\n"); 875 } 876 System.out.print(sb); 877 } 878 public static long power(long x, long y, long p) 879 { 880 //0^0 = 1 881 long res = 1L; 882 x = x%p; 883 while(y > 0) 884 { 885 if((y&1)==1) 886 res = (res*x)%p; 887 y >>= 1; 888 x = (x*x)%p; 889 } 890 return res; 891 } 892 } 893 ``` 894 895 **Implementation in Kotlin by Tlatoani** 896 897 ``` 898 const val MOD = 1000000007L 899 900 fun main() { 901 for (c in 1..readLine()!!.toInt()) { 902 val (n, m) = readLine()!!.split(" ").map { it.toInt() } 903 var zeros = (1..n).sumBy{ readLine()!!.count { it == '0' } } 904 var answer = 1L 905 for (j in 1..(n * m) - zeros) { 906 answer *= 2L 907 answer %= MOD 908 } 909 if (zeros == 0) { 910 answer-- 911 } 912 println(answer) 913 } 914 } 915 ``` 916 917 **Implementation in C++ by kefaa2** 918 919 ``` 920 #ifdef DEBUG 921 #define _GLIBCXX_DEBUG 922 #endif 923 #pragma GCC optimize("O3") 924 #include <bits/stdc++.h> 925 926 using namespace std; 927 typedef long double ld; 928 typedef long long ll; 929 const int mod = (int)1e9 + 7; 930 int main() { 931 ios_base::sync_with_stdio(false); 932 cin.tie(nullptr); 933 // freopen("input.txt", "r", stdin); 934 int tst; 935 cin >> tst; 936 while (tst--) { 937 int n, m; 938 cin >> n >> m; 939 int ans = 1; 940 bool has =false; 941 for (int i = 0; i < n; i++) { 942 for (int j = 0; j < m; j++) { 943 char c; 944 cin >> c; 945 if (c == '0') { 946 has = true; 947 } 948 else { 949 ans = (2LL * ans) % mod; 950 } 951 } 952 } 953 if (has) { 954 cout << ans << '\n'; 955 } 956 else { 957 cout << (ans - 1) << '\n'; 958 } 959 } 960 return 0; 961 } 962 ``` 963 964 **Implementation in Haskell by Tlatoani** 965 966 ``` 967 import Data.List (intercalate) 968 import Control.Monad (replicateM) 969 970 md x = mod x 1000000007 971 972 main = do t <- read <$> getLine 973 replicateM t solve 974 975 solve = do n:m:[] <- (map read . words) <$> getLine 976 free <- (sum . map (sum . map (\chara -> if chara == '#' then 1 else 0))) <$> replicateM n getLine 977 putStrLn $ show (if free == n * m then pow 2 free - 1 else pow 2 free) 978 979 pow :: (Integral a) => Integer -> a -> Integer 980 pow _ 0 = 1 981 pow x y = md $ x * (pow x (y - 1)) 982 ``` 983 984 # [1536F - Omkar and Akmar](/contest/1536/problem/F "Codeforces Round 724 (Div. 2)") 985 986 Idea: [malachi_toney_goat](/profile/malachi_toney_goat "Master malachi_toney_goat") 987 988 Preparation: [malachi_toney_goat](/profile/malachi_toney_goat "Master malachi_toney_goat") 989 990 [Video editorial](https://www.youtube.com/watch?v=iTou7R_fJfY) 991 992 **Hint 1** 993 994 Solve a simpler version of the problem, where you just need to print who would win if both players play optimally. 995 996 **Hint 1 Hint** 997 998 Consider the possible ending states of the board. 999 1000 **Hint 1 Solution** 1001 1002 The 2nd player, Omkar, always wins no matter what either player does. The easiest way to see this is by considering ending states of the board. An ending state with an even number of letters means that the 2nd player wins (because the first player is the next player and there are no more moves), and an ending state with an odd number of letters means that the 1st player wins. 1003 1004 An ending state must be in the form ABABA... or BABA..., where there are 0 or 1 empty cells in between each letter and the letters form an alternating pattern. If there is more than 1 empty cell in between two cells, then a player will be able to play a letter, thus it is not a valid ending state. 1005 1006 If an ending state has two of the same letters next to each other, then it is not a valid ending state. Either they are next to each other, which is illegal, or there is at least one empty cell in between them, which means that a player can play the other letter in between. 1007 1008 Since the ending state must form an alternating pattern, there must be an even number of states. Thus, the 2nd player, Omkar, always wins. 1009 1010 **Hint 2** 1011 1012 Find the implication of the 2nd player always winning on the number of optimal games. 1013 1014 **Hint 2 Solution** 1015 1016 Because the 2nd player always wins no matter what, the number of optimal games basically means the total number of possible games. 1017 1018 **Solution** 1019 1020 Because of Hint 1 and Hint 2, we want to find the total number of possible games. This can be done by iterating over the number of moves and counting the number of ways to play a game with that number of moves. 1021 1022 We want to find the number of games that end in $x$ moves on a board of size $n$. 1023 1024 The first step is to calculate the total number of ending states. If $x=n$, the total number of ending states is just $2$ because you can either have ABABA... or BABAB... 1025 1026 Otherwise, a game that ends in $x$ moves will consist of $x$ letters, for example A|B|A|B|... where a | is a possible location of a single empty cell (there cannot be multiple empty cells next to each other or else it would not be a valid ending state). There are $x$ possible places where there can be an empty cell, and $n-x$ empty cells, so there are $\binom x {n-x}$ ways to choose places to put empty cells. Due to the circular nature of the board, you need to account for the case where the first cell on the board is an empty cell (the previous formula only works if the first cell is not empty). If you set the first cell to be empty, there are not $x-1$ possible places to put an empty cell and $n-x-1$ remaining empty cells, so you have to add $\binom {x-1} {n-x-1}$. Multiply the answer by $2$ to account for starting with an A or B. 1027 1028 Finally, multiply by $x!$ to account for all the ways you can reach each ending configuration. 1029 1030 Thus, if $x=n$, there are $2 \cdot x!$ optimal games, otherwise there are $2 \cdot (\binom x {n-x} + \binom {x-1} {n-x-1} ) \cdot x!$ optimal games. 1031 1032 Add up the number of games that end in $x$ moves for all even $x$ from $\lceil \frac{n}{2} \rceil$ to $n$, inclusive. Thus, the solution is $O(n)$. 1033 1034 **Implementation in Java by golions** 1035 1036 ``` 1037 //make sure to make new file! 1038 import java.io.*; 1039 import java.util.*; 1040 1041 public class OmkarAndAkmarSolution{ 1042 1043 public static int MAXN = 1000005; 1044 public static long MOD = 1000000007L; 1045 public static long[] fac; 1046 public static long[] ifac; 1047 1048 public static void main(String[] args)throws IOException{ 1049 BufferedReader f = new BufferedReader(new InputStreamReader(System.in)); 1050 PrintWriter out = new PrintWriter(System.out); 1051 1052 int n = Integer.parseInt(f.readLine()); 1053 1054 fac = new long[MAXN]; 1055 ifac = new long[MAXN]; 1056 1057 fac[0] = 1L; 1058 ifac[0] = 1L; 1059 for(int k = 1; k < MAXN; k++){ 1060 fac[k] = (fac[k-1] * (long)k + MOD)%MOD; 1061 ifac[k] = modInverse(fac[k],MOD); 1062 } 1063 1064 /* 1065 ifac[MAXN-1] = modInverse(fac[MAXN-1],MOD); 1066 for(int k = MAXN-2; k >= 0; k--){ 1067 ifac[k] = (ifac[k+1]*(long)(k+1) + MOD)%MOD; 1068 }*/ 1069 1070 int start = (n+1)/2; 1071 if(start % 2 == 1) start++; 1072 1073 long answer = 0L; 1074 for(int k = start; k <= n; k+=2){ 1075 long prod1 = 1L; 1076 if(n-k>=1){ 1077 //doesn't do first skip 1078 prod1 = choose(k,n-k); 1079 //does first skip 1080 prod1 = (prod1 + choose(k-1,n-k-1) + MOD)%MOD; 1081 } 1082 long prod2 = (prod1*2L + MOD)%MOD; 1083 long prod3 = (prod2*fac[k] + MOD)%MOD; 1084 answer = (answer + prod3 + MOD)%MOD; 1085 } 1086 1087 out.println(answer); 1088 1089 1090 1091 1092 1093 1094 1095 1096 out.close(); 1097 } 1098 1099 //a choose b, a!/(b!(a-b)!) 1100 public static long choose(int a, int b){ 1101 long prod = (fac[a]*ifac[b] + MOD)%MOD; 1102 long prod2 = (prod*ifac[a-b] + MOD)%MOD; 1103 return prod2; 1104 } 1105 1106 public static long modInverse(long a, long m) 1107 { 1108 long m0 = m; 1109 long y = 0; 1110 long x = 1; 1111 if (m == 1) 1112 return 0; 1113 1114 while (a > 1) { 1115 // q is quotient 1116 long q = a / m; 1117 1118 long t = m; 1119 1120 // m is remainder now, process 1121 // same as Euclid's algo 1122 m = a % m; 1123 a = t; 1124 t = y; 1125 1126 // Update x and y 1127 y = x - q * y; 1128 x = t; 1129 } 1130 1131 // Make x positive 1132 if (x < 0) 1133 x += m0; 1134 1135 return x; 1136 } 1137 1138 1139 } 1140 ``` 1141 1142 **Implementation in Kotlin by Tlatoani** 1143 1144 ``` 1145 const val MOD = 1000000007L 1146 1147 fun main() { 1148 val n = readLine()!!.toInt() 1149 val factorial = LongArray(n + 1) 1150 factorial[0] = 1L 1151 for (j in 1..n) { 1152 factorial[j] = (j.toLong() * factorial[j - 1]) % MOD 1153 } 1154 val invFactorial = LongArray(n + 1) 1155 invFactorial[n] = factorial[n] pow -1 1156 for (j in n - 1 downTo 0) { 1157 invFactorial[j] = ((j + 1).toLong() * invFactorial[j + 1]) % MOD 1158 } 1159 fun choose(a: Int, b: Int) = if (b in 0..a) ((factorial[a] * ((invFactorial[b] * invFactorial[a - b]) % MOD)) % MOD) else 0L 1160 var answer = 0L 1161 for (k in 0..n step 2) { 1162 answer += factorial[k] * (choose(k, n - k) + choose(k - 1, n - k - 1)) 1163 answer %= MOD 1164 } 1165 answer *= 2L 1166 answer %= MOD 1167 println(answer) 1168 } 1169 1170 const val MOD_TOTIENT = MOD.toInt() - 1 1171 1172 infix fun Long.pow(power: Int): Long { 1173 var e = power 1174 e %= MOD_TOTIENT 1175 if (e < 0) { 1176 e += MOD_TOTIENT 1177 } 1178 if (e == 0 && this == 0L) { 1179 return this 1180 } 1181 var b = this % MOD 1182 var res = 1L 1183 while (e > 0) { 1184 if (e and 1 != 0) { 1185 res *= b 1186 res %= MOD 1187 } 1188 b *= b 1189 b %= MOD 1190 e = e shr 1 1191 } 1192 return res 1193 } 1194 ``` 1195 1196 **Implementation in C++ by kefaa2** 1197 1198 ``` 1199 #ifdef DEBUG 1200 #define _GLIBCXX_DEBUG 1201 #endif 1202 #pragma GCC optimize("O3") 1203 #include <bits/stdc++.h> 1204 1205 using namespace std; 1206 typedef long double ld; 1207 typedef long long ll; 1208 const int mod = (int)1e9 + 7; 1209 int mult(int a, int b) { 1210 return (1LL * a * b) % mod; 1211 } 1212 int sum(int a, int b) { 1213 int s = a + b; 1214 if (s >= mod) s -= mod; 1215 return s; 1216 } 1217 const int maxN = 2e6 + 10; 1218 int inv[maxN], fact[maxN], invfact[maxN]; 1219 int cnk(int n, int k) { 1220 if (n < k || k < 0) return 0; 1221 return mult(fact[n], mult(invfact[k], invfact[n - k])); 1222 } 1223 int main() { 1224 ios_base::sync_with_stdio(false); 1225 cin.tie(nullptr); 1226 // freopen("input.txt", "r", stdin); 1227 inv[1] = 1; 1228 fact[0] = invfact[0] = fact[1] = invfact[1] = 1; 1229 for (int i = 2; i < maxN; i++) { 1230 inv[i] = mult(inv[mod % i], mod - mod / i); 1231 fact[i] = mult(fact[i - 1], i); 1232 invfact[i] = mult(invfact[i - 1], inv[i]); 1233 } 1234 int ans = 0; 1235 int n; 1236 cin >> n; 1237 for (int moves = 0; moves <= n - 1; moves++) { 1238 int spaces = n - 1 - moves; 1239 int coef = cnk(moves + 1, spaces); 1240 if (moves % 2 == 0) continue; 1241 int fi = (moves + 1) / 2; 1242 coef = mult(coef, fact[moves]); 1243 // cout << coef << endl; 1244 ans = sum(ans, coef); 1245 } 1246 ans = mult(ans, 2 * n); 1247 cout << ans; 1248 return 0; 1249 } 1250 ``` 1251 1252 **Implementation in Haskell by Tlatoani** 1253 1254 ``` 1255 import Data.List (reverse) 1256 import Data.Array (listArray, (!)) 1257 1258 chara = 1000000007 1259 md x = mod x chara 1260 1261 main = do n <- read <$> getLine 1262 putStrLn $ show (solve n) 1263 1264 solve n = md $ 2 * (sum (map (\k -> md (factorials!k * (choose k (n - k) + choose (k - 1) (n - k - 1)))) [0,2..n])) 1265 where factorials = listArray (0, n) (reverse (helper n)) 1266 where helper 0 = 1:[] 1267 helper n' = md (n' * f):fs 1268 where fs@(f:_) = helper (n' - 1) 1269 invFactorials = listArray (0, n) (helper 0) 1270 where helper n' | n' == n = inv (factorials!n):[] 1271 | otherwise = md ((n' + 1) * f):fs 1272 where fs@(f:_) = helper (n' + 1) 1273 choose a b | 0 <= b && b <= a = md $ factorials!a * (md (invFactorials!b * invFactorials!(a - b))) 1274 | otherwise = 0 1275 1276 modPow :: (Integral a) => Integer -> a -> Integer 1277 modPow _ 0 = 1 1278 modPow x y = md $ (if even y then 1 else x) * modPow (md (x * x)) (div y 2) 1279 1280 inv x = modPow x (chara - 2) 1281 ```