A small confessionHi, this is the first time I write such a blog like this. All is because of my excitement that for the first time I can solve all problems, not because I am worshiping myself or something. I know this is just a Div-3 contest, so there are many people who can solve it. But if you are stuck with some problems, feel free to read my solutions.
This is not an official editorial, so the solutions might not be the best of all solutions out there, so if you have something to discuss, feel free to leave something below. Thanks for all.
The first two numbers cannot be produced by a sum operation, so we have $$$2$$$ of $$$3$$$ numbers we must find. How to find the last one? Subtract these two from the largest one.
Implentationvector<ll> a(7);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
ll ttl = a[6];
cout << a[0] << ' ' << a[1] << ' ' << a[6] - a[0] - a[1] << '\n';
We need to create an empty answer string.
Starting from the first substring, for each substring follows, if the first character of it equals the last character of the currently answer string, add the last character, otherwise, append the whole string.
In the end, check if the answer string has the length n or not. If not, repeat the last character.
Be careful of the case we didn't add any whole substring.
Implentationll n;
cin >> n;
string s = "";
ll h = 0;
FOR(i, 0, n - 3)
{
string t;
cin >> t;
if (s.empty() || t[0] != s.back())
{
s += t;
h = 1;
}
else s += t[1];
}
if (!h) s += 'a';
while(s.length() < a) s += s.back();
cout << s << '\n';
The most likely answer for each case is the gcd of all odd-indexed elements or the gcd of all even-indexed elements.
Our work now is to check if it is divisible by some "neighbor index" or not.
Implentationll n;
cin >> n;
vector<ll> C(a);
for (auto &x: C) cin >> x;
ll g = 0;
for (ll i = 0; i < a; i += 2)
{
g = gcd(g, C[i]);
}
for (ll i = 1; i < a; i += 2)
{
ll t = gcd(g, C[i]);
if (t == g) g = 1;
}
if (g != 1)
{
cout << g << '\n';
return;
}
g = 0;
for (ll i = 1; i < a; i += 2)
{
g = gcd(g, C[i]);
}
for (ll i = 0; i < a; i += 2)
{
ll t = gcd(g, C[i]);
if (t == g) g = 1;
}
if (g != 1) cout << g << '\n';
else cout << 0 << '\n';
We need three to optimize two things: the numbers we use in $$$k$$$ operations must be as large as possible, and the total result of $$$k$$$ operations must be as small as possible.
Thus, we will use $$$2k$$$ largest numbers.
Implentationll a, k;
cin >> a >> k;
vector<ll> C(a);
for (auto &x : C) cin >> x;
REVERSE_SORT(C);
ll ttl = 0;
FOR(i, 0, k - 1)
{
ttl += C[i + k] / C[i];
}
FOR(i, k * 2, a - 1) ttl += C[i];
cout << ttl << '\n';
We have a system of equations, it goes like this:
If we add all of them, we will have something like:
Moreover, if we subtract two neighbor equations, for example, the first from the second equation, we will get something like this:
Using this we can calculate all numbers from $$$a_1$$$ to $$$a_n$$$. Of course, we will have to check the exceptions: $$$n*(n+1)/2$$$ is not divisible from the sum of all elements from $$$b$$$, or some $$$b[i]$$$ is non-positive.
Implentationll n;
cin >> n;
vector<ll> b(n);
for (auto &x : b) cin >> x;
ll ttl = 0;
FOR(i, 0, n - 1)
{
ttl += b[i];
}
ll k = n * (n + 1) / 2;
if (ttl % k != 0)
{
cout << "NO" << '\n';
return;
}
ttl /= k;
vector<ll> ans(n, 0);
FOR(i, 0, n - 1)
{
ll x = (i + n - 1) % n;
ans[i] = (ttl + b[x] - b[i]) / n;
if (ttl + b[x] < b[i])
{
cout << "NO" << '\n';
return;
}
if ((ttl + b[x] - b[i]) % n != 0)
{
cout << "NO" << '\n';
return;
}
if (ans[i] == 0)
{
cout << "NO" << '\n';
return;
}
}
cout << "YES" << '\n';
printVector(ans);
cout << '\n';
if $$$x = y$$$, the answer is YES.
else if $$$y$$$ is divisible by $$$2$$$, the answer is NO.
else we have to check if the binary string $$$s$$$ of $$$x$$$ can convert into the binary string $$$t$$$ of $$$y$$$ or not, with $$$s$$$ we can convert into several "starting strings":
Itself.
Itself, with one extra '1' at the end.
Itself but erase all '0's at the end.
Itself, erase all '0's, reversed.
Clearly, the operation is to choose to keep the string or erase all the '0's at the end then add some '1's (maybe zero) to the beginning or the end of the string.
The work now is to check each case if we can obtain $$$t$$$ by adding '1's to the beginning or the end of the current string.
Implentationll x, y;
cin >> x >> y;
if (x == y)
{
cout << "YES" << '\n';
return;
}
if (y % 2 == 0)
{
cout << "NO" << '\n';
return;
}
function<string(ll)> convert = [&](ll a)
{
string s = "";
ll n = 1;
while (a)
{
if (a & n) s += '1';
else s += '0';
if (a & n) a ^= n;
n <<= 1;
}
revrs(s);
return s;
}
string s = convert(x);
string t = convert(y);
function<bool(ll, ll)> check = [&](ll m, ll n)
{
FOR(i, m, n) if (t[i] == '0') return false;
return true;
};
function<void()> extract = [&]()
{
ll len = s.length();
FOR(i, 0, t.length() - 1)
{
if (i + len > t.length()) break;
if (t.substr(i, len) == s)
{
if (!check(0, i - 1) || !check(i + len, t.length() - 1)) continue;
cout << "YES" << '\n';
exit(0);
}
}
if (s.back() == '0') return;
revrs(s);
FOR(i, 0, t.length() - 1)
{
if (i + len > t.length()) break;
if (t.substr(i, len) == s)
{
if (!check(0, i - 1) || !check(i + len, t.length() - 1)) continue;
cout << "YES" << '\n';
exit(0);
}
}
revrs(s);
};
s = s + '1';
extract();
s.pop_back();
extract();
while (!s.empty() && s.back() == '0')
{
s.pop_back();
}
if (!s.empty()) extract();
cout << "NO" << '\n';
A simple way to solve: use two sets, both store vectors of four elements: the leftmost index of the segment, the rightmost index of the segment, how many numbers we take from it, and the distance between it and the next segment on the array. The first set will sort by the distance, the second set will sort by their first elements.
So how to use them? At first, merge the two arrays a and b into 1 array, let's call it TTL, use a map to save if we are currently have something or not. Then for each element, we will make a segment based on them: the leftmost and rightmost is their index, the number of elements we will take is either 1 or 0 depending on the map I described above, the distance will be the difference between it and the next number in TTL.
What will we do now? Solve the problem offline, for each query merge some of the segments which have the smallest "distance" into some other segments, so there will be no more than N merges. Since we are using sets, the complexity is O(NlogN).
To calculate the sum efficiently, use a prefix array.
Implentationll a, b, q;
cin >> a >> b >> q;
vec(ll) ttl;
map<ll, ll> C, first, last;
ll cnt = 0;
FOR(i, 0, a - 1)
{
ll x;
cin >> x;
cnt += x;
ttl.pb(x);
C[x]++;
}
FOR(i, 0, b - 1)
{
ll x;
cin >> x;
ttl.pb(x);
}
SORT(ttl);
FOR(i, 0, ttl.size() - 1) last[ttl[i]] = i;
FORD(i, ttl.size() - 1, 0) first[ttl[i]] = i;
vector<ll> PREF = ttl;
FOR(i, 1, PREF.size() - 1) PREF[i] += PREF[i - 1];
set<vector<ll> > SORT_BY_DIST; // DIST -> TAKEN_ELEMENTS -> LAST_ELE -> FIRST_ELE
set<vector<ll> > SORT_BY_FIRST_ELEMENT; // FIRST_ELE -> LAST_ELE -> TAKEN_ELEMENTS -> DIST
FOR(i, 0, ttl.size() - 2)
{
if (ttl[i] == ttl[i + 1]) continue;
ll x = ttl[i];
SORT_BY_DIST.insert({ttl[i + 1] - ttl[i], C[x], last[x], first[x]});
SORT_BY_FIRST_ELEMENT.insert({first[x], last[x], C[x], ttl[i + 1] - ttl[i]});
}
SORT_BY_DIST.insert({(ll)1e18, C[ttl.back()], last[ttl.back()], first[ttl.back()]});
SORT_BY_FIRST_ELEMENT.insert({first[ttl.back()], last[ttl.back()], C[ttl.back()], (ll)1e18});
vec(ll) ans(q);
vector<p<ll, ll> > QUERIES(q);
FOR(i, 0, q - 1)
{
cin >> QUERIES[i].f;
QUERIES[i].s = i;
}
SORT(QUERIES);
function<ll(ll, ll)> SUB = [&](ll LAST, ll TAKEN)
{
ll l = LAST - TAKEN;
ll tmp = 0;
if (l == -1)
{
tmp += PREF[0];
l = 0;
}
tmp += PREF[LAST] - PREF[l];
return tmp;
};
for (auto x : QUERIES)
{
vector<ll> K = *SORT_BY_DIST.begin();
while (K[0] <= x.f)
{
vector<ll> Q = K;
revrs(Q);
vector<ll> T = *SORT_BY_FIRST_ELEMENT.upper_bound(Q);
vector<ll> P = T;
revrs(P);
SORT_BY_DIST.erase(K);
SORT_BY_DIST.erase(P);
SORT_BY_FIRST_ELEMENT.erase(Q);
SORT_BY_FIRST_ELEMENT.erase(T);
cnt -= SUB(Q[1], Q[2]);
cnt -= SUB(T[1], T[2]);
cnt += SUB(T[1], Q[2] + T[2]);
T[2] = Q[2] + T[2];
T[0] = Q[0];
SORT_BY_FIRST_ELEMENT.insert(T);
revrs(T);
SORT_BY_DIST.insert(T);
K = *SORT_BY_DIST.begin();
}
ans[x.s] = cnt;
}
printVector(ans);
cout << '\n';
Hope that my defines are not difficult to understand.
Yes, I'm a fan of neal_wu.