# Codeforces Edu. Round #102 (Div. 2) [Personal Summary]

ABCDEFG
OOOOØØØ

## A. Replacing Elements

### Description

Time Limit: 2 seconds Memory Limit: 256 megabytes

You have an array $a_1, a_2, \dots, a_n$. All $a_i$ are positive integers.

In one step you can choose three distinct indices $i$, $j$, and $k$ ($i \neq j$; $i \neq k$; $j \neq k$) and assign the sum of $a_j$ and $a_k$ to $a_i$, i. e. make $a_i = a_j + a_k$.

Can you make all $a_i$ lower or equal to $d$ using the operation above any number of times (possibly, zero)?

#### Input

The first line contains a single integer $t$ ($1 \le t \le 2000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $d$ ($3 \le n \le 100$; $1 \le d \le 100$) — the number of elements in the array $a$ and the value $d$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$) — the array $a$.

#### Output

For each test case, print $\texttt{YES}$, if it’s possible to make all elements $a_i$ less or equal than $d$ using the operation above. Otherwise, print $\texttt{NO}$.

You may print each letter in any case (for example, $\texttt{YES}$, $\texttt{Yes}$, $\texttt{yes}$, $\texttt{yEs}$ will all be recognized as positive answer).

#### Example

##### Input
3
5 3
2 3 2 5 4
3 4
2 4 4
5 4
2 1 5 3 6

##### Output
NO
YES
YES


#### Note

In the first test case, we can prove that we can’t make all $a_i \le 3$.

In the second test case, all $a_i$ are already less or equal than $d = 4$.

In the third test case, we can, for example, choose $i = 5$, $j = 1$, $k = 2$ and make $a_5 = a_1 + a_2 = 2 + 1 = 3$. Array $a$ will become $[2, 1, 5, 3, 3]$.

After that we can make $a_3 = a_5 + a_2 = 3 + 1 = 4$. Array will become $[2, 1, 4, 3, 3]$ and all elements are less or equal than $d = 4$.

### Code

  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 119 120 121 122 123 124 125 126 127  /*************************************************************/ #if __cplusplus < 201103L // For jury which unsupports C++11 #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define ffor(_var, _begin, _end, ...) \ for(__typeof__(_end) _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for(__typeof__(_rbegin) _var = _rbegin; _var > _rend; __VA_ARGS__) #define cfor(_var, _cbegin, _cend, ...) \ for(__typeof__(_cend) _var = _cbegin; _var != _cend; __VA_ARGS__) #else #include using namespace std; #define ffor(_var, _begin, _end, ...) \ for(decay::type _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for(decay::type _var = _rbegin; _var > _rend; __VA_ARGS__) #endif typedef long long ll; typedef long double ld; #define ABS(x) ((x) > 0 ? (x) : -(x)) const int INF = 0x3f3f3f3f; // #define __DEBUG__ #ifdef __DEBUG__ #if defined _WIN32 #define _WINDEBUG #include inline std::ostream& __YELLOW__(std::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_GREEN|FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } inline std::ostream& __WHITE__(std::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE); return s; } inline std::ostream& __RED__(std::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } #elif defined __linux__ #define _LINUXDEBUG #define __YELLOW__ "\033[33;1m" #define __WHITE__ "\033[0m" #endif #endif #if defined _WINDEBUG || defined _LINUXDEBUG #define ar2vec(_begin, _end) \ vector::value_type>::type>(_begin, _end) #define debug(x...) \ do { cout << __YELLOW__ << #x << " -> "; err(x); } while(0) void err() { cout << __WHITE__ << endl; } template void err(T a, A... x) { cout << __RED__ << a << __YELLOW__ << ' '; err(x...); } template class T, typename t, typename... A> void err(T a, A... x) { for(auto& v : a) cout << __RED__ << v << __YELLOW__ << ' '; err(x...); } #else #define ar2vec(...) #define debug(...) #endif /*************************************************************/ const int MAXN = 100; int a[MAXN + 10]; int main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("test.in", "r", stdin); // freopen("test.out", "w", stdout); int t = 0; cin >> t; while(t--) { int n = 0, d = 0; cin >> n >> d; for(int i = 1; i <= n; i++) cin >> a[i]; bool flag = true; for(int i = 1; i <= n; i++) if(a[i] > d) { flag = false; break; } if(flag) { cout << "YES" << endl; continue; } sort(a + 1, a + n + 1); if(a[1] + a[2] > d) cout << "NO" << endl; else cout << "YES" << endl; } return 0; } 

## B. String LCM

### Description

Time Limit: 2 seconds Memory Limit: 256 megabytes

Let’s define a multiplication operation between a string $a$ and a positive integer $x$: $a \cdot x$ is the string that is a result of writing $x$ copies of $a$ one after another. For example, “$\texttt{abc}$” $\cdot~2~=$ “$\texttt{abcabc}$”, “$\texttt{a}$” $\cdot~5~=$ “$\texttt{aaaaa}$”.

A string $a$ is divisible by another string $b$ if there exists an integer $x$ such that $b \cdot x = a$. For example, “$\texttt{abababab}$” is divisible by “$\texttt{ab}$”, but is not divisible by “$\texttt{ababab}$” or “$\texttt{aa}$”.

LCM of two strings $s$ and $t$ (defined as $LCM(s, t)$) is the shortest non-empty string that is divisible by both $s$ and $t$.

You are given two strings $s$ and $t$. Find $LCM(s, t)$ or report that it does not exist. It can be shown that if $LCM(s, t)$ exists, it is unique.

#### Input

The first line contains one integer $q$ ($1 \le q \le 2000$) — the number of test cases.

Each test case consists of two lines, containing strings $s$ and $t$ ($1 \le |s|, |t| \le 20$). Each character in each of these strings is either ‘$\texttt{a}$’ or ‘$\texttt{b}$’.

#### Output

For each test case, print $LCM(s, t)$ if it exists; otherwise, print $\texttt{-1}$ . It can be shown that if $LCM(s, t)$ exists, it is unique.

#### Example

##### Input
3
baba
ba
aa
aaa
aba
ab

##### Output
baba
aaaaaa
-1


#### Note

In the first test case, “$\texttt{baba}$” = “$\texttt{baba}$” $\cdot~1~=$ “$\texttt{ba}$” $\cdot~2$.

In the second test case, “$\texttt{aaaaaa}$” = “$\texttt{aa}$” $\cdot~3~=$ “$\texttt{aaa}$” $\cdot~2$.

### Code

  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 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143  /*************************************************************/ #if __cplusplus < 201103L // For jury which unsupports C++11 #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define ffor(_var, _begin, _end, ...) \ for(__typeof__(_end) _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for(__typeof__(_rbegin) _var = _rbegin; _var > _rend; __VA_ARGS__) #define cfor(_var, _cbegin, _cend, ...) \ for(__typeof__(_cend) _var = _cbegin; _var != _cend; __VA_ARGS__) #else #include using namespace std; #define ffor(_var, _begin, _end, ...) \ for(decay::type _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for(decay::type _var = _rbegin; _var > _rend; __VA_ARGS__) #endif typedef long long ll; typedef long double ld; #define ABS(x) ((x) > 0 ? (x) : -(x)) const int INF = 0x3f3f3f3f; // #define __DEBUG__ #ifdef __DEBUG__ #if defined _WIN32 #define _WINDEBUG #include inline std::ostream& __YELLOW__(std::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_GREEN|FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } inline std::ostream& __WHITE__(std::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE); return s; } inline std::ostream& __RED__(std::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } #elif defined __linux__ #define _LINUXDEBUG #define __YELLOW__ "\033[33;1m" #define __WHITE__ "\033[0m" #endif #endif #if defined _WINDEBUG || defined _LINUXDEBUG #define ar2vec(_begin, _end) \ vector::value_type>::type>(_begin, _end) #define debug(x...) \ do { cout << __YELLOW__ << #x << " -> "; err(x); } while(0) void err() { cout << __WHITE__ << endl; } template void err(T a, A... x) { cout << __RED__ << a << __YELLOW__ << ' '; err(x...); } template class T, typename t, typename... A> void err(T a, A... x) { for(auto& v : a) cout << __RED__ << v << __YELLOW__ << ' '; err(x...); } #else #define ar2vec(...) #define debug(...) #endif /*************************************************************/ string getsub(string &s) { int n = s.length(); for(int i = 1; i <= n; i++) { if(n % i) continue; string sub = s.substr(0, i); bool flag = true; for(int j = i; j < n; j += i) { if(sub != s.substr(j, i)) { flag = false; break; } } if(flag) return sub; } return string(""); } int main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("test.in", "r", stdin); // freopen("test.out", "w", stdout); int q = 0; cin >> q; while(q--) { string s, t; cin >> s >> t; string s_sub = getsub(s); string t_sub = getsub(t); debug(s_sub); debug(t_sub); if(s_sub != t_sub) cout << -1 << endl; else { int s_num = s.length() / s_sub.length(); int t_sum = t.length() / t_sub.length(); int lcd = s_num * t_sum / __gcd(s_num, t_sum); debug(s_num, t_sum, lcd); for(int i = 1; i < lcd; i++) s_sub += t_sub; cout << s_sub << endl; } } return 0; } 

## C. No More Inversions

### Description

Time Limit: 2 seconds Memory Limit: 256 megabytes

You have a sequence $a$ with $n$ elements $1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k)$ ($k \le n < 2k$).

Let’s call as inversion in $a$ a pair of indices $i < j$ such that $a[i] > a[j]$.

Suppose, you have some permutation $p$ of size $k$ and you build a sequence $b$ of size $n$ in the following manner: $b[i] = p[a[i]]$.

Your goal is to find such permutation $p$ that the total number of inversions in $b$ doesn’t exceed the total number of inversions in $a$, and $b$ is lexicographically maximum .

Small reminder: the sequence of $k$ integers is called a permutation if it contains all integers from $1$ to $k$ exactly once.

Another small reminder: a sequence $s$ is lexicographically smaller than another sequence $t$, if either $s$ is a prefix of $t$, or for the first $i$ such that $s_i \ne t_i$, $s_i < t_i$ holds (in the first position that these sequences are different, $s$ has smaller number than $t$).

#### Input

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first and only line of each test case contains two integers $n$ and $k$ ($k \le n < 2k$; $1 \le k \le 10^5$) — the length of the sequence $a$ and its maximum.

It’s guaranteed that the total sum of $k$ over test cases doesn’t exceed $10^5$.

#### Output

For each test case, print $k$ integers — the permutation $p$ which maximizes $b$ lexicographically without increasing the total number of inversions.

It can be proven that $p$ exists and is unique.

#### Example

##### Input
4
1 1
2 2
3 2
4 3

##### Output
1
1 2
2 1
1 3 2


#### Note

In the first test case, the sequence $a = [1]$, there is only one permutation $p = [1]$.

In the second test case, the sequence $a = [1, 2]$. There is no inversion in $a$, so there is only one permutation $p = [1, 2]$ which doesn’t increase the number of inversions.

In the third test case, $a = [1, 2, 1]$ and has $1$ inversion. If we use $p = [2, 1]$, then $b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2]$ and also has $1$ inversion.

In the fourth test case, $a = [1, 2, 3, 2]$, and since $p = [1, 3, 2]$ then $b = [1, 3, 2, 3]$. Both $a$ and $b$ have $1$ inversion and $b$ is the lexicographically maximum.

### Code

  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  /*************************************************************/ #if __cplusplus < 201103L // For jury which unsupports C++11 #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define ffor(_var, _begin, _end, ...) \ for(__typeof__(_end) _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for(__typeof__(_rbegin) _var = _rbegin; _var > _rend; __VA_ARGS__) #define cfor(_var, _cbegin, _cend, ...) \ for(__typeof__(_cend) _var = _cbegin; _var != _cend; __VA_ARGS__) #else #include using namespace std; #define ffor(_var, _begin, _end, ...) \ for(decay::type _var = _begin; _var < _end; __VA_ARGS__) #define rfor(_var, _rbegin, _rend, ...) \ for(decay::type _var = _rbegin; _var > _rend; __VA_ARGS__) #endif typedef long long ll; typedef long double ld; #define ABS(x) ((x) > 0 ? (x) : -(x)) const int INF = 0x3f3f3f3f; // #define __DEBUG__ #ifdef __DEBUG__ #if defined _WIN32 #define _WINDEBUG #include inline std::ostream& __YELLOW__(std::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_GREEN|FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } inline std::ostream& __WHITE__(std::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE); return s; } inline std::ostream& __RED__(std::ostream &s) { HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hStdout, FOREGROUND_RED|FOREGROUND_INTENSITY); return s; } #elif defined __linux__ #define _LINUXDEBUG #define __YELLOW__ "\033[33;1m" #define __WHITE__ "\033[0m" #endif #endif #if defined _WINDEBUG || defined _LINUXDEBUG #define ar2vec(_begin, _end) \ vector::value_type>::type>(_begin, _end) #define debug(x...) \ do { cout << __YELLOW__ << #x << " -> "; err(x); } while(0) void err() { cout << __WHITE__ << endl; } template void err(T a, A... x) { cout << __RED__ << a << __YELLOW__ << ' '; err(x...); } template class T, typename t, typename... A> void err(T a, A... x) { for(auto& v : a) cout << __RED__ << v << __YELLOW__ << ' '; err(x...); } #else #define ar2vec(...) #define debug(...) #endif /*************************************************************/ const int MAXN = 1e5; int p[MAXN + 10]; int main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("test.in", "r", stdin); // freopen("test.out", "w", stdout); int t = 0; cin >> t; while(t--) { int n = 0, k = 0; cin >> n >> k; for(int i = 1; i <= 2 * k - n - 1; i++) p[i] = i; for(int i = 2 * k - n, cnt = k; i <= k; i++) p[i] = cnt--; for(int i = 1; i <= k; i++) if(i == k) cout << p[i] << endl; else cout << p[i] << " "; } return 0; } 

## D. Program

### Description

Time Limit: 2 seconds Memory Limit: 256 megabytes

You are given a program that consists of $n$ instructions. Initially a single variable $x$ is assigned to $0$. Afterwards, the instructions are of two types:

• increase $x$ by $1$;
• decrease $x$ by $1$.

You are given $m$ queries of the following format:

• query $l$ $r$ — how many distinct values is $x$ assigned to if all the instructions between the $l$-th one and the $r$-th one inclusive are ignored and the rest are executed without changing the order?

#### Input

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

Then the description of $t$ testcases follows.

The first line of each testcase contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of instructions in the program and the number of queries.

The second line of each testcase contains a program — a string of $n$ characters: each character is either ‘$\texttt{+}$’ or ‘$\texttt{-}$’ — increment and decrement instruction, respectively.

Each of the next $m$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — the description of the query.

The sum of $n$ over all testcases doesn’t exceed $2 \cdot 10^5$. The sum of $m$ over all testcases doesn’t exceed $2 \cdot 10^5$.

#### Output

For each testcase print $m$ integers — for each query $l$, $r$ print the number of distinct values variable $x$ is assigned to if all the instructions between the $l$-th one and the $r$-th one inclusive are ignored and the rest are executed without changing the order.

#### Example

##### Input
2
8 4
-+--+--+
1 8
2 8
2 5
1 1
4 10
+-++
1 1
1 2
2 2
1 3
2 3
3 3
1 4
2 4
3 4
4 4

##### Output
1
2
4
4
3
3
4
2
3
2
1
2
2
2


#### Note

The instructions that remain for each query of the first testcase are:

1. empty program — $x$ was only equal to $0$;
2. “$\texttt{-}$” — $x$ had values $0$ and $-1$;
3. “$\texttt{—+}$” — $x$ had values $0$, $-1$, $-2$, $-3$, $-2$ — there are $4$ distinct values among them;
4. “$\texttt{+–+–+}$” — the distinct values are $1$, $0$, $-1$, $-2$.

### Solution

  1 2 3 4 5 6 7 8 9 10 11  struct Data { int maxx, minn, add; Data(int _max = 0, int _min = 0, int _add = 0): maxx(_max), minn(_min), add(_add) {} Data operator + (const Data &d) { return Data(max(maxx, add + d.maxx), min(minn, add + d.minn), add + d.add); } }; #endif