Idea: AndreyPavlov
Preparation: AndreyPavlov
Editorialist: AndreyPavlov
Note that there are two variants of which numbers to take to make their amount odd: $$$3$$$ odd number; $$$2$$$ even and $$$1$$$ odd. Let’s save all indices of even and odd numbers into two arrays, and check both cases.
def solve():
n = int(input())
a = list(map(int, input().split()))
odd, even = [], []
for i in range(n):
if a[i] % 2 == 0:
even.append(i + 1)
else:
odd.append(i + 1)
if len(odd) >= 1 and len(even) >= 2:
print("YES")
print(odd[0], even[0], even[1])
elif len(odd) >= 3:
print("YES")
print(odd[0], odd[1], odd[2])
else:
print("NO")
t = int(input())
for test in range(t):
solve()
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> odd, even;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x % 2 == 0) {
even.push_back(i);
} else {
odd.push_back(i);
}
}
if (odd.size() >= 3) {
cout << "YES\n";
cout << odd[0] << " " << odd[1] << " " << odd[2] << '\n';
} else if (odd.size() >= 1 && even.size() >= 2) {
cout << "YES\n";
cout << odd[0] << " " << even[0] << " " << even[1] << '\n';
} else {
cout << "NO\n";
}
}
}
Idea: 74TrAkToR
Preparation: qualdoom
Editorialist: qualdoom
Let's note that it doesn't make sense for us to divide into more than $$$k = 2$$$ subsegments. Let's prove it.
Let us somehow split the array $$$a$$$ into $$$m > 2$$$ subsegments : $$$b_1, b_2, \ldots, b_m$$$. Note that $$$\gcd(b_1, b_2, \ldots, b_m) \le \gcd(b_1 + b_2, b_3, \ldots, b_m)$$$, since if $$$b_1$$$ and $$$b_2$$$ were multiples of $$$\gcd(b_1, b_2 , \ldots, b_m)$$$, so $$$b_1 + b_2$$$ is also a multiple of $$$\gcd(b_1, b_2, \ldots, b_m)$$$. This means that we can use $$$b_1 + b_2$$$ instead of $$$b_1$$$ and $$$b_2$$$, and the answer will not worsen, thus it is always beneficial to use no more than $$$k = 2$$$ subsegments.
How to find the answer? Let $$$s$$$ be the sum of the array $$$a$$$. Let's say $$$pref_i = {\sum_{j = 1}^{i} a_j}$$$, then the answer is $$$\max\limits_{1 \le i < n}(\gcd(pref_i, s - pref_i)$$$.
from math import gcd
t = int(input())
for test in range(t):
n = int(input())
a = list(map(int, input().split()))
s = 0
for i in range(n):
s += a[i]
ans = 0
pref = 0
for i in range(n - 1):
pref += a[i]
ans = max(ans, gcd(pref, s - pref))
print(ans)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
long long s = accumulate(a.begin(), a.end(), 0ll), cur = 0;
long long ans = 1;
for (int i = 0; i < n - 1; i++) {
cur += a[i], s -= a[i];
ans = max(ans, __gcd(s, cur));
}
cout << ans << "\n";
}
}
Idea: AndreyPavlov
Preparation: qualdoom, AndreyPavlov
Editorialist: qualdoom, AndreyPavlov
There are two similar solutions to this problem, we will tell you both.
Subtract $$$1$$$. What can we say now about the number of units at the beginning of the binary notation of a number? There are exactly $$$cnt - cnt_w + 1$$$, where $$$cnt$$$ is the number of unit bits after subtracting the unit, and $$$cnt_w$$$ is — before subtracting. Now we subtract them, for this we need to subtract the number $$$2^{cnt - cnt_w + 1} - 1$$$ and continue the algorithm. But such an algorithm makes at worst $$$60$$$ requests. To save queries, note that we know the number of units after we remove the units from the beginning, therefore it is useless to make another request for this. Then at the same time, as we remove the units from the beginning, we will immediately subtract the unit. As a result, there will be absolutely no more than $$$cnt$$$ operations, where $$$cnt$$$ is the initial number of single bits in the record of the number $$$n$$$. This number does not exceed $$$O(log_2(n))$$$, in turn, $$$log_2(n)$$$ does not exceed 30, which fits into the restrictions.
Let $$$ans$$$ be the desired number $$$n$$$, and $$$was$$$ be the initial number of bits in the number $$$n$$$. Let's subtract the powers of two : $$$2^0, 2^1, 2^2, ... 2^ k$$$, while $$$was$$$ it will not become 0. We will support the $$$Shift$$$ flag — whether there was a bit transfer to $$$n$$$ when subtracting any power of two. Suppose we subtracted $$$2^k$$$ at the $$$k$$$th step and the number of bits became equal to $$$cnt_{new}$$$, and before the subtraction was $$$cnt$$$, then consider two cases.
1) $$$cnt - cnt_{new} = 1$$$, then bit $$$k$$$ was included in $$$n$$$ at the $$$k$$$th step, and if $$$Shift = false$$$, then we add to $$$ans$$$ — $$$2^k$$$, since there was no bit transfer, which means bit k is also in the original number, and subtract from $$$was$$$ — $$$1$$$. If $$$Shift = true$$$, then we added this bit during previous operations, and it does not need to be taken into account.
2) $$$cnt - cnt_{new} \neq 1$$$, then we know that the number of bits has not decreased, also that in the number $$$n$$$ there was such a bit $$$m$$$ that $$$2^m > 2^k$$$, and at the same time the bit $$$m$$$ is in $$$n$$$. Moreover, $$$m - k - 1 = cnt_{new} - cnt$$$. So $$$m = k + 1 + cnt_{new} - cnt$$$. Let's add $$$2^m$$$ to the answer, subtract from $$$was$$$ — $$$1$$$ and assign the $$$Shift$$$ flag the value $$$true$$$, since there was a bit transfer.
Thus, we found the initial number $$$n$$$, which is equal to $$$ans$$$, and also made no more than $$$O(log_2(n))$$$ queries, since $$$k\le log_2(n)$$$.
Thus, the solution spends no more than 30 requests, which fits into the limitations of the task.
t = int(input())
def ask (x):
print('-', x)
return int(input())
for i in range(t):
cur = int(input())
add = 0
ans = 0
while cur > 0:
x = ask(add + 1)
back = x - cur + 1
add = 2 ** back - 1
ans += 2 ** back
cur = x - back
print('!', ans)
#include <iostream>
using namespace std;
int ask (int x) {
cout << "- " << x << endl;
if (x == -1)
exit(0);
cin >> x;
return x;
}
int main() {
int t;
cin >> t;
while (t--) {
int cnt;
cin >> cnt;
int n = 0;
int was = 0;
while (cnt > 0) {
n += 1;
int nw = ask(1 + was);
int back = nw - cnt + 1;
n += (1 << back) - 1;
was = (1 << back) - 1;
cnt = nw - back;
}
cout << "! " << n << endl;
}
}
1780E - Josuke and Complete Graph
Idea: IzhtskiyTimofey
Preparation: IzhtskiyTimofey
Editorialist: IzhtskiyTimofey
Let’s fix $$$g$$$ and check that the $$$g$$$ weight edge exists in $$$G'$$$. The first number, which is divided into $$$g$$$, starting with $$$L$$$ — $$$\lceil \frac{L}{g} \rceil \cdot g$$$, and the second — $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g$$$, note that their $$$\gcd$$$ is $$$g$$$, so the edge between these vertices weighs $$$g$$$. If the second number is greater $$$R$$$, the edge with weight $$$g$$$ in the $$$G'$$$ doesn't exist, because on the segment from $$$L$$$ to $$$R$$$ at most one vertex, which is divided by $$$g$$$. That is, we should calculate the number of such $$$g$$$, which is $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g \leq R$$$.
For $$$g \geq L$$$: $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g = 2 \cdot g$$$. Get the upper limit on the $$$g \leq \lfloor \frac{R}{2} \rfloor$$$. That is, all $$$g$$$ on segment from $$$L$$$ to $$$\lfloor \frac{R}{2} \rfloor$$$ occur in the $$$G'$$$ as weight some edge. Add them to the answer.
Look at $$$g < L$$$.
Note that $$$\lceil \frac{L}{g} \rceil$$$ takes a $$$O(\sqrt{L})$$$ of different values. Let's fix some $$$f = \lceil \frac{L}{g} \rceil$$$. Note that $$$f$$$ corresponds to a consecutive segment $$$l \leq g \leq r$$$. Let's brute this segments in ascending order $$$f$$$. Then, if there is a left border $$$l$$$ of the segment, you can find $$$r$$$ either by binary search or by writing the formula. The next left border is $$$r + 1$$$. Then note, if $$$f$$$ is fixed, then $$$(f + 1) \cdot g \leq R$$$ is equivalent to $$$g \leq \lfloor \frac{R}{f + 1} \rfloor$$$. That is, with a fixed segment from $$$l$$$ to $$$r$$$, $$$g$$$ occurs in the $$$G'$$$ as weight some edge if $$$l \leq g \leq min(r, \lfloor \frac{R}{f + 1} \rfloor)$$$. Then brute all these segments and sum up of all good $$$g$$$.
Overall time complexity is $$$O(\sqrt{L})$$$ or $$$O(\sqrt{L} \cdot log(L))$$$.
def solve():
L, R = map(int, input().split())
ans = max(0, R // 2 - L + 1)
left = 1
while left < L:
C = (L + left - 1) // left
right = (L + C - 2) // (C - 1) - 1
ans += max(0, min(right, R // (C + 1)) - left + 1)
left = right + 1
print(ans)
t = int(input())
for test in range(t):
solve()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
for (int test_case = 0; test_case < t; test_case++){
ll L, R;
cin >> L >> R;
ll ans = max(0ll, R / 2 - L + 1);
for (ll left = 1, right; left < L; left = right + 1){
ll C = (L + left - 1) / left;
right = (L + C - 2) / (C - 1) - 1;
ans += max(0ll, min(right, R / (C + 1)) - left + 1);
}
cout << ans << '\n';
}
}
Idea: AndreyPavlov
Preparation: AndreyPavlov
Editorialist: qualdoom
Let's sort the array and process the triples $$$i, j, k$$$, assuming that $$$i < j < k$$$ and $$$a_i < a_j < a_k$$$. Now if $$$\gcd(a_i, a_k) = 1$$$, then the number of ways to take the index $$$j$$$ is $$$k - i - 1$$$.
We will consider the answer to the problem for each $$$k$$$ from $$$1$$$ to $$$n$$$, assuming that $$$a_k$$$ is the maximum number in the triple. Now let $$$c$$$ be the number of numbers that are mutually prime with $$$a_k$$$ on the prefix from $$$1$$$ to $$$k - 1$$$, and $$$sum$$$ is the sum of their indices. Then you need to add $$$c\cdot i - sum - c$$$ to the answer.
It remains to find out the number of numbers that are mutually prime with $$$a_k$$$ and the sum of their indices. This can be done using the inclusion and exclusion method. Let $$$cnt_i$$$ be the number of numbers $$$a_j$$$ that are divisible by $$$i$$$, $$$s_i$$$ be the sum of the indices $$$j$$$ of numbers $$$a_j$$$ that are divisible by $$$i$$$. Let's look at the prime numbers $$$p_1, p_2, ..., p_m$$$ included in the factorization of the number $$$a_k$$$.
Then let $$$c$$$ initially be equal to the number of numbers on the prefix, and $$$sum$$$ to the sum of the indices on the prefix. Note that then we took into account the extra elements — numbers that are divisible by $$$p_1, p_2, ..., p_m$$$, since they will not be mutually simple with $$$a_k$$$, we subtract them from $$$c$$$ and $$$sum$$$. But having done this, we again took into account the extra elements that are multiples of the numbers of the form $$$p_i * p_j$$$, where $$$i \neq j$$$, add them back, etc. So we can iterate over the mask $$$mask$$$ of the primes $$$p_1, p_2, ..., p_m$$$. And depending on the parity of the bits in the mask, we will subtract or add elements that are multiples of $$$d$$$, where $$$d$$$ is the product of the primes included in $$$mask$$$. Having received $$$c$$$ and $$$sum$$$, we can recalculate the answer for the position $$$i$$$.
To move from position $$$i$$$ to position $$$i+1$$$, update the values of $$$cnt$$$ and $$$s$$$ by adding the element $$$a_{i-1}$$$ by iterating over the mask of the simple element $$$a_{i-1}$$$.
#include "bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define sz(v) ((int)(v).size())
#define all(a) (a).begin(), (a).end()
#define rall(a) a.rbegin(), a.rend()
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define time ((double)clock() / (double)CLOCKS_PER_SEC)
using pii = pair<int, int>;
using ll = long long;
using int64 = long long;
using ld = double;
const ll infll = (ll) 1e18 + 27;
const ll inf = (ll) 1e9;
#define dbg(x) cout << #x << " = " << (x) << endl
template<class T>
using pq = priority_queue<T, vector<T>, less<T>>;
template<class T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename T2>
istream &operator>>(istream &in, pair<T, T2> &b) {
in >> b.first >> b.second;
return in;
}
template<typename T, typename T2>
ostream &operator<<(ostream &out, const pair<T, T2> &b) {
out << "{" << b.first << ", " << b.second << "}";
return out;
}
template<typename T>
istream &operator>>(istream &in, vector<T> &b) {
for (auto &v : b) {
in >> v;
}
return in;
}
template<typename T>
ostream &operator<<(ostream &out, vector<T> &b) {
for (auto &v : b) {
out << v << ' ';
}
return out;
}
template<typename T>
ostream &operator<<(ostream &out, deque<T> &b) {
for (auto &v : b) {
out << v << ' ';
}
return out;
}
template<typename T>
void print(T x, string end = "\n") {
cout << x << end;
}
template<typename T1, typename T2>
bool chkmin(T1 &x, const T2 &y) { return x > y && (x = y, true); }
template<typename T1, typename T2>
bool chkmax(T1 &x, const T2 &y) { return x < y && (x = y, true); }
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N = 3e5 + 10;
ll s[N];
ll cnt[N];
ll d[N][20];
int ptr[N];
bool u[N];
ll Cnt = 0;
ll Sum = 0;
ll Ans = 0;
void Answer (int x, int pos) {
ll C = Cnt;
ll X = Sum;
int K = (1ll << ptr[x]);
for (int mask = 1; mask < K; mask++) {
ll k = 1;
for (int j = 0; j < ptr[x]; j++) {
if ((mask >> j) & 1) {
k *= d[x][j];
}
}
int bits = __builtin_popcount(mask);
int D = k;
if (bits % 2 == 1) {
C -= cnt[D];
X -= s[D];
} else {
C += cnt[D];
X += s[D];
}
}
Ans += C * pos - X;
}
void add (int x, int pos) {
Cnt += 1;
Sum += pos + 1;
auto v = d[x];
int K = (1ll << ptr[x]);
for (int mask = 1; mask < K; mask++) {
ll k = 1;
for (int j = 0; j < ptr[x]; j++) {
if ((mask >> j) & 1) {
k *= d[x][j];
}
}
int D = k;
s[D] += pos + 1;
cnt[D] += 1;
}
}
void solve() {
for (int i = 2; i < N; i++) {
if (!u[i]) {
for (int j = i; j < N; j += i) {
u[j] = true;
d[j][ptr[j]] = i;
ptr[j]++;
}
}
}
int n;
cin >> n;
vector<int> a(n);
cin >> a;
sort(all(a));
for (int i = 0; i < n; i++) {
Answer(a[i], i);
if (i > 0) {
add(a[i - 1], i - 1);
}
}
cout << Ans << "\n";
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}
Idea: IzhtskiyTimofey
Preparation: IzhtskiyTimofey, AndreyPavlov
Editorialist: IzhtskiyTimofey, AndreyPavlov
This problem has several solutions using different suffix structures. We will tell two of them — using suffix array, and using suffix automaton.
Let's build suffix array $$$suf$$$ and array $$$lcp$$$ (largest common prefixes) on the string $$$s$$$. Fix some $$$k > 1$$$ и consider about all substring $$$s$$$ length $$$k$$$. Match $$$1$$$ to positions $$$i$$$ array $$$lcp$$$, such that $$$lcp_i \geq k$$$, and match $$$0$$$ to other positions. One in position $$$i$$$ means that the substrings length $$$k$$$ starting at $$$suf_i$$$ and $$$suf_{i + 1}$$$ are equal. Consider any block of units length $$$len$$$, then for $$$len + 1$$$ substrings length $$$k$$$ number of occurrences in $$$s$$$ — $$$len + 1$$$, then in order for the substrings in this block to be delicious, it is necessary that $$$len + 1$$$ divided by $$$k$$$.
Let's brute $$$k$$$ from $$$n$$$ to $$$2$$$ и sustain all sizes blocks. Then, when shift to a new $$$k$$$ should events — change $$$0$$$ to $$$1$$$, for all $$$i$$$, such that $$$lcp_i = k$$$. To do this you can sustain DSU (Disjoint set union). Then for each block size we know the number of blocks with this size. Then it is enough to consider all blocks of length $$$len$$$, such as $$$len + 1$$$ — divider $$$k$$$. It can be done explicitly, just brute $$$k$$$, $$$2 \cdot k$$$, ..., as $$$len + 1$$$. And this works in sum of harmonic series: $$${\sum_{k = 2}^{n} \lfloor \frac{n}{k} \rfloor}$$$ $$$= O(n \cdot log(n))$$$.
For $$$k = 1$$$, obviously, any substring length $$$1$$$ satisfies, so you can just add $$$n$$$ to the answer.
Overall time complexity is $$$O(n \cdot log(n))$$$.
The solution with the suffix automaton is as follows: let's build the suffix automaton itself, now we calculate for each vertex of the suffix automaton the dynamics $$$dp_v$$$ — this is the number of paths from the vertex $$$v$$$ to the terminal vertices. This dynamics means the number of occurrences of the substring corresponding to this vertex in the entire string. Let's introduce the function $$$f(v)$$$ — the length of the longest substring leading to the vertex $$$v$$$. We know that all substrings of length from $$$l_v$$$ to $$$r_v$$$ lead to the vertex $$$v$$$ of the suffix automaton — each once. Where $$$r_v = f(v)$$$ and $$$l_v = f(suff_v) + 1$$$, where $$$suff_v$$$ is the suffix link of $$$v$$$. Why is it so? All substrings of the form $$$s[x:k], s[x+1:k], ..., s[y:k]$$$ lead to the vertex $$$v$$$ of the suffix automaton, and there is a suffix link $$$suff_v$$$ to which lead all substrings of the form $$$s[x + 1:k], s[y + 2:k], ..., s[t: k]$$$.
In order to solve the problem, let's go through the $$$v$$$ vertex and look at the number of occurrences of any substring that leads to the $$$v$$$ — $$$dp_v$$$ vertex, then fix $$$c$$$ — the number of such $$$l_v \le x \le r_v$$$, that $$$dp_v$$$ is evenly divisible by $$$x$$$. Therefore, $$$dp_v \cdot c$$$ must be added to the answer. All divisors can be stored in $$$O(n \cdot log(n))$$$ and each time find the number of such $$$x$$$ by binsearch.
Asymptotics $$$O(n \cdot log(n))$$$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> suffix_array(string s){
int n = s.size();
vector<int> a(n), c(n), h(n);
vector<pair<char, int>> t;
for (int i = 0; i < n; i++) t.push_back({s[i], i});
sort(t.begin(), t.end());
int cur = -1;
for (int i = 0; i < n; i++){
if (i == 0 || t[i].first != t[i - 1].first){
cur++;
h[cur] = i;
}
a[i] = t[i].second;
c[a[i]] = cur;
}
vector<int> a1(n), c1(n);
for (int len = 1; len < n; len *= 2){
for (int i = 0; i < n; i++){
int j = (n + a[i] - len) % n;
a1[h[c[j]]++] = j;
}
a = a1;
cur = -1;
for (int i = 0; i < n; i++){
if (i == 0 || c[a[i]] != c[a[i - 1]] || c[(a[i] + len) % n] != c[(a[i - 1] + len) % n]){
cur++;
h[cur] = i;
}
c1[a[i]] = cur;
}
c = c1;
}
return a;
}
vector<int> build_lcp(string s, vector<int> suf){
int n = s.size();
vector<int> rsuf(n), lcp(n);
for (int i = 0; i < n; i++) rsuf[suf[i]] = i;
int cur = 0;
for (int i = 0; i < n; i++){
int j = rsuf[i];
if (j != n - 1){
while (s[suf[j] + cur] == s[suf[j + 1] + cur]) cur++;
lcp[j] = cur;
}
if (cur > 0) cur--;
}
return lcp;
}
const int N = 1e6 + 1;
int r[N], l[N], us[N], cnt[N];
vector<int> pos[N];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
string s;
cin >> s;
s += '$';
vector<int> suf = suffix_array(s);
vector<int> lcp = build_lcp(s, suf);
for (int i = 0; i < lcp.size(); i++) {
pos[lcp[i]].push_back(i);
}
ll ans = n;
for (int k = n; k >= 2; k--) {
for (int i : pos[k]) {
// add i
us[i] = true;
cnt[1]++;
l[i] = r[i] = i;
if (i != 0 && us[i - 1]) {
cnt[i - l[i - 1]]--;
cnt[1]--;
cnt[i - l[i - 1] + 1]++;
l[i] = l[i - 1];
r[l[i - 1]] = i;
}
if (i + 1 < lcp.size() && us[i + 1]) {
cnt[r[i + 1] - i]--;
cnt[i - l[i] + 1]--;
cnt[r[i + 1] - l[i] + 1]++;
l[r[i + 1]] = l[i];
r[l[i]] = r[i + 1];
}
}
for (int x = k; x <= n; x += k) {
ans += 1ll * x * cnt[x - 1];
}
}
cout << ans << "\n";
}
/* Includes */
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
/* Using libraries */
using namespace std;
/* Defines */
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ld long double
#define pb push_back
#define vc vector
#define sz(a) (int)a.size()
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pii pair <int, int>
#define vec pt
#define all(a) a.begin(), a.end()
const int K = 26;
const int N = 1e6 + 1;
struct node {
int next[K];
int suf = -1, pr = -1, dp = 0, len = 0, ch = -1;
node () {
forn (i, K) next[i] = -1;
}
};
int get (char c) {
if (c >= 'a')
return c - 'a';
return c - 'A';
}
int lst = 0, sz = 1;
node t[N * 2];
int used[N * 2];
int add (int a, int x) {
int b = sz++;
t[b].pr = a;
t[b].suf = 0;
t[b].ch = x;
for (; a != -1; a = t[a].suf) {
if (t[a].next[x] == -1) {
t[a].next[x] = b;
t[b].len = max(t[b].len, t[a].len + 1);
continue;
}
int c = t[a].next[x];
if (t[c].pr == a) {
t[b].suf = c;
break;
}
int d = sz++;
forn (i, K) t[d].next[i] = t[c].next[i];
t[d].suf = t[c].suf;
t[c].suf = t[b].suf = d;
t[d].pr = a;
t[d].ch = x;
for (; a != -1 && t[a].next[x] == c; a = t[a].suf) {
t[a].next[x] = d;
t[d].len = max(t[d].len, t[a].len + 1);
}
break;
}
return b;
}
void add (char c) {
lst = add(lst, get(c));
}
void dfs (int u) {
used[u] = 1;
for (int i = 0; i < K; ++i) {
if (t[u].next[i] == -1) continue;
int v = t[u].next[i];
if (!used[v])
dfs(v);
t[u].dp += t[v].dp;
}
}
vc <int> p[N], pr;
int dr[N];
vc <pii> d;
int l, r, cur = 0;
int cnt_log (int x, int y) {
int z = 1, res = 0;
while (y >= z) {
z *= x;
++res;
}
return res - 1;
}
void rec (int i, int x) {
if (i == sz(d)) {
cur += l <= x;
return;
}
rec(i + 1, x);
for (int j = 1; j <= d[i].second; ++j) {
x *= d[i].first;
if (x > r)
break;
rec(i + 1, x);
}
}
void solve () {
int n;
cin >> n;
string s;
cin >> s;
for (char c : s)
add(c);
for (int a = lst; a != -1; a = t[a].suf)
t[a].dp = 1;
dfs(0);
for (int i = 2; i <= n; ++i) {
if (dr[i] == 0) {
dr[i] = i;
pr.pb(i);
}
for (int j = 0; j < sz(pr) && pr[j] <= dr[i] && i * pr[j] <= n; ++j)
dr[i * pr[j]] = pr[j];
}
long long ans = 0;
forn (i, sz) {
if (t[i].len == 0) continue;
l = t[t[i].suf].len + 1;
r = t[i].len;
int x = t[i].dp;
d.clear();
while (x > 1) {
int y = dr[x];
if (d.empty() || d.back().first != y)
d.pb({y, 1});
else
d.back().second++;
x /= y;
}
rec(0, 1);
ans += t[i].dp * cur;
cur = 0;
}
cout << ans << '\n';
}
/* Starting and precalcing */
signed main() {
/* freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); */
fast;
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
Can't wait for the solution of C. Show us guys, how to solve NP-hard problems!
Hahahahahahahaha you're so funny hahahahhaha
Maybe it is P but not O(n^2).
Prove P=NP to solve it
Not my duty, lol
Has no one made a hack for C yet?
The tester code probably uses the same faulty algorithm so it would be to no avail.
The author's solution is wrong. Therefore, any hack would still get AC, even if the output is incorrect.
Problem D was very interesting :) ,one mistake and whole efforts of problemsetters and testers got ruined.
I thought D was easier than B. Although I kinda over complicated B for no reason.
Weren't the incorrect greedy solutions for C O(n)? Why was the constraint on the problem O(n^2) then?
I think it was to allow solutions that did not use priority_queue or something similar
On the last row of Tutorial of B:
"Let $$$s$$$ be the array $$$a$$$"
should probably be
"Let $$$s$$$ be the sum of the array $$$a$$$"
They probably used machine translation. The solution to E is impenetrable.
delete
It's a bad idea because some poor people like me spent ~30min trying to solve it and ~20min trying to understand why so many people solved such a hard problem xd
delete
No
LOL. Some people solved C with incorrect solutions that they figured out within minutes and moved on. And those who realized that solution is incorrect will be punished. What kind of fairness is that?
My solution failed system tests on C because it got a better result than the author's one, lol
Did you found any counter-test for your solution?
Yeah
They should have asked for the exact assignment instead of just the maximum value, so that they can check for a
FAIL
verdict correctly. (FYI,FAIL
is the verdict when the submission found a better solution than the jury's) They might have found the issue before the contest if this was the case.lol
how it should be 11 can u explain it bit more clearer...
There are 6 guests who likes the dish #1, and the remaining 5 likes the #2. So if we split the 6 guests in table #1 and #2, and the 5 who like #2 at table #3, all 11 guests will be happy.
Problem G is quite similar to this problem. I had to modify my solution for the Educational round problem a bit to get AC on this round's G.
A brief tutorial to problem E, for people like me who cannot follow the official one:
Value $$$x$$$ will appear in one of the edges iff: $$$L \leq px < (p+1)x \leq R$$$, where $$$p=ceil(\frac{L}{x})$$$.
Now we enumerate every value of $$$p$$$ and count the number of possible $$$x$$$ for each $$$p$$$.
For $$$p=p_0$$$, the above inequality gives range of x: $$$\frac{L}{p_0} \leq x \leq \frac{R}{p_0+1}$$$.
Note that there is a hidden constraint of $$$ceil(\frac{L}{x}) = p_0$$$. This translates to $$$\frac{L}{p_0} \leq x < \frac{L}{p_0-1}$$$.
Combine the two ranges above, we get, for $$$p=p_0$$$, possible values of $$$x$$$ satisfies: $$$\frac{L}{p_0} \leq x \leq min(\frac{R}{p_0+1}, floor(\frac{L-1}{p_0-1}))$$$.
And we use sqrt decomposition to solve this counting problem: For $$$p\leq sqrt(L)+1$$$, we compute the range of $$$x$$$. For $$$p > sqrt(L)+1$$$, we have $$$x \leq sqrt(L)$$$, so we can just iterate through all $$$x$$$ values.
Complexity is $$$O(sqrt(L))$$$.
In C question greedy solution fail on test case-
1
11 3
1 1 1 1 1 1 2 2 2 2 2
5 4 2
correct answer for above testcase = 11, but greedy solution gives answer = 10
Can anyone explain what was the intended solution for C, which turned out to be incorrect.
Group people by what they like, and while there are groups of people and tables left, try to put the largest group on the largest table. If they don't fit, just use as many as you can and subtract that amount before deleting the table. If they do fit, delete the group of people and the table. "Answer" is however many people this process gives a table. The original might've been slightly different, but this is the silly wrong solution I got AC with.
In
Problem D
, in 2nd Tutorial (by qualdoom), for the condition (pt.2) where "$$$cnt-cnt_{new}\not=1$$$", can someone kindly explain the part, how this below equation is formed?$$$m - k - 1 = cnt_{new} - cnt$$$
Consider the real number is 24 its binary representation is
11000
, and you need to guess this number. also, you can't subtract a number greater than the real number so if we subtracted 1 from real number which was 24, we will have 23 which its binary representation is10111
so the number of unit bits has been changed and become 4-unit bits instead of 2 how this happened? hence, we now have 23 which has 4-unit bits and previous has 2 so the LSB at index (4-2+1) 0-based we add1<<lsbIndex
to obtain the real number. I hope that helped you.Who can explain me, how to use mobius function in problem F?
When you want to get $$$f(d) = \#func(a, b)$$$ where $$$gcd(a, b) = d$$$. You can count $$$g(d) = \#func(a, b)$$$ where $$$d | a$$$ and $$$d | b$$$.
Then $$$f(d) = \sum_{i=1}^n g(i * d) * \mu(i)$$$
Where $$$\mu(x)$$$ is the mobius function.
Then you need to count for each number $$$k$$$ from 1 to max $$$a_i$$$, the number of triplets $$$(a_i, a_j, a_k)$$$ with $$$k | min(a_i, a_j, a_k)$$$ and $$$k | max(a_i, a_j, a_k)$$$.
Mobius, more like Morbius
Can you share some resources where I can study this?
these blogs are very useful:
https://codeforces.me/blog/entry/54090
https://codeforces.me/blog/entry/53925
but I got the main idea from this pdf
I don't know why. I want to comfort the author. qnq
Here goes an easier and short solution of F which does not involve Mobius or this inclusion-exclusion using masks and their parity
Can someone give a test case where this approach gives a wrong answer to C?
Calculate how many meals of each type and how many tables of each size there are.
Go through the meals, if there is a table with the same size as the count of that meal, then put those people to that table.
Put remaining meal and table counts to two priority queues. While there are still some empty tables or not all people has a spot: take the top of meals and put them at the biggest empty table, if some people who like that meal are still left, check if there is empty table with that amount of spots, if there is put them there, otherwise put that number back to priority queue.
Ok, here's a counterexample: tables are
2 2 3
and people are1 1 1 1 2 2 2
. The second step goes as no-op, so you will take ones into the third table (which has 3 seats) and then twos are placed in the remaining first/second table, which is not a correct strategy since you could have placed ones into first and second table and then remaining twos into the third table.My approach for D (similar to the second tutorial solution, it seems, but it doesn't explicitly need flags and might be easier to understand for some):
To determine whether the last bit is 0 or 1, we can simply subtract 1. If the last bit was a 1, then it becomes 0 and the $$$cnt$$$ decreases by exactly 1. Now that the last bit is already 0, we can check the second-to-last bit by subtracting 2. In general, if the last $$$k$$$ bits are set to 0 while the rest of the bits are unchanged from the original, we can test bit position $$$k$$$ (from the right) by subtracting $$$2^k$$$ and seeing if $$$cnt$$$ decreases by exactly 1.
But what happens when the bit at the position we're testing (let's say position $$$k$$$) is actually a 0? In that case, $$$cnt$$$ either stays the same or increases, so we know that this position originally has a 0. However, this attempted subtraction of $$$2^k$$$ ruins our desired pattern, because the bit at position $$$k$$$ changed from 0 to 1 and at least one bit on its left has changed. We would have wanted the bits from up to position $$$k$$$ to all be 0 and everything else unchanged in order to test the next bit, at position $$$k + 1$$$...
We can deal with this by "undoing" the latest undesirable subtraction by instead treating it as part of the next subtraction. Normally, the next subtraction is supposed to be $$$2^{k + 1}$$$, but since we already performed an undesirable subtraction of $$$2^k$$$, we simply subtract another $$$2^k$$$ to result in a overall subtraction of $$$2^{k + 1}$$$ as if the undesired subtraction never happened.
Note that there could be a sequence of undesirable subtractions, in which case, we just keep track of the total of the undesirable subtractions and treat them all as part of the next subtraction. Eventually, we would have to find a 1, which resolves all these undesirable subtractions. Once we find the MSB, the $$$cnt$$$ should become 0, at which point, we are done.
My submission: 190561881 ($$$acc$$$ is the accumulation of undesired subtractions that we are trying to undo)
Thank you for the explanation!!
Simple implementation for F 190544353
Can you explain your solution if it's different from the editorial?
I have similar solution. Mine is: calculate $$$dp[x]$$$ -- number of ways to choose a triple which value of gcd is $$$x$$$. To calculate amount of such triples for every $$$x$$$ sort an array then for every $$$x$$$ consider only numbers which are divisible by $$$x$$$, let their indices be $$$ind$$$, we should calculate sum over all $$$i < j$$$ of $$$ind_j - ind_i - 1$$$, we can calculate it by iterating over these indices storing sum of considered indices and their cnt. Then you have a $$$dp$$$ where you should substract from $$$dp[x]$$$ $$$dp[2 * x], dp[3 * x], ...$$$ to obtain correct answer.
Consider for g<sqrt(L) and g>sqrt(L) respectively, for the first situation there's at most sqrt(L) values of g, so ceil(L/g) will have at most sqrt(L) values. For the second situation, we have 1<=ceil(L/g)<L/g+1<L/sqrt(L)+1=sqrt(L)+1, so there's at most ceil(sqrt(L)) different values.
How to generate all values of ceil(L / i) where i belongs to [1, L] in O(sqrt(L))?
First let i = 1 to ceil(sqrt(L))-1. For the remaining values, for m = L/ceil(sqrt(L)) to 1, calculate the range where ceil(L/i)=m.
I did the same thing in problem B yet kept getting TLE. Can someone point out my mistake. Thankyou!
Please help !
cuml may not fit in 32bit integers
use long long, instead of long int. https://en.cppreference.com/w/cpp/language/types Long int's aren't always 64 bits-width, maybe that's a problem in your case.
On 32-bit compilers "long int" is same as "int", both of them are 32 bits. Use "long long" instead.
What is the time complexity in F and why is it quick? IMHO we have O(N * 2^(an average number of prime divisors)) so it doesn't seem like a quick solution.
lets think like this. you know the number of divisors of a number n is O(log(n)). now you are only iterating on SOME of these divisors.
Let $$$preres_x$$$ be the number of ways of choosing the triplets where the $$$gcd(a_i,b_j)$$$ is a multiple of $$$x$$$ and $$$res_x$$$ be the number of ways of choosing the triplets where $$$gcd(a_i,b_i)$$$ is exactly $$$x$$$. You can calculate array $$$res$$$ from $$$preres$$$. If you know the values of $$$res_y$$$ for all $$$y$$$ (where $$$y$$$ is a multiple of $$$x$$$) and $$$preres_x$$$, then you can calculate the value of $$$res_x$$$ and finally, $$$res_1$$$ will be the answer. You can do this by iterating from $$$3*10^5$$$ to $$$1$$$.
The time complexity is sum of harmonic sequence $$$\sum_{x = 1}^{N} \left \lfloor \frac{N}{x} \right \rfloor$$$ which is equal to $$$O(nlogn)$$$.
Of all the rounds this had to happen in a round full of Jojo's references
Can someone please tell me what was wrong with C? My approach to solving C was: Group all the guests having the same liking. Now assign the biggest group to the largest table. If some guests are still left, insert them in the priority queue and continue this way.
How was C an NP hard problem?
https://codeforces.me/blog/entry/111737?#comment-995960
Your approach is incorrect. Consider the following scenario:
If you assign the biggest group to the largest table, then the 4-table serves dish 1 (all four like it), one of the 3-tables serves dish 2 (all three like it), and the other 3-table serves dish 1 (two out of three like it), with one unsatisfied guest. But if you instead had both 3-tables serve dish 1 while the 4-table serves dish 2, then everyone would be satisfied.
ok Thanks for telling
Even though C couldn't be solved with given constraints during the contest I think it's better to lower constraints to make it solvable, write a proper solution and post the updated solution in the editorial, instead of completely removing it from the contest and archive. The problem is not bad at all, tbh.
It's NP-hard, which means it almost certainly cannot be solved in polynomial time. Constraints would require $$$n$$$ to be about $$$20$$$, or maybe even less! The brute-force solution would be incredibly dull. There may be heuristics to speed it up and allow a little higher constraints, but this is not suitable for CP.
Doesn't mean it can't be solved at all. Better to keep a modified version with extremely low constraints than to remove it completely.
Can anybody tell me "correct" solution of C? or at least some ideas
I would surely become a specialist after this round (rank 16) but...... It's unrated! And problem G is kind of rigid that almost everyone who has learnt sam before can solve it.
But anyway,the problems are excellent!
can someone explain what's wrong with problem C. Instead of posting correct solution why authors completely removed problem C
There is no correct solution to that problem. It is a NP-hard problem which cannot be solved in polynomial time
D was quite confusing cuz I have never solve interactive problems lol. F was easier than normal :V.
I don't understand the tutorial for problem G. Can anyone explain the idea of it?
Does any one know how to calculate the time complexity of G? More detailedly,the time complexity of find the number of x,which is a factor of n, that l<=x<=r? The solution implied that is almost nlog(n) in total , but I can't understand why.
how do we get the root L bound in problem E. Can someone prove