Thanks for participating in the contest . We hope you liked the problems. We would love to hear your feedback in the comments.
If you find anything wrong in the editorial which is more likely to happen because we have written a rather long editorial to make you understand the solutions better, then comment below.
We also tried to write the thought process of how you can come up with the solution for the easier problems. The approach I followed is similar to what the current AI agents do. They first generate some thoughts, then do some actions, then gather observations, and repeat the process until they find the solution. Hope you will like this approach.
Also, don't forget to upvote the editorial. See you in the next contest!
Also, please rate the problems after checking the editorial. Because otherwise you might have solved it in a very cumbersome way that you will end up hating the problem.
Also, huge props to redpanda for creating awesome manim video editorials for problems A to D. Check it out here: https://www.youtube.com/watch?v=elRvvUbk1J4
Author: YouKn0wWho
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
using ll = long long;
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cout << 2 * i - 1 << ' ';
}
cout << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Author: YouKn0wWho
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
using ll = long long;
void solve() {
string s; cin >> s;
int n = s.size();
for (int i = 0; i + 1 < n; i++) {
if (s[i] == s[i + 1]) {
cout << s.substr(i, 2) << '\n';
return;
}
}
for (int i = 0; i + 2 < n; i++) {
if (s[i] != s[i + 1] and s[i] != s[i + 2] and s[i + 1] != s[i + 2]) {
cout << s.substr(i, 3) << '\n';
return;
}
}
cout << -1 << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
2039C1 - Shohag Loves XOR (Easy Version)
Author: YouKn0wWho
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int x; ll m; cin >> x >> m;
int ans = 0;
for (int y = 1; y <= min(2LL * x, m); y++) {
if (x != y and ((x % (x ^ y)) == 0 or (y % (x ^ y) == 0))) {
++ans;
}
}
cout << ans << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
2039C2 - Shohag Loves XOR (Hard Version)
Author: YouKn0wWho
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int x; ll m; cin >> x >> m;
// divisible by x
ll p = m - m % x;
ll ans = p / x - (x < p);
if ((x ^ p) >= 1 and (x ^ p) <= m) ++ans;
p += x;
if ((x ^ p) >= 1 and (x ^ p) <= m) ++ans;
// divisibly by y
for (int y = 1; y <= min(1LL * x, m); y++) {
ll cur = x ^ y;
if (cur % y == 0) {
++ans;
}
}
// divisible by both
if (x <= m) {
--ans;
}
cout << ans << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Author: YouKn0wWho
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int p[N];
void solve() {
int n, m; cin >> n >> m;
vector<int> s(m + 1);
for (int i = 1; i <= m; i++) {
cin >> s[i];
}
if (m < __lg(n) + 1) {
cout << -1 << '\n';
return;
}
for (int i = 1; i <= n; i++) {
cout << s[m - p[i]] << ' ';
}
cout << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 2; i < N; i++) {
if (p[i]) continue;
for (int j = i; j < N; j += i) {
int x = j;
while (x % i == 0) x /= i, ++p[j];
}
}
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
using ll = long long;
vector<int> d[N];
void solve() {
int n, m; cin >> n >> m;
vector<int> s(m + 1);
for (int i = 1; i <= m; i++) {
cin >> s[i];
}
vector<int> a(n + 1, -1);
for (int i = 1; i <= n; i++) {
set<int> banned;
for (int j: d[i]) {
banned.insert(a[j]);
}
for (int k = m; k >= 1; k--) {
if (banned.find(s[k]) == banned.end()) {
a[i] = s[k];
break;
}
}
if (a[i] == -1) {
cout << -1 << '\n';
return;
}
}
for (int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
cout << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 1; i < N; i++) {
for (int j = i + i; j < N; j += i) {
d[j].push_back(i);
}
}
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
2039E - Shohag Loves Inversions
Author: YouKn0wWho
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9, mod = 998244353;
using ll = long long;
int dp[N]; // count of arrays that we can get if the current number of inversions is > max element of the array
void solve() {
int n; cin >> n;
int sum = 0;
for (int i = n; i >= 1; i--) {
dp[i] = (1LL * i * sum % mod + 1) % mod;
sum = (sum + dp[i]) % mod;
}
int ans = n - 1; // arrays having 0 and 1 inversions
for (int k = 3; k <= n; k++) {
int ways = (1LL * (k - 1) * (k - 2) / 2 - 1 + mod) % mod; // count of arrays achievable such that > 1 inversion count was inserted for the first time
ans += 1LL * ways * dp[k] % mod;
ans %= mod;
}
cout << ans << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
#include <bits/stdc++.h>
#include <chrono>
std::mt19937 eng(std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) { return std::uniform_int_distribution<int>(l, r)(eng); }
namespace FastIO {
// char buf[1 << 21], *p1 = buf, *p2 = buf;
// #define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
// inline char rChar() { char ch = getchar(); while (!isalpha(ch)) ch = getchar(); return ch; }
}; using namespace FastIO;
using i32 = int32_t;
using u32 = uint32_t;
using u64 = uint64_t;
template <uint32_t MOD> struct mint {
static constexpr u32 get_r() {
u32 ret = MOD;
for (i32 i = 0; i < 4; ++i) ret *= 2 - MOD * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(MOD) % MOD;
static_assert(r * MOD == 1, "invalid, r * MOD != 1");
static_assert(MOD < (1 << 30), "invalid, MOD >= 2 ^ 30");
static_assert((MOD & 1) == 1, "invalid, MOD % 2 == 0");
u32 a;
constexpr mint() : a(0) {}
constexpr mint(const int64_t &b) : a(reduce(u64(b % MOD + MOD) * n2)){};
static constexpr u32 reduce(const u64 &b) { return (b + u64(u32(b) * u32(-r)) * MOD) >> 32; }
constexpr mint &operator += (const mint &b) { if (i32(a += b.a - 2 * MOD) < 0) a += 2 * MOD; return *this; }
constexpr mint &operator -= (const mint &b) { if (i32(a -= b.a) < 0) a += 2 * MOD; return *this; }
constexpr mint &operator *= (const mint &b) { a = reduce(u64(a) * b.a); return *this; }
constexpr mint &operator /= (const mint &b) { *this *= b.inverse(); return *this; }
constexpr mint operator + (const mint &b) const { return mint(*this) += b; }
constexpr mint operator - (const mint &b) const { return mint(*this) -= b; }
constexpr mint operator * (const mint &b) const { return mint(*this) *= b; }
constexpr mint operator / (const mint &b) const { return mint(*this) /= b; }
constexpr bool operator == (const mint &b) const { return (a >= MOD ? a - MOD : a) == (b.a >= MOD ? b.a - MOD : b.a); }
constexpr bool operator != (const mint &b) const { return (a >= MOD ? a - MOD : a) != (b.a >= MOD ? b.a - MOD : b.a); }
constexpr mint operator-() const { return mint() - mint(*this); }
constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul, n >>= 1; } return ret; }
constexpr mint inverse() const { return pow(MOD - 2); }
friend std::ostream &operator<< (std::ostream &os, const mint &b) { return os << b.get(); }
friend std::istream &operator>> (std::istream &is, mint &b) { int64_t t; is >> t; b = mint<MOD>(t); return (is); }
constexpr u32 get() const { u32 ret = reduce(a); return ret >= MOD ? ret - MOD : ret; }
static constexpr u32 get_MOD() { return MOD; }
explicit operator u32() const { return get(); }
}; using modint = mint<998244353>;
// Let's write some brute first
// dp[i][j] := current length is i, current number of inversions is j (not inserted)
// dp[i][j] -> dp[>= i + 1][[j + 1, j + i]]
// this is true for j >= 1, so let's do something when j = 0
// we can generate [0, (0 ... ), 1, 0] -> dp[>= 3][1]
// this is still kinda annoying because 1 > 1 does not hold, we process it till j >= 2
// [0, 0, ..., 0, 1, 0] -> [0, 0, ..., 0, 1, 0, 1, ..., 1]
// after that we insert an 1 before some numbers of 0 and we get dp[i][1] -> dp[>= i + 1][[j + 1, j + i - 1]]
// the answer is sum dp[i][j] for all 1 <= i <= n, j >= 1, plus 1 ([0, 0, 0 ... 1])
// actually we care nothing 'bout, j so let's say f[i] = sum dp[i][j]
// (f[i] * i - 1) -> f[i + 1], f[i + 2], ..., f[n]
#define MAXN 1000001
modint f[MAXN];
void solve() {
int n = read<int>(); modint ans = 1, pre = 2;
f[3] = 1;
for (int i = 4; i <= n; ++i)
f[i] = pre + modint(1), pre += f[i] * modint(i) - modint(1);
for (int i = 3; i <= n; ++i) ans += f[i];
// f[3] : [0, 1, 0]
// f[4] : [0, 0, 1, 0] (+1), [0, 1, 1, 0], [1, 0, 1, 0] (dp[3][1] * 2)
print<int>(ans.get(), '\n');
}
int main() { int T = read<int>(); while (T--) solve(); return 0; }
2039F1 - Shohag Loves Counting (Easy Version)
Author: YouKn0wWho
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9, mod = 998244353;
using ll = long long;
int add(int a, int b){
a += b;
if(a > mod) a -= mod;
if(a < 0) a += mod;
return a;
}
// dp[i][j] = number of arrays where starting element is i and gcd of the array is j
int dp[N], cur[N], uni[N];
int sum[N];
vector<int> d[N];
void solve() {
int m; cin >> m;
for (int i = 1; i <= m; i++) {
dp[i] = cur[i] = 0;
uni[i] = 0;
sum[i] = 0;
}
int ans = 0;
ans = 0;
for (int i = m; i >= 1; i--) {
for (int j: d[i]) {
cur[j] = 0;
}
int sz = d[i].size();
for(int idj = sz-1; idj >= 0; idj--){
int j = d[i][idj];
uni[j] = add(sum[j],sum[j]);
for(int idk = idj+1; idk < sz; idk++){
int k = d[i][idk];
if(k%j) continue;
uni[j] = add(uni[j],-uni[k]);
}
cur[j] = add(uni[j], - add(dp[j],dp[j]));
}
cur[i] += 1;
for (int j : d[i]) {
dp[j] = add(dp[j],cur[j]);
for(auto k : d[j]){
sum[k] = add(sum[k],cur[j]);
}
ans = add(ans,cur[j]);
}
}
cout << ans << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i) {
d[j].push_back(i);
}
}
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
2039F2 - Shohag Loves Counting (Hard Version)
Author: YouKn0wWho
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9, mod = 998244353;
inline void add(int &x, int y) {
x = x + y >= mod ? x + y - mod : x + y;
}
int mob[N];
void mobius() {
mob[1] = 1;
for (int i = 2; i < N; i++){
mob[i]--;
for (int j = i + i; j < N; j += i) {
mob[j] -= mob[i];
}
}
for (int i = 1; i < N; i++) {
mob[i] = (mob[i] % mod + mod) % mod;
}
}
vector<int> divs[N];
int dp[N];
int f[N];
int tmp[N], ans[N];
void solve() {
for (int i = 1; i < N; i++) {
for (int d: divs[i]) {
tmp[d] = (mod - f[d]) % mod;
for (int c: divs[d]) {
add(tmp[d], dp[c]);
}
tmp[d] = (2 * tmp[d] + 1) % mod;
}
// apply mobius inversion formula
for (int d: divs[i]) {
for (int c: divs[d]) {
add(dp[d], 1LL * mob[c] * tmp[d / c] % mod);
}
add(f[d], tmp[d]);
}
ans[i] = ans[i - 1];
add(ans[i], f[i]);
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i) {
divs[j].push_back(i);
}
}
mobius();
solve();
int t = 1;
cin >> t;
while (t--) {
int m; cin >> m;
cout << ans[m] << '\n';
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9, mod = 998244353;
inline void add(int &x, int y) {
x = x + y >= mod ? x + y - mod : x + y;
}
int spf[N];
void sieve() {
vector<int> p;
for(int i = 2; i < N; i++) {
if (spf[i] == 0) spf[i] = i, p.push_back(i);
int sz = p.size();
for (int j = 0; j < sz && i * p[j] < N && p[j] <= spf[i]; j++) {
spf[i * p[j]] = p[j];
}
}
}
int mob[N];
void mobius() {
mob[1] = 1;
for (int i = 2; i < N; i++){
mob[i]--;
for (int j = i + i; j < N; j += i) {
mob[j] -= mob[i];
}
}
for (int i = 1; i < N; i++) {
mob[i] = (mob[i] % mod + mod) % mod;
}
}
int c[N];
vector<int> divs[N];
void gen_divs(int n) { // not sorted
int id = 1, x = n;
divs[n][0] = 1;
while (n > 1) {
int k = spf[n];
int cur = 1, sz = id;
while (n % k == 0) {
cur *= k;
n /= k;
for (int i = 0; i < sz; i++) {
divs[x][id++] = divs[x][i] * cur;
}
}
}
}
void prec() {
sieve();
// generate divisors without using push_back as its really slow on Codeforces
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i) {
c[j]++;
}
divs[i].resize(c[i]);
gen_divs(i);
}
mobius();
}
int dp[N];
int f[N];
int tmp[N], ans[N];
void solve() {
for (int i = 1; i < N; i++) {
for (int d: divs[i]) {
tmp[d] = (mod - f[d]) % mod;
for (int c: divs[d]) {
add(tmp[d], dp[c]);
}
tmp[d] = (2 * tmp[d] + 1) % mod;
}
// apply mobius inversion formula
for (int d: divs[i]) {
for (int c: divs[d]) {
add(dp[d], 1LL * mob[c] * tmp[d / c] % mod);
}
add(f[d], tmp[d]);
}
ans[i] = ans[i - 1];
add(ans[i], f[i]);
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
prec();
solve();
int t = 1;
cin >> t;
while (t--) {
int m; cin >> m;
cout << ans[m] << '\n';
}
return 0;
}
Author: YouKn0wWho
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
const int N = 1e6 + 9, T = 1e7 + 9, RT = 33333, mod = 998244353;
using ll = long long;
int power(int n, long long k) {
int ans = 1 % mod;
while (k) {
if (k & 1) ans = (long long) ans * n % mod;
n = (long long) n * n % mod;
k >>= 1;
}
return ans;
}
int SQRT(int n) {
int x = sqrt(n);
while (x * x < n) ++x;
while (x * x > n) --x;
return x;
}
int spf[T], id[T], DIAMETER, mu[T];
vector<int> primes; // 1 indexed
int prefix_prime_count[T], prefix_sum_mu[T];
void init() {
mu[1] = 1;
for(int i = 2; i < T; i++) {
if (spf[i] == 0) spf[i] = i, mu[i] = i <= DIAMETER ? 0 : -1, primes.push_back(i);
int sz = primes.size();
for (int j = 0; j < sz && i * primes[j] < T && primes[j] <= spf[i]; j++) {
spf[i * primes[j]] = primes[j];
if (i % primes[j] == 0) mu[i * primes[j]] = 0;
else mu[i * primes[j]] = mu[i] * (primes[j] <= DIAMETER ? 0 : -1);
}
}
primes.insert(primes.begin(), 0);
for (int i = 1; i < primes.size(); i++) {
id[primes[i]] = i;
}
for (int i = 2; i < T; i++) {
prefix_prime_count[i] = prefix_prime_count[i - 1] + (spf[i] == i);
}
for (int i = 1; i < T; i++) prefix_sum_mu[i] = prefix_sum_mu[i - 1] + mu[i];
}
int cnt[N]; // count of nodes having each diameter
int m;
namespace GoodNumbers { // numbers which aren't divisible by the first k primes
gp_hash_table<int, int, custom_hash> mp[RT << 1];
int count_num(int n, int k) { // n is a floor value, returns good numbers <= n
if (k == 0 or n == 0) return n;
if (primes[k] >= n) return 1;
if (n < T and 1LL * primes[k] * primes[k] > n) {
return 1 + prefix_prime_count[n] - k;
}
if (mp[k].find(n) != mp[k].end()) return mp[k][n];
int ans;
if (1LL * primes[k] * primes[k] > n) {
int x = upper_bound(primes.begin(), primes.begin() + k, (int)SQRT(n)) - primes.begin() - 1;
ans = count_num(n, x) - (k - x);
}
else ans = count_num(n, k - 1) - count_num(n / primes[k], k - 1);
mp[k][n] = ans;
return ans;
}
};
vector<pair<int, int>> v;
namespace Dirichlet {
// good number = numbers that aren't divisible by any prime <= DIAMETER
// we will run dirichlet imagining there exists no prime <= DIAMETER
gp_hash_table<int, int, custom_hash> mp;
int p_c(int n) {
return n < 1 ? 0 : 1;
}
int p_g(int n) {
return GoodNumbers::count_num(n, v.back().first);
}
int solve (int x) { // sum of mob[i] over 1 <= i <= x and i is a good number
if (x < T) return prefix_sum_mu[x];
if (mp.find(x) != mp.end()) return mp[x];
int ans = 0;
for (int i = 2, last; i <= x; i = last + 1) {
last = x / (x / i);
ans += solve(x / i) * (p_g(last) - p_g(i - 1));
}
ans = p_c(x) - ans;
return mp[x] = ans;
}
};
int count_primes(int n) {
if (n < T) return prefix_prime_count[n];
int x = SQRT(n);
int k = upper_bound(primes.begin(), primes.end(), x) - primes.begin() - 1;
return GoodNumbers::count_num(n, k) + k - 1;
}
// diameter > 2 * sqrt(m)
void solve_large() {
// only primes are good, so count total ways
// and subtract where gcd is prime (means all nodes have a fixed prime)
int total_ways = 1;
int primes_under_m = count_primes(m);
for (auto [k, c]: v) {
if (m <= primes[k]) break;
total_ways = 1LL * total_ways * power((primes_under_m - k + 1) % mod, c) % mod; // 1 or a prime > k
}
int bad_ways = (max(0, primes_under_m - v.back().first)) % mod;
int ans = (total_ways - bad_ways + mod) % mod;
cout << ans << '\n';
}
// diameter <= 2 * sqrt(m)
void solve_small() {
int ans = 0;
for (int l = 1, r; l <= m; l = r + 1) {
int x = m / l;
r = m / x;
int cur = ((Dirichlet::solve(r) - Dirichlet::solve(l - 1)) % mod + mod) % mod;
if (cur) {
int mul = 1;
for (auto [k, c]: v) {
if (x <= primes[k]) break;
mul = 1LL * mul * power(GoodNumbers::count_num(x, k) % mod, c) % mod;
}
ans += 1LL * cur * mul % mod;
ans %= mod;
}
}
cout << ans << '\n';
}
vector<int> g[N];
int dp[N], up[N];
void dfs(int u, int p = 0) {
dp[u] = 0;
if (p) g[u].erase(find(g[u].begin(), g[u].end(), p));
for (auto v: g[u]) {
if (v ^ p) {
dfs(v, u);
dp[u] = max(dp[u], dp[v] + 1);
}
}
}
int pref[N], suf[N];
void dfs2(int u) {
int sz = g[u].size();
for (int i = 0; i < sz; i++) {
int v = g[u][i];
pref[i] = dp[v] + 1;
if (i) pref[i] = max(pref[i], pref[i - 1]);
}
for (int i = sz - 1; i >= 0; i--) {
int v = g[u][i];
suf[i] = dp[v] + 1;
if (i + 1 < sz) suf[i] = max(suf[i], suf[i + 1]);
}
for (int i = 0; i < sz; i++) {
int v = g[u][i];
int cur = up[u];
if (i) cur = max(cur, pref[i - 1]);
if (i + 1 < sz) cur = max(cur, suf[i + 1]);
up[v] = cur + 1;
}
for (auto v: g[u]) {
dfs2(v);
}
}
int mx_d[N];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n >> m;
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
dfs2(1);
for (int u = 1; u <= n; u++) {
vector<int> vec;
if (u != 1) vec.push_back(up[u]);
for (auto v: g[u]) {
vec.push_back(dp[v] + 1);
}
sort(vec.rbegin(), vec.rend());
mx_d[u] = vec[0];
if (vec.size() > 1) {
mx_d[u] += vec[1];
}
mx_d[u] += 1;
}
for (int i = 1; i <= n; i++) {
cnt[mx_d[i]]++;
DIAMETER = max(DIAMETER, mx_d[i]);
}
init();
int last_prime = 0;
for (int i = 2; i <= DIAMETER; i++) {
if (spf[i] == i) last_prime = i;
if (cnt[i]) {
int k = id[last_prime];
if (!v.empty() and v.back().first == k) {
v.back().second += cnt[i];
} else {
v.push_back({k, cnt[i]});
}
}
}
if (DIAMETER > 2 * SQRT(m)) solve_large();
else solve_small();
return 0;
}
2039H1 - Cool Swap Walk (Easy Version)
Author: wuhudsm
We can observe that this kind of path is imporatnt — when we are in $$$(x, x)$$$, we only perform one of the following two kind of moves:
Move 1
This move transforms $$$[\ldots,a_x, a_{x+1},\ldots]$$$ into $$$[\ldots,a_{x+1}, a_{x},\ldots]$$$.
Move 2
This move transforms $$$[\ldots,a_x, a_{x+1},a_{x+2},\ldots]$$$ into $$$[\ldots,a_{x+2}, a_{x+1},a_{x},\ldots]$$$.
Summary of the path:
Note the arrays before and after the path as $$$a$$$ and $$$a'$$$, respectively. We can see $$$a'_n=a_1$$$, and $$$[a'_1,\ldots,a'_{n-1}]$$$ can be obtained from $$$[a_2,\ldots,a_{n}]$$$ through the following transformation:
- Swap any two adjacent numbers of $$$[a_2,\ldots,a_{n}]$$$, but each number can be swapped at most once.
This inspires us to use Odd-Even Sort algorithm.
Steps to Achieve the Sorted Array:
Step $$$1$$$: Initialize $$$a_1 = mn$$$: If $$$a_1 \neq mn$$$, where $$$mn$$$ is the minimum of the array, use the following path:
This sequence ensures that $$$a_1 = mn$$$.
Then, repeat steps $$$2$$$ and $$$3$$$ until the array is sorted.
Step $$$2$$$: Perform Odd-Even Sorting: Perform an Odd-Even Sort (a round of comparison) using the key path above on the subarray $$$a_2, \dots, a_n$$$.
Step $$$3$$$: Maintain the orderliness of $$$[a_{2}, \dots ,a_{n}]$$$ while repeatedly making $$$a_1 = mn$$$: After step $$$2$$$, we want $$$mn$$$ back to the head of the array. To achieve this, perform the following operations:
This sequence transforms the array as follows:
When this is performed after an odd-even sort, it ensures that:
- $$$mn$$$ is back to the head of the array.
- The subarray $$$a_1, \dots, a_{n-1}$$$ has been cyclically shifted.
Handling Continuous Cyclic Shifts in Odd-Even Sort:
- Even Length ($$$n-1$$$ is even): Cyclic shifting does not affect the odd-even sort. You can continue applying the sort as usual.
- Odd Length ($$$n-1$$$ is odd): A small modification is needed. Specifically, First compare $$$(a_3,a_4),(a_5,a_6),\ldots$$$ instead of $$$(a_2,a_3),(a_4,a_5),\ldots$$$ This adjustment ensures that the odd-even sort operates correctly despite the continuous cyclic shifts.
Overall, we obtained a sorted array using $$$2n$$$ walks.
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=2010;
int T,n,mn,tot;
int a[N];
vector<int> X[N],Y[N];
void path1(int num) //(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->...
{
for(int i=1;i<=n;i++)
{
X[num].push_back(i),Y[num].push_back(i);
if(i!=n)
{
X[num].push_back(i),Y[num].push_back(i+1);
swap(a[i],a[i+1]);
}
}
}
void path2(int num) //(1,1)->(1,n)->(n,n)
{
for(int i=1;i<=n;i++)
{
X[num].push_back(1),Y[num].push_back(i);
swap(a[1],a[i]);
}
for(int i=2;i<=n;i++)
{
X[num].push_back(i),Y[num].push_back(n);
swap(a[i],a[n]);
}
}
void walk1(int j)
{
X[tot].push_back(j-1),Y[tot].push_back(j);
X[tot].push_back(j-1),Y[tot].push_back(j+1);
X[tot].push_back(j),Y[tot].push_back(j+1);
X[tot].push_back(j+1),Y[tot].push_back(j+1);
swap(a[j-1],a[j+1]);
}
void walk2(int j)
{
X[tot].push_back(j-1),Y[tot].push_back(j);
X[tot].push_back(j),Y[tot].push_back(j);
X[tot].push_back(j),Y[tot].push_back(j+1);
X[tot].push_back(j+1),Y[tot].push_back(j+1);
swap(a[j-1],a[j]);
swap(a[j],a[j+1]);
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
mn=n;tot=0;
for(int i=1;i<=n;i++) mn=min(mn,a[i]);
for(int i=1;i<=3*n;i++) X[i].clear(),Y[i].clear();
int p1;
for(int i=1;i<=n;i++) if(a[i]==mn) p1=i;
if(p1!=1)
{
tot++;
for(int i=1;i<=p1;i++) X[tot].push_back(1),Y[tot].push_back(i),swap(a[1],a[i]);
for(int i=2;i<=p1;i++) X[tot].push_back(i),Y[tot].push_back(p1),swap(a[i],a[p1]);
for(int i=p1+1;i<=n;i++) X[tot].push_back(p1),Y[tot].push_back(i),swap(a[p1],a[i]);
for(int i=p1+1;i<=n;i++) X[tot].push_back(i),Y[tot].push_back(n),swap(a[i],a[n]);
}
for(int i=2;i<=n;i++)
{
tot++;
X[tot].push_back(1),Y[tot].push_back(1);
if(n&1)
{
if(i&1)
{
for(int j=2;j<=n;j+=2)
{
if(j+1==i) walk2(j);
else if(a[j]>a[j+1]) walk1(j);
else walk2(j);
}
}
else
{
for(int j=2;j<=n;j+=2)
{
if(a[j]>a[j+1]) walk1(j);
else walk2(j);
}
}
}
else
{
if(i&1)
{
for(int j=2;j<=n;j+=2)
{
if(j==i-1)
{
X[tot].push_back(j-1),Y[tot].push_back(j);
X[tot].push_back(j),Y[tot].push_back(j);
swap(a[j-1],a[j]);
j--;
}
else if(a[j]>a[j+1]) walk1(j);
else walk2(j);
}
}
else
{
for(int j=2;j<=n;j+=2)
{
if(j==i)
{
X[tot].push_back(j-1),Y[tot].push_back(j);
X[tot].push_back(j),Y[tot].push_back(j);
swap(a[j-1],a[j]);
j--;
}
else if(a[j]>a[j+1]) walk1(j);
else walk2(j);
}
}
}
path2(++tot);
}
printf("%d\n",tot);
for(int i=1;i<=tot;i++)
{
for(int j=1;j<2*n-1;j++)
{
if(X[i][j]==X[i][j-1]) printf("R");
else printf("D");
}
printf("\n");
}
}
return 0;
}
2039H2 - Cool Swap Walk (Hard Version)
Author: wuhudsm
First, read the editorial of the easy version. We can see that the bottleneck lies in the fact that after every round of odd-even sorting, we need to perform a walk operation to ensure that $$$a_1 = mn$$$.
The following method can break through this bottleneck: for simplicity, let's assume $$$n$$$ is even. Define the numbers smaller than or equal to $$$\frac{n}{2}$$$ as $$$S$$$, and the numbers bigger than $$$\frac{n}{2}$$$ as $$$B$$$. If we have $$$a = [S, \ldots, S, B, \ldots, B]$$$, we can repeatedly perform key path operations to get the following sequence:
- $$$[S, \ldots, S, B, \ldots, B] \to [S, \ldots, S, B, \ldots, B, S] \to [S, \ldots, S, B, \ldots, B, S, S] \to \ldots \to [B, \ldots, B, S, \ldots, S]$$$ In this process, we only perform odd-even sorting for the subarray $$$[B, \ldots, B]$$$.
- $$$[B, \ldots, B, S, \ldots, S] \to [B, \ldots, B, S, \ldots, S, B] \to [B, \ldots, B, S, \ldots, B, B] \to \ldots \to [S, \ldots, S, B, \ldots, B]$$$ In this process, we only perform odd-even sorting for the subarray $$$[S, \ldots, S]$$$.
After that, the array is sorted.
Finally, the only remaining problem is how to arrange $$$a = [S, \ldots, S, B, \ldots, B]$$$.
Assume we have $$$k$$$ positions $$$p_1, p_2, \ldots, p_k$$$ such that $$$1 < p_1 < p_2 < \ldots < p_k \leq n$$$. Consider what the following operations are doing:
$$$(1, 1) \to (1, p_1)\to (2, p_1) \to (2, p_2)\to (3, p_2) \to \ldots \to (k, p_k)$$$
If we ignore the other numbers,these operations correspond to:
$$$\text{swap}(a_1, a_{p_1}), \text{swap}(a_2, a_{p_2}), \ldots$$$
Then, we can take any path from $$$(k, p_k)$$$ to $$$(n, n)$$$.
At first, we perform one operation to set $$$a_1 = n$$$, then choose $$$\frac{n}{2}$$$ positions $$$p_1, p_2, \ldots, p_{\frac{n}{2}}$$$ to obtain $$$a = [S, \ldots, S, B, \ldots, B]$$$.
For $$$n$$$ being odd, we need two additional operations for some little adjustments.
Overall, we obtained a sorted array using $$$n + 4$$$ walks.
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=2010;
int T,n,tot;
int a[N];
vector<int> X[N],Y[N];
void path1(int num) //(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->...
{
for(int i=1;i<=n;i++)
{
X[num].push_back(i),Y[num].push_back(i);
if(i!=n)
{
X[num].push_back(i),Y[num].push_back(i+1);
swap(a[i],a[i+1]);
}
}
}
void path2(int num) //(1,1)->(1,n)->(n,n)
{
for(int i=1;i<=n;i++)
{
X[num].push_back(1),Y[num].push_back(i);
swap(a[1],a[i]);
}
for(int i=2;i<=n;i++)
{
X[num].push_back(i),Y[num].push_back(n);
swap(a[i],a[n]);
}
}
void path3(int num,vector<int> p) //swap(1,p[0]),(2,p[1]),... note p[0]!=1
{
for(int i=1;i<=p[0];i++)
{
X[num].push_back(1),Y[num].push_back(i);
swap(a[1],a[i]);
}
for(int i=1;i<p.size();i++)
{
for(int j=p[i-1];j<=p[i];j++)
{
X[num].push_back(i+1),Y[num].push_back(j);
swap(a[i+1],a[j]);
}
}
int x=p.size(),y=p.back();
while(x!=n)
{
x++;
X[num].push_back(x),Y[num].push_back(y);
swap(a[x],a[y]);
}
while(y!=n)
{
y++;
X[num].push_back(x),Y[num].push_back(y);
swap(a[x],a[y]);
}
}
void walk1(int j)
{
X[tot].push_back(j-1),Y[tot].push_back(j);
X[tot].push_back(j-1),Y[tot].push_back(j+1);
X[tot].push_back(j),Y[tot].push_back(j+1);
X[tot].push_back(j+1),Y[tot].push_back(j+1);
swap(a[j-1],a[j+1]);
}
void walk2(int j)
{
X[tot].push_back(j-1),Y[tot].push_back(j);
X[tot].push_back(j),Y[tot].push_back(j);
X[tot].push_back(j),Y[tot].push_back(j+1);
X[tot].push_back(j+1),Y[tot].push_back(j+1);
swap(a[j-1],a[j]);
swap(a[j],a[j+1]);
}
void walk3(int j)
{
X[tot].push_back(j-1),Y[tot].push_back(j);
X[tot].push_back(j),Y[tot].push_back(j);
swap(a[j-1],a[j]);
}
void init()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
tot=0;
for(int i=1;i<=3*n;i++) X[i].clear(),Y[i].clear();
vector<pair<int,int> > pr;
for(int i=1;i<=n;i++) pr.push_back(make_pair(a[i],i));
sort(pr.begin(),pr.end());
for(int i=1;i<=n;i++) a[pr[i-1].second]=i;
}
void step1()
{
int p1,pn;
vector<int> p;
for(int i=1;i<=n;i++) if(a[i]==1) p1=i;
if(p1!=1)
{
p.push_back(p1);
path3(++tot,p);
}
if(n==2) return ;
tot++;
X[tot].push_back(1),Y[tot].push_back(1);
for(int j=2;j<=n;j+=2)
{
if(j+1>n) walk3(j);
else if(a[j]==n) walk1(j);
else walk2(j);
}
p1=n;
for(int i=1;i<=n;i++) if(a[i]==n) pn=i;
p.clear();
p.push_back(pn);p.push_back(p1);
path3(++tot,p);
p.clear();
for(int i=1;i<=n;i++) if(a[i]<=(n+1)/2) p.push_back(i);
path3(++tot,p);
}
void step2()
{
int head;
if(n&1)
{
for(int t=1;t<=2;t++)
{
head=n/2+2;
for(int i=1;i<=n/2+(t==1);i++)
{
tot++;
X[tot].push_back(1),Y[tot].push_back(1);
for(int j=2;j<=n;j++)
{
if(!(head<=j&&j<=head+n/2-1)) walk3(j);
else if(j==head&&(head&1)) walk3(j);
else
{
if(!(head<=j+1&&j+1<=head+n/2-1)) walk3(j);
else if(a[j]>a[j+1]) walk1(j),j++;
else walk2(j),j++;
}
}
head--;
}
}
}
else
{
for(int t=1;t<=2;t++)
{
head=n/2+1;
for(int i=1;i<=n/2;i++)
{
tot++;
X[tot].push_back(1),Y[tot].push_back(1);
for(int j=2;j<=n;j++)
{
if(!(head<=j&&j<=head+n/2-1)) walk3(j);
else if(j==head&&(head&1)) walk3(j);
else
{
if(!(head<=j+1&&j+1<=head+n/2-1)) walk3(j);
else if(a[j]>a[j+1]) walk1(j),j++;
else walk2(j),j++;
}
}
head--;
}
}
}
}
void output()
{
printf("%d\n",tot);
for(int i=1;i<=tot;i++)
{
for(int j=1;j<2*n-1;j++)
{
if(X[i][j]==X[i][j-1]) printf("R");
else printf("D");
}
printf("\n");
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
init();
step1();
step2();
output();
}
return 0;
}
Even after solving A,B my rating went from 999 to 994 why?
Many people solved C1 and higher difficulty problems, so your rank dropped to 6000+ out of ~9100+ which gets calculated as a slightly lower performance than your last rating.
You can check more on rating calculation at https://mirror.codeforces.com/blog/entry/20762 or try out some CodeForces Rating Predictor for a better view on the rank vs rating.
Oh! Okay I guess I have to grind more to reach pupil
Bitmask + XOR = Pain
Shohag Loves Bitmasks :')
Shohag loves OEIS (specially A079752)
_LonggVuz. bitmasks almost killed me, the problem D saved my rating ._.
F2: Cool problem, but why set the time limit so tight? The model solution (and most of the contestants' solutions) run in over 3s, and I couldn't get my solution to run much faster than 5s during the contest. :(
I agree. It's a cool problem but the time limit is too tight
I liked B, C1, C2, E. Thanks for the round. H also looks interesting
Anyone else solved C2 using binary search ? 😂 😂
I did. I found the highest y <= m, such that x^y is a multiple of x.
No sir we are sane
Could you explain your binary search solution?
What's the approximate rating of D?
https://clist.by/problems/
Here you can see approximate ratings of all problems
Probably 1800 to 1900.
On clist, his rating is roughly 1700 points
The problem E does not request even ability to think. We need only slow solution that can calculate the number of possible arrays without modulo for $$$n < 14$$$ (which is easy to implement) and Wolfram Mathematica function
FindSequenceFunction
, which attempts to find a simple function that yields the sequence, when given successive integer arguments. Using the slow solution, we get the following sequence $$$(0, 1, 2, 5, 19, 102, 682, 5321, 47071, 464570, 5057058, 60166913, 776595027)$$$ of the answers. Now, we can useFindSequenceFunction
to obtain the solution:It gives the answer:
It is the recurrence relation, which can be simply coded: 292998575.
Some learnings as an Author: Judging by the votes and comments it seems like people mostly liked the problems individually but didn't like that most problems were mathy and didn't have enough variations. So I will try to keep that in mind and will add more variations to the contest in the future.
And I am also not happy that during the contest we found out that some people found the second difference/derivative of the sequence on OEIS. I searched on OEIS before but couldn't find it (I saw that it's not there but I didn't notice that there are some deltas matching for another sequence that were written on the OEIS page, I guess I have to be better regarding finding sequences on OEIS). Otherwise, we would have definitely modified the problem. Sorry for this issue.
Hopefully next time I will try to bring a more diverse round. Thanks for participating in the round!
Why
Shohag
loves so much number theory, although problems are really good.Bro how does D have more solves than C2
Hello every one I have been trying to learn more about mobius function and it’s application but I couldn’t find any resources Can some one help me in this matter ?
It's mobin' time.
The time limit of F2 is very bad. The solution which runs in $$$\sum_i \sigma^2(i)$$$ should have passed easily. It should not be a close call. The optimisations into $$$\sum_i \sigma(i) \times p(i)$$$ do not add any new ideas, and the constraints suggest there is a solution faster than this.
The inclusion of both C1 and C2 may make sense in terms of round balance (which frankly, is still pretty bad), but I don't see it being a good idea to test the same skill-set twice.
There's a cute solution to D.
Let
cnt(x)
be the number of divisors ofx
, not including 1 andx
.Then, set
answer[i]
to be equal toS[m - cnt(i)]
.That's it :)
And if the index is ever equal to zero or negative (assuming indexing starts at 1), then output -1.
The reasoning stems from the same thoughts as the editorial, though I am too tired to write out a formal proof.
https://mirror.codeforces.com/contest/2039/submission/292985320
My D solution failing at testcase 2. Any help will be deeply appreciated.
My solution of how managed to solve C2 but also at the same time failed miserably at it. I am able to skip an observation, but with paid a serious price in terms of implementation.
We need to check for $$$x| x \ xor \ y$$$ or $$$y | x\ xor\ y$$$. The second case is only possible if $$$y <= 2x$$$. We focus on the first case, rewrite $$$x xor y$$$ as $$$x + y - 2 (x\ and\ y)$$$. Let $$$k$$$ be the smallest integer such that $$$2^k > x$$$. Then, the value of $$$y\ mod\ 2^k$$$ is enough to determine $$$x\ and\ y$$$. For each $$$0 \leq c < 2^k$$$, we consider $$$y = a2^k + c$$$, this becomes a certain divisbility condition imposed on $$$a$$$, which can be solved with a certain CRT. This solution is now $$$O(x \log x)$$$.
To optimise, It can be seen (by looking at the implementation), that the required extended modular inverse to calculate is same for every $$$c$$$, so the $$$log x$$$ time to calculate inverse is common. This gives a solution of $$$O(x)$$$.
Being able to come up with a highly technical alternative solution, but unable to actually follow through with it in implementation, turns out to costed me greatly in this round. Submission: 292984478.
The condition $$$x|x \oplus y$$$ is equivalent to $$$x|y-2(x&y)$$$. Since $$$y=a2^k+c$$$, we just need to determine whether there exists some $$$a$$$ st $$$x|a2^k+c-2(x&c)$$$, or equivalently whether there exists some $$$a$$$ st $$$a2^k \equiv 2(x&c)-c \pmod x$$$. Could you please explain how you do this? I tried to understand from your code, but it has always been hard for me to read other's code, plus I don't know Kotlin. Any help would be greatly appreciated, thank you.
you will be seeking some $$$a$$$ such that it is within some calculated range (depending on $$$m$$$), and $$$a2^k \equiv d$$$, where $$$d = 2(c\ and\ x) -x$$$, and thus fixed per $$$c$$$. It is not too difficult to solve that the possible $$$a$$$ must be something of the form $$$As+B$$$ for some integer $$$A$$$,$$$B$$$, which can be calculated with (extended) modular inverses. The formula is as follows:
I might have a little less mathy and simpler explanation for C2.
Let’s say
x XOR y
is a multiple ofx
.So,
x XOR y = c * x
(wherec
is any integer>= 0
).If
c = 0
:x XOR y = 0
impliesx = y
(which is a valid case).If
c = 1
:x XOR y = x
impliesy = 0
(which is an invalid case sincey > 0
).If
c = 2
:x XOR y = 2 * x
impliesy = (2 * x) XOR x
.In this case,
y > x
, because the leftmost bit in2 * x
is not set inx
. Therefore, the XOR operation introduces a set bit that makesy > x
.Thus,
x XOR y
is a multiple ofx
if and only ify > x
.Now, consider
y = (c * x) XOR x
for some constantc
.From this, we can deduce:
y <= c * x + x
andy >= c * x - x
.So, for any multiple of
x
, the value ofy
can differ fromc * x
by at mostx
.To solve this:
x
that are<= m
.y
is valid withinm
.Personally, I used binary search to find the largest
y
such thaty = (c * x) XOR x <= m
. Then, I checked the next two multiples ofx
beyond this point to see if their corresponding range ofy
also falls withinm
.Dividing the Range of
y
Since
1 <= y <= m
, we can split the range ofy
into two parts:For
1 <= y <= x
:Here, we can simply loop over all values of
x
inO(n)
and check ifx XOR y
is divisible byx
ory
.For
x < y <= m
:From the earlier reasoning,
x XOR y
is divisible byx
. But not divisible byy
, as shown in the editorial in Case 2.This approach ensures correctness and efficiency with a O(n) solution.
Thanks.I think in this way but can't find out y <= c*x; also x is efficient as there is m = 1e18
Please tell me why k+2 to (k+10)??
If you play with xor a little and see how xor works (think about most significant bit), then u'll see that for any two numbers x and y (where y > x), we have
y-x <= x xor y <= x+y
So, if you replace y with cx, then you have that inequality mentioned above.
At the time of the contest I was not sure about this elaborate proof and perfectly with the constraints. I just figured out that there would be some multiples of x above m, so I just thought there could not be more than 10 multiples. So I just took a guess and went with it. Later on I found out that there could be at most 2 such multiples.
Thanks Please check my submission (http://mirror.codeforces.com/contest/2039/submission/292965221)I was solve C1 within 1 to x and got ac but tutorial say 2*x is there any edge case for my solution?
Yeah I also, just solved looping till x. Maybe there is either no test case for that or if we see it more rigorously, we can prove it.
Actually I got an observation that after the msb of x if bit is on in y then x^y is not a divisor of y or x, it's only possibly when all bit is off in x but x = 0 is not possible so always answer lie in x. Just share my thinking it can be right or wrong.
Hey,can you please tell me why did you put (y <= m) in the condition,in your c1 solution?
xor is like subtraction without borrowing.(problem c2 editorial correction)YouKn0wWho
.
C2: I found a "cool" way to solve it using some insight in the pattern of valid y when y>x. In particular the pattern has length
2^k
, where k is32 - clz(x) - ctz(x)
. In this way we can then easily count by blocks of the given length and then iterate through the pattern untill there are enough numbers. This solution works in O(n), my submission took more time because I used larger upperlimits to be sure of choosing the right pattern and avoid silly mistakes.Submission: 292969986
Did I think wrong or there exist a clerical error in the F1 question? If sequence a is a non decreasing sequence, then the maximum value of subinterval with length $$$k$$$ should be the last $$$n - k+1$$$ numbers instead of $$$k$$$ numbers?
why my code gets tle any help is appreciated problem d. 293022163
Well Explained.
Shit E.Don't make this kind of problem again.
What is OEIS?
https://oeis.org
read this
I am not very good at math but this contest is full of math. This sucks.
Thank you YouKn0wWho for such good editorials. I would love to see more such editorials.
Edit: I don't know why did the comment get so many dislikes, sorry if my comment looks irrelevant. I just wanted to appreciate the editorial as I got to learn something new from it.
B was too easy, for a Div 1+2 Contest ! (Not to mention
Shohag
's obession w/ maths.)So, under these circumstances, wouldn't it be possible to have a time limit in C1?
Since 1≤t≤1e4 and 1≤x≤1e6.
I'd like to make C2 case 1 clearer:
Initial conditions:
Let's consider ranges $$$ [1;m-x]$$$, $$$(m-x;m+x]$$$ and $$$(m+x;\infty)$$$
The first point, "... Thus, for this segment, we add $$$\lfloor \frac{m - x}{x} \rfloor$$$ to our answer.".
I can't understand this last argument. What is the proof?
Edit: Gotcha! We need to get the number of multiples of $$$x$$$ in the range $$$[1, m - x]$$$ so $$$p$$$ can be any of these multiples and there is always a valid $$$y$$$ for such $$$p$$$.
(x^y) <= x + y trivially
thank you for your explaination,which helps me a lot QWQ
when x=2 y=4 lcm(x,y) = 4 but 2*max(x,y) = 8 it against the Solution in c2 how to solve it
The C2's case3 is wrong, x = 2 and y = 4 then boom lcm(x,y)≥2⋅max(x,y) is wrong
For C2, the editorial for case 3 says when x isn’t equal to y, lcm(x,y) >= 2*max(x,y) isn’t this not true for x=2, y=4 for example? How does this prove that only x=y works for this case?
An alternative proof would be something like:
Wlog let y > x. lcm(x,y) >= y. Assume (x ^ y)/lcm(x,y)=k (where k is some integer).
k!=1, (x^y)/lcm(x,y) <= (x+y)/y < 2. So k = 0 which would mean x=y.
why is k != 1?
no, the interpretation they tried to show may be is the following: given: x^y < 2*max(x,y) and we want lcm(x,y) divide x^y . now, try with all multiple of lcm(x,y) which are less than 2*max(x,y) because x^y always smaller than 2*max(x,y) and if we take lcm(x,y) = max(x,y) then then first multiple of lcm(x,y) will be lcm(x,y) it self and we made it equal to x^y => x^y = max(x,y) => one of them must be zero if x!=y, which is a contradiction. so lcm(x,y) must be at least 2*max(x,y). may be they wanted this, not sure.
Is there a lower bound on the minimum number of operations needed for problem H? My randomized code can pass every test currently using no more than $$$n+3$$$ operations, but cannot squeeze the number to $$$n+2$$$ on test 25.
UPD: This code used at most $$$n-1$$$ operations and passed. Of course we have to use at least $$$1$$$ operation when $$$n=2$$$, so it seems that this code reached the lower bound?
I don't feel like there is any reason why the theoretical lower limit of O(log n) cannot be reached. When solving the problem, I saw that for small n, 3 operations could get every permutation (n<=7). It seems that the operation is extremly versatile, but as usual such versatility is hard to made use of constructively.
.
Well, what's wrong with C2? imo it is indeed a nice problem (maybe nicer without C1). But currently it got 165 downvotes.
In problem C1, I got ac but In my implementation where 1 to x is sufficient to find out Y. Please check my submission and tell me is there any edge case can i got wa??Also in tutorial y <= 2 * x but i can do it in x https://mirror.codeforces.com/contest/2039/submission/292965221
Shohag really loves GCD.
i feel shame for not solving D
please help me where is it better to solve archive tasks
acmp or timus?
i will remember this round like one of the most funniest in my life. B problem is so good, love math and patterns. and c1 is really most funniest shit i ever done. it's shame i didn't done a D problem(TL at one of the last tests)
my point is-why people downvoting this round???? it was really cool round
D , solution 2 i understand that this solution achieve optimal sequence but i can't prove why when im at some index that have m or more divisors and these divisors use all m values so the answer -1 !
at index i, u need to find the biggest number in S where a[i] ≠ a[divisors of i], so when there is no a possible number, the answer is -1.
i mean why it's -1 if there's no possible number depending on my divisors values ,one could say my previous steps were bad that what i need to prove
Because the optimal way is also to choose the max possible number,
to make sure that a[divisors of i] ≠ gcd(a[divisors of i], a[i]), is to make sure that the values of a[divisors of i] is greater than a[i], then the values of gcd(a[divisors of i],a[i]) will never be equal to a[divisors of i].
so the answer is -1 when there is no enough numbers.
thanks <3
Can someone explain what's going on with their solution to E? In their last paragraph ("And to count..."), their last sum goes from 1+2+3+..,+(m-2) to (m-1)(m-2)/2-1 which has an extra -1 term.
Also, I thought that there would be j places to put the 1 instead of j-1. You can put the extra 1 before the 1 and before any of the previous j-1 zero terms for a total of j instead of j-1 spots.
Never mind, I figured it out. There's just a small typo. Instead of the sum starting at j = 2, it should start at j = 3.
Here is an explanation for the formula in G (no explanation was given), for anyone who wants it:
Denote S_g as the number of assignments of a's such that the a's have gcd divisible by g. Denote "a_u can not be a multiple of any prime number p <= h_u" by (*)
First, the formula of S_g only makes sense when considering g's that are good, because otherwise, for a vertex of index x that is on the longest path (so h_x = D), there will be a prime p less than D that divides a_x (since g divides a_x and there is a prime p less than D that divides g, so p divides a_x), so the condition (*) is broken.
The mobius function in there is used for Inclusion-exclusion principle purposes. To see that, let's consider all the primes between 1 and m, denote them by p_1,...p_r. Denote by B_i the set of assignments that have their gcd not divisible by p_i. Then what we desire is the size of the set Intersection(B_i, for i from 1 to r). From the inclusion-exclusion principle: |Inters(all B_i)| = |Union(all B_i)| — sum of all |B_i| + sum of all |B_i inters B_j| — ...
|Union(all B_i)| = S_1, and |for k many B_i's : Inters of B_i's| = S_(product of those k indexes), with its sign being the parity of k. Note that we don't need numbers that contain a prime twice in their factorization, so the mobius function is ideal for our use since it excludes them.
The answer thus is sum from 1 to m of whether_g_is_good(g) * mobius(g) * S_g.
How to compute S_g: Since g divides all a_i, and g is coprime with all numbers between 1 and D since it is good, we thus get that any number p <= h_i that doesn't divide a_i also doesn't divide a_i / g. There are floor(m/g) numbers divisible by g in the interval [1, m]. Hence, for each vertex with index i, we have f_(floor(m/g)),(h_i) ways to choose an a_i that is divisible by g and isn't divisible by anything less than h_i. Therefore, S_g = product for all i in [1, n] of f_(floor(m/g)),(h_i)
Have u proved in problem F that all valid sequences can be generated from a valid non-decreasing sequence?
Maximum is on one of the ends of the array. Suppose we remove it. Then all gcd-s still need to be increasing, so the property that maximum is on one of the edges still holds. Suppose our original maximum was on the right. Then we can reverse the array. So when we remove maximum, we always remove the first element. If we wouldn't erase maximums, just reverse the suffix if the first element of that suffix is less than its last. Nothing changed and our array is non-increasing
oh i got it ty
what's wrong with this solution for C2 submission link
problems were really nice and these long explainations were really nice too
but why sohag is loving niumber theory so much
You wrote good editorial for beginners. It is great to see that you are showing how to think on the problems.
The solution to problem C2 is really confusing.
I have an another thought of that.
Let $$$x' = 2^k$$$, and $$$\frac{x'}{2} \le x < x'$$$.
For that $$$y \le x'$$$, we could find that the only valid $$$y$$$ satisfy $$$(x \oplus y) \mid y$$$, or $$$x \oplus y$$$ should be over $$$y$$$. So we can bruteforce in $$$[1, x']$$$.
Let $$$n' = 2^t$$$, and $$$n' \le n < 2n'$$$.
Then we can find that, which $$$p$$$ of $$$px \le n'(p \ge 1)$$$, $$$y = px \oplus x$$$ could be satisfy $$$y \le n$$$. So we can easily calculate it by $$$\left\lfloor\frac{x'}{x'}\right\rfloor / x - 1$$$.
And for that over $$$n'$$$, bruteforce again.
You can read my code to summary that.
293451693
还是我太菜了
in problem A instead of bugging in maths deeply just try to think easily that what should be value of a1 that modulus with 1 comes 0 what should be the value of a2 that modulus with 2 comes 1 ,what should the value of a3 that modulus with 3 produce 2- you will get your ans sequence of odd numbers starting from 1 to 99 will be our ans i.e 2*i+1 upto n.thanks open to discussion