2241A - Divide and Conquer

Let $$${z_1, z_2, z_3, ..., z_k}$$$ be the values of $$$z$$$ in the operations to transform $$$x$$$ into $$$y$$$. $$$\newline$$$ The resulting x after the operations is: $$$\dfrac{x}{\displaystyle\prod^{k}_{i=1} z_i}$$$

In other words, we have $$$y = \dfrac{x}{\displaystyle\prod^{k}_{i=1} z_i}$$$

Or $$$\displaystyle\prod^{k}_{i=1} z_i = \dfrac{x}{y}$$$.

Since $$$\displaystyle\prod^{k}_{i=1} z_i$$$ is an integer, $$$\dfrac{x}{y}$$$ must also be an integer, so the answer is YES if $$$x$$$ is divisible by $$$y$$$ and NO otherwise

Time complexity: $$$O(1)$$$ per testcase

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;

int t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while(t--) {
    	int a, b;
    	cin >> a >> b;
    	cout << (a % b == 0 ? "YES" : "NO") << endl;
    }
}

2241B - Good times Good times

Before we find the answer, express $$$concat(n, n)$$$ (where concat(x, y) means concatenating $$$x$$$ and $$$y$$$ together) in terms of $$$n$$$

We know that $$$10^{d(n)} + 1$$$ is a good number since it only contains 0 and 1, and $$$concat(n, n)$$$ is a good number since n is a good number, so we need to output $$$10^{d(n)} + 1$$$. We do not need to worry about the bounds since $$$d(n) \le 8$$$

Time complexity: $$$O(d(n))$$$ per testcase

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;

int t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while(t--) {
    	int x;
    	cin >> x;
    	string s = to_string(x);
    	cout << '1';
    	for(int i = 0; i < s.size() - 1; i++) cout << '0';
    	cout << '1' << endl;
    }
}

An alternative solution (that I realized after the contest) is just to output 100000001 in every testcase

Time complexity: $$$O(1)$$$ per testcase

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;

int t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while(t--) {
    	int x;
    	cin >> x;
    	cout << "100000001" << endl;
    }
}

2241C - RemovevomeR

First, let's prove that the answer does not exceed 2

Consider a binary string $$$s$$$ of length $$$n \ge 3$$$.

• If there are 2 consecutive equal characters, they form a palindrome

• Otherwise, $$$s$$$ must be of the form $$$01010101...$$$ or $$$10101010...$$$. Then $$$010$$$ and $$$101$$$ form palindromes.

So we can always decrease the size of a binary string with length at least 3

Now let's see in which cases is the answer equal to 2. $$$\newline$$$ In fact, the answer is equal to 2 when there exists exactly 1 index $$$i$$$ such that $$$1 \le i \le n - 1$$$ and $$$s_i \ne s_{i + 1}$$$

This can be proven by combining consecutive equal characters into blocks.

• If there are exactly 2 blocks, they cannot be combined together, thus resulting in a final length of 2.

• Otherwise, operations can be performed to turn a block into a single character with the corresponding value. The leftover string will have alternating 1s and 0s, so we can keep removing characters until there is only 1 character left.

Time complexity: $$$O(n)$$$ per testcase

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;

int t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while(t--) {
    	int n;
    	string s;
    	cin >> n >> s;
    	int cnt = 0;
    	for(int i = 0; i < n - 1; i++) {
    		if(s[i] != s[i + 1]) cnt++;
    	}
    	if(cnt == 1) cout << 2 << endl;
    	else cout << 1 << endl;
    }
}

2241D - An Alternative Way

There are 2 observations we need to make in this problem:

1. We do not need to care cases where $$$a_i \le b_i$$$ since we can perform an operation where $$$l = r = i$$$ a total of $$$b_i - a_i$$$ times

2. When we want to decrease $$$a_i$$$, we have to increase $$$a_{i - 1}$$$. This leads to the fact that we cannot decrease the first element

From these 2 observations, we can form a strategy as follows:

Traverse the array backwards and for each $$$i$$$ such that $$$2 \le i \le n$$$ and $$$a_i \gt b_i$$$, we decrease $$$a_i$$$ by $$$a_i - b_i$$$ and increase $$$a_{i - 1}$$$ by $$$a_i - b_i$$$ $$$\newline$$$ Finally, if $$$a_1 \le b_1$$$ output YES, otherwise output NO

Time complexity: $$$O(n)$$$ per testcase

Note: For the sake of simplicity, the decrease of $$$a_i$$$ has been omitted in the following implementation

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;

int t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while(t--) {
    	int n;
    	cin >> n;
    	vector<ll> a(n), b(n);
    	for(int i = 0; i < n; i++) cin >> a[i];
    	for(int i = 0; i < n; i++) cin >> b[i];
    	for(int i = n - 1; i > 0; i--) {
    		if(a[i] > b[i]) {
    			a[i - 1] += (a[i] - b[i]);
    		}
    	}
    	if(a[0] > b[0]) cout << "NO" << endl;
    	else cout << "YES" << endl;
    }
}