Editorial of CodeTON Round 9 (Div. 1 + Div. 2)

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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.

How did you find the contest?

Which problem is your most favourite?

Which problem you hate the most?

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

2039A - Shohag Loves Mod

Author: YouKn0wWho

Tutorial

Code

#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;
}

Rate the Problem

2039B - Shohag Loves Strings

Author: YouKn0wWho

Tutorial

Code

#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;
}

Rate the Problem

2039C1 - Shohag Loves XOR (Easy Version)

Author: YouKn0wWho

Tutorial

Code

#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;
}

Rate the Problem

2039C2 - Shohag Loves XOR (Hard Version)

Author: YouKn0wWho

Tutorial

Code

#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;
}

Rate the Problem

2039D - Shohag Loves GCD

Author: YouKn0wWho

Tutorial

Code (Solution 1)

#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;
}

Code (Solution 2)

#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;
}

Rate the Problem

2039E - Shohag Loves Inversions

Author: YouKn0wWho

Tutorial

Code

#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;
}

Code (by wyrqwq, without initial casework)

#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; }

Rate the Problem

2039F1 - Shohag Loves Counting (Easy Version)

Author: YouKn0wWho

Tutorial

Code (by LipArcanjo)

#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;
}

Rate the Problem

2039F2 - Shohag Loves Counting (Hard Version)

Author: YouKn0wWho

Tutorial

Code (unoptimized)

#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;
}

Code (optimized)

#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;
}

Rate the Problem

2039G - Shohag Loves Pebae

Author: YouKn0wWho

Tutorial

Code

#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;
}

Rate the Problem

2039H1 - Cool Swap Walk (Easy Version)

Author: wuhudsm

Tutorial

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

$$$ (x, x) \rightarrow (x, x+1) \rightarrow (x+1, x+1) $$$

This move transforms $$$[\ldots,a_x, a_{x+1},\ldots]$$$ into $$$[\ldots,a_{x+1}, a_{x},\ldots]$$$.

Move 2

$$$ (x, x) \rightarrow (x, x+1) \rightarrow (x, x+2) \rightarrow (x+1, x+2) \rightarrow (x+2, x+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:

$$$ (1, 1) \rightarrow (1, p_1) \rightarrow (p_1, p_1) \rightarrow (p_1, n) \rightarrow (n, n) $$$

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:

$$$ (1, 1) \rightarrow (1, n) \rightarrow (n, n) $$$

This sequence transforms the array as follows:

$$$ [a_1, a_2, \dots, a_n(a_n=mn)] \rightarrow [a'_1, a'_2, \dots, a'_n]=[a_n, a_{n-1}, a_1, a_2, \dots, a_{n-2}] $$$

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.

Code

#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;
}

Rate the Problem

2039H2 - Cool Swap Walk (Hard Version)

Author: wuhudsm

Tutorial

Code

#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;
}

Rate the Problem

Comments (32)

Write comment?

Tsar1453

2 hours ago, # |

Even after solving A,B my rating went from 999 to 994 why?

→ Reply

HarshitKumarGupta

2 hours ago, # ^ |

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.

117 minutes ago, # ^ |

Oh! Okay I guess I have to grind more to reach pupil

Mhn_Neek

+49

This round was a peace of shit

shiinamashiro_

+16

can't be said better

Pa_sha

Why? Looks like really good round for me

eternal_happiness

112 minutes ago, # ^ |

+17

probably related to the fact that E was oeis-able

methanol

84 minutes ago, # ^ |

Yeah that's sad. I think it is a good problem otherwise

Asuna_Yuuki

118 minutes ago, # ^ |

+11

PaciukZvichainyi

107 minutes ago, # ^ |

← Rev. 2 →

Personally, I didn't like this contest because half of the problems involve gcd, half of the problems involve combinatorics, and half of the problems involve gcd + combinatorics.

FellingRain

95 minutes ago, # ^ |

Alireza_OLY

91 minute(s) ago, # ^ |

can't agree more Got 1599 for this ...

amirhanordobaev

Bitmask + XOR = Pain

tafsiruzzaman

118 minutes ago, # |

Shohag Loves Bitmasks :')

Leonardo_Paes

113 minutes ago, # |

Shohag loves OEIS (specially A079752)

Gromp16

bro changed all the bad downvotes to average, disgusting

vudinhlongg

111 minutes ago, # |

_LonggVuz. bitmasks almost killed me, the problem D saved my rating ._.

Benq

89 minutes ago, # |

← Rev. 3 →

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. :(

Pyqe

5 minutes ago, # ^ |

I agree. It's a cool problem but the time limit is too tight

Dominater069

84 minutes ago, # |

I liked B, C1, C2, E. Thanks for the round. H also looks interesting

the_last_smilodon

71 minute(s) ago, # |

Anyone else solved C2 using binary search ? 😂 😂

risingStark

24 minutes ago, # ^ |

I did. I found the highest y <= m, such that x^y is a multiple of x.

Russian_Chessist

67 minutes ago, # |

What's the approximate rating of D?

gaspar.kristijan

52 minutes ago, # ^ |

https://clist.by/problems/

Here you can see approximate ratings of all problems

Stalin67

13 minutes ago, # ^ |

Probably 1800 to 1900.

Cuellius

61 minute(s) ago, # |

+13

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 use FindSequenceFunction to obtain the solution:

FindSequenceFunction[{0, 1, 2, 5, 19, 102, 682, 5321, 47071, 464570, 
  5057058, 60166913, 776595027}]

It gives the answer:

DifferenceRoot[Function[{y, n}, 
    {1 + (2 + n)*y[n] + (-3 - n)*y[1 + n] + 
          y[2 + n] == 0, y[1] == 0, y[2] == 1, y[3] == 2}]]

It is the recurrence relation, which can be simply coded: 292998575.

YouKn0wWho

47 minutes ago, # |

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!

17 minutes ago, # |

Why Shohag loves so much number theory, although problems are really good.

dsarules

13 minutes ago, # |

Bro how does D have more solves than C2

Aziz.Ammourah

8 minutes ago, # |

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 ?

arvindf232

3 minutes ago, # |

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.

real.emerald

2 minutes ago, # |

There's a cute solution to D.

Let cnt(x) be the number of divisors of x, not including 1 and x.

Then, set answer[i] to be equal to S[m - x].

That's it :)

And if the index is ever negative, then output -1.

The reasoning stems from the same thoughts as the editorial, though I am too tired to write out a formal proof.

YouKn0wWho's blog