1742F.md (3519B)
1 Source: https://codeforces.com/problemset/problem/1742/F 2 3 F. Smaller 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Alperen has two strings, $s$ and $t$ which are both initially equal to "a". 22 23 He will perform $q$ operations of two types on the given strings: 24 25 * $1 \;\; k \;\; x$ — Append the string $x$ exactly $k$ times at the end of string $s$. In other words, $s := s + \underbrace{x + \dots + x}_{k \text{ times}}$. 26 * $2 \;\; k \;\; x$ — Append the string $x$ exactly $k$ times at the end of string $t$. In other words, $t := t + \underbrace{x + \dots + x}_{k \text{ times}}$. 27 28 After each operation, determine if it is possible to rearrange the characters of $s$ and $t$ such that $s$ is lexicographically smaller$^{\dagger}$ than $t$. 29 30 Note that the strings change after performing each operation and don't go back to their initial states. 31 32 $^{\dagger}$ Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. A formal definition is as follows: string $p$ is lexicographically smaller than string $q$ if there exists a position $i$ such that $p_i \lt q_i$, and for all $j \lt i$, $p_j = q_j$. If no such $i$ exists, then $p$ is lexicographically smaller than $q$ if the length of $p$ is less than the length of $q$. For example, $\texttt{abdc} \lt \texttt{abe}$ and $\texttt{abc} \lt \texttt{abcd}$, where we write $p \lt q$ if $p$ is lexicographically smaller than $q$. 33 34 Input 35 36 The first line of the input contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 37 38 The first line of each test case contains an integer $q$ $(1 \leq q \leq 10^5)$ — the number of operations Alperen will perform. 39 40 Then $q$ lines follow, each containing two positive integers $d$ and $k$ ($1 \leq d \leq 2$; $1 \leq k \leq 10^5$) and a non-empty string $x$ consisting of lowercase English letters — the type of the operation, the number of times we will append string $x$ and the string we need to append respectively. 41 42 It is guaranteed that the sum of $q$ over all test cases doesn't exceed $10^5$ and that the sum of lengths of all strings $x$ in the input doesn't exceed $5 \cdot 10^5$. 43 44 Output 45 46 For each operation, output "YES", if it is possible to arrange the elements in both strings in such a way that $s$ is lexicographically smaller than $t$ and "NO" otherwise. 47 48 Example 49 50 Input 51 52 ``` 53 3 54 55 5 56 57 2 1 aa 58 59 1 2 a 60 61 2 3 a 62 63 1 2 b 64 65 2 3 abca 66 67 2 68 69 1 5 mihai 70 71 2 2 buiucani 72 73 3 74 75 1 5 b 76 77 2 3 a 78 79 2 4 paiu 80 ``` 81 82 Output 83 84 ``` 85 YES 86 NO 87 YES 88 NO 89 YES 90 NO 91 YES 92 NO 93 NO 94 YES 95 ``` 96 97 Note 98 99 In the first test case, the strings are initially $s = $ "a" and $t = $ "a". 100 101 After the first operation the string $t$ becomes "aaa". Since "a" is already lexicographically smaller than "aaa", the answer for this operation should be "YES". 102 103 After the second operation string $s$ becomes "aaa", and since $t$ is also equal to "aaa", we can't arrange $s$ in any way such that it is lexicographically smaller than $t$, so the answer is "NO". 104 105 After the third operation string $t$ becomes "aaaaaa" and $s$ is already lexicographically smaller than it so the answer is "YES". 106 107 After the fourth operation $s$ becomes "aaabb" and there is no way to make it lexicographically smaller than "aaaaaa" so the answer is "NO". 108 109 After the fifth operation the string $t$ becomes "aaaaaaabcaabcaabca", and we can rearrange the strings to: "bbaaa" and "caaaaaabcaabcaabaa" so that $s$ is lexicographically smaller than $t$, so we should answer "YES".