To make the arithmetic mean be equal to exactly $$$1$$$ the sum needs to be equal to the number of elements in the array.
Let's consider $$$3$$$ cases for this problem:
1) The sum of the array equals $$$n$$$: Here the answer is $$$0$$$ since the arithmetic mean of the array is initially $$$1$$$.
2) The sum of the array is smaller than $$$n$$$: The answer is always $$$1$$$ since we can add a single integer $$$k$$$ such that $$$sum + k = n + 1$$$ is satisfied and more specifically $$$k = n - sum + 1$$$.
3) The sum of the array is greater than $$$n$$$: If we add any number apart from $$$0$$$ will add to the sum more or equal than to the number of elements. The number of $$$0$$$'s to add can be found by a loop of adding $$$0$$$'s until the number of elements is equal to the sum or by the simple formula of $$$sum-n$$$.
#include "bits/stdc++.h"
using namespace std;
int main()
{
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int sum = 0;
for (int i = 0;i < n; i++){
int a;
cin >> a;
sum += a;
}
if(sum < n)cout << "1\n";
else cout << sum - n << "\n";
}
}
#include "bits/stdc++.h"
using namespace std;
int main()
{
int t;
cin >> t;
while(t--){
int n, m, i, j;
cin >> n >> m >> i >> j;
cout << 1 << " " << 1 << " " << n << " " << m << "\n";
}
}
#include "bits/stdc++.h"
using namespace std;
int main()
{
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<int> h(n);
for (int i = 0;i < n; i++){
cin >> h[i];
}
sort(h.begin(), h.end());
if(n == 2){
cout << h[0] << " " << h[1] << "\n";
continue;
}
int pos = -1, mn = INT_MAX;
for (int i = 1;i < n; i++){
if(mn > abs(h[i] - h[i - 1])){
pos = i;
mn = abs(h[i] - h[i - 1]);
}
}
for (int i = pos;i < n; i++){
cout << h[i] << " ";
}
for(int i = 0;i < pos; i++){
cout << h[i] << " ";
}
cout << "\n";
}
}
#include "bits/stdc++.h"
using namespace std;
int main()
{
int t;
cin >> t;
while(t--){
int n;
cin >> n;
if(n % 2 == 1){
cout << "Bob\n";
continue;
}
int cnt = 0;
while(n % 2 == 0){
cnt++;
n /= 2;
}
if(n > 1){
cout << "Alice\n";
}else if(cnt % 2 == 0){
cout << "Alice\n";
}else cout << "Bob\n";
}
}
1537E1 - Erase and Extend (Easy Version)
#include "bits/stdc++.h"
using namespace std;
string get(string s, int k){
while((int)s.size() < k){
s = s + s;
}
while((int)s.size() > k)
s.pop_back();
return s;
}
int main()
{
int n, k;
string s;
cin >> n >> k;
cin >> s;
string pref = "";
pref += s[0];
string mn = get(pref, k);
for(int i = 1;i < n;i++){
if(s[i] > s[0])break;
pref += s[i];
mn = min(mn, get(pref, k));
}
cout << mn << "\n";
}
1537E2 - Erase and Extend (Hard Version)
We know that the final string is some prefix repeated a bunch of times. Incrementally for $$$i$$$ from $$$1$$$ to $$$n$$$ we will keep the longest among the first $$$i$$$ prefixes that gives the best answer we've seen so far.
So assume the $$$m-th$$$ prefix is currently the best and we're considering position $$$p$$$. If the $$$p-th$$$ character is greater than the corresponding character in $$$s_{1..m} \cdot (a lot)$$$ then the $$$p-th$$$ prefix and any further prefixes can't possibly give a smaller answer, so we just print the current one and finish. Otherwise all the characters before the $$$p-th$$$ are all less than or equal to the corresponding characters in $$$s_1..m \cdot (a lot)$$$, so if the $$$p-th$$$ is smaller than the corresponding we set the $$$p-th$$$ prefix as the best.
Now the interesting case is if the current character is the same as the corresponding one. Say then that $$$p = m + t$$$, by the logic of the previous paragraph we must have $$$s_{(m + 1)..(m + t)} = s_{1..t}$$$. If $$$t = m$$$ then the new prefix is just the old one twice, so set $$$p$$$ as the best prefix now. This ensures that otherwise $$$t < m$$$.
Denote $$$A = s_{1..t}$$$ and $$$B = s_{(t + 1)..m}$$$, so the string formed by the current best prefix is $$$ABABABABA...$$$ and the new one is $$$ABAABAABA...$$$ Now if $$$AB = BA$$$ then these strings are in fact the same, so set $$$m + t$$$ as the new best prefix. Otherwise we can find the first position where $$$AB$$$ and $$$BA$$$ differ, and use that to determine whether the new prefix is better. This can be done in $$$O(1)$$$ with Z function, thus giving a linear solution for the full problem.
Solution by Ari.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string s;
int n, k;
vector<int> z_func(string &s) {
int n = s.size(), L = -1, R = -1;
vector<int> z(n);
z[0] = n;
for(int i = 1; i < n; i++) {
if(i <= R)
z[i] = min(z[i - L], R - i + 1);
while(i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if(i + z[i] - 1 > R) {
L = i;
R = i + z[i] - 1;
}
}
return z;
}
void finish(int m) {
for(int i = 0; i < k; i++)
cout << s[i % m];
cout << '\n';
exit(0);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k >> s;
auto z = z_func(s);
int cur = 1;
for(int i = 1; i < n; i++) {
if(s[i] > s[i % cur])
finish(cur);
if(s[i] < s[i % cur]) {
cur = i + 1;
continue;
}
int off = i - cur + 1;
if(off == cur) {
cur = i + 1;
continue;
}
if(z[off] < cur - off) {
if(cur + off + z[off] >= k) {
cur = i + 1;
continue;
}
if(s[off + z[off]] > s[z[off]])
cur = i + 1;
continue;
}
if(z[cur - off] < off) {
if(2 * cur + z[cur - off] >= k) {
cur = i + 1;
continue;
}
if(s[cur - off + z[cur - off]] < s[z[cur - off]])
cur = i + 1;
continue;
}
cur = i + 1;
}
finish(cur);
}
#include "bits/stdc++.h"
using namespace std;
const int N = 2e5 + 10;
vector<long long> adj[N];
long long s[N], n, m;
bool bipartite()
{
bool bip = true;
for(long long i = 0;i < n;i++)
s[i] = -1;
queue<long long> q;
for(long long i = 0;i < n;i++){
if(s[i] != -1)continue;
q.push(i);
s[i] = 0;
while(!q.empty()){
long long v = q.front();
q.pop();
for(long long u: adj[v]){
if(s[u] == -1){
s[u] = s[v] ^ 1;
q.push(u);
}else bip &= s[u] != s[v];
}
}
}
return bip;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
long long T;
cin >> T;
while(T--)
{
cin >> n >> m;
for(long long i = 0;i < n;i++)
adj[i].clear();
vector<long long> v(n), t(n);
long long p1 = 0, p2 = 0;
for(long long i = 0;i < n; i++){
cin >> v[i];
p1 = (p1 + abs(v[i])) % 2;
}
for (long long i = 0;i < n; i++){
cin >> t[i];
p2 = (p2 + abs(t[i])) % 2;
}
for(long long i = 0;i < m;i++){
long long a, b;
cin >> a >> b;
--a, --b;
adj[a].push_back(b);
adj[b].push_back(a);
}
if(p1 != p2){
cout << "NO\n";
continue;
}
if(bipartite() == false){
cout << "YES\n";
}else{
vector<long long> c(2, 0);
for(int i = 0;i < n;i++){
c[s[i]] += v[i] - t[i];
}
if(c[0] == c[1]){
cout << "YES\n";
}else cout << "NO\n";
}
}
}