## 1152A - Neko Finds Grapes

Author: xuanquang1999

Development: xuanquang1999, Akikaze, GreenGrape

Theme development: Akikaze, GreenGrape

Editorialist: xuanquang1999

**Tutorial**

**Solution (xuanquang1999)**

Submission link: 53259456

**Source code in plain text**

```
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char* argv[])
{
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(n), b(m);
for(int i = 0; i < n; ++i)
scanf("%d", &a[i]);
for(int i = 0; i < m; ++i)
scanf("%d", &b[i]);
int c0 = 0, c1 = 0;
for(int i = 0; i < n; ++i)
if (a[i]%2 == 0)
++c0;
else
++c1;
int k0 = 0, k1 = 0;
for(int i = 0; i < m; ++i)
if (b[i]%2 == 0)
++k0;
else
++k1;
int ans = min(c1, k0) + min(c0, k1);
printf("%d", ans);
return 0;
}
```

## 1152B - Neko Performs Cat Furrier Transform

Author: Akikaze

Development: Akikaze, xuanquang1999

Theme development: Akikaze

Editorialist: Akikaze

**Tutorial**

**Solution 1 - Greedy (Akikaze)**

Submission link: 53259692

**Source code in plain text**

```
#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int x;
bool isCompletion(int z) {
int bitval = 0;
z += 1; while (z % 2 == 0) {z /= 2; bitval++;}
return (z == 1);
}
int MSB(int z) {
for (int i=20; i>=0; i--) {
if ((z >> i) & 1) return i;
}
return -1;
}
void Input() {
cin >> x;
}
void Solve() {
int i = 0; vector<int> xorCmd;
while (!isCompletion(x)) {
i = i + 1;
if (i % 2 == 0) {x++; continue;}
int r = MSB(x);
if ((1 << r) != x) r++;
x = (x ^ ((1 << r) - 1)); xorCmd.push_back(r);
}
cout << i << endl;
for (auto z: xorCmd) cout << z << " "; cout << endl;
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(NULL); Input(); Solve();
return 0;
}
```

**Solution 2 - BFS (Akikaze)**

Submission link: 53259743

**Source code in plain text**

```
#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int x; vector<vector<int>> vis(2, vector<int>(1048576, INT_MAX));
vector<vector<pair<int, int>>> Last(2, vector<pair<int, int>>(1048576, {-1LL, -1LL}));
int isCompletion(int z) {
int bitval = 0;
z += 1; while (z % 2 == 0) {z /= 2; bitval++;}
if (z != 1) return -1;
return bitval;
}
void Input() {
cin >> x;
}
void Solve() {
queue<pair<int, int>> Q;
vis[0][x] = 0; Q.push({0, x});
int p1 = -1, p2 = -1;
while (!Q.empty()) {
pair<int, int> Token = Q.front();
int p = Token.first, z = Token.second; Q.pop();
if (isCompletion(z) != -1) {p1 = p; p2 = z; break;}
if (p == 1) {
if (vis[0][z+1] == INT_MAX) {
vis[0][z+1] = vis[1][z] + 1;
Last[0][z+1] = {1, z}; Q.push({0, z+1});
}
}
else {
for (int i=0; i<20; i++) {
int t = (z ^ ((1 << i) - 1));
if (vis[1][t] != INT_MAX) continue;
vis[1][t] = vis[0][z] + 1;
Last[1][t] = {0, z}; Q.push({1, t});
}
}
}
cout << vis[p1][p2] << endl;
vector<int> xorCmd;
while (Last[p1][p2] != make_pair(-1, -1)) {
pair<int, int> Token = Last[p1][p2];
int z = Token.first, t = Token.second;
if (p1 == 1) xorCmd.push_back(isCompletion(p2 ^ t));
p1 = z; p2 = t;
}
reverse(xorCmd.begin(), xorCmd.end());
for (auto z: xorCmd) cout << z << " ";
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(NULL); Input(); Solve();
return 0;
}
```

## 1152C - Neko does Maths

Author: stefdasca

Development: stefdasca, Akikaze

Theme development: xuanquang1999, neko_nyaaaaaaaaaaaaaaaaa

Editorialist: stefdasca

**Tutorial**

**Solution (implemented by stefdasca)**

Submission link: 53259956

**Source code in plain text**

```
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand_seed()
{
long long a = rng();
return a;
}
long long a, b;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b;
long long dif = abs(a - b);
vector<int>v;
for(int i = 1; i * i <= dif; ++i)
{
if(dif % i == 0)
{
v.push_back(i);
if(i * i != dif)
v.push_back(dif / i);
}
}
long long ans = (1LL<<62);
int vl = 0;
sort(v.begin(), v.end());
for(int i = 0; i < v.size(); ++i)
{
int nr = v[i];
if(a % nr != b % nr)
continue;
if(a % nr == 0)
{
long long pans = (a * b)/__gcd(a, b);
if(pans < ans)
ans = pans, vl = 0;
}
else
{
long long pans = ((nr - a % nr + a) * (nr - b % nr + b))/__gcd((nr - a % nr + a), (nr - b % nr + b));
if(pans < ans)
ans = pans, vl = nr - a % nr;
}
}
cout << vl;
return 0;
}
```

**Solution (implemented by Akikaze)**

Submission link: 53270277

**Source code in plain text**

```
#pragma comment(linker, "/stack:247474112")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int a, b;
void Input() {
cin >> a >> b;
}
void Solve() {
if (a == b) {cout << "0\n"; return;}
vector<int> Divisors;
for (int i=1; i<=sqrt(max(a,b) - min(a,b)); i++) {
if ((max(a,b) - min(a,b)) % i != 0) continue;
int j = (max(a,b) - min(a,b)) / i;
Divisors.push_back(i);
if (i != j) Divisors.push_back(j);
}
pair<long long, int> Token = make_pair(LLONG_MAX, INT_MAX);
for (auto d: Divisors) {
int k = (d - a % d) % d;
pair<long long, int> NewToken = make_pair(1LL * (0LL + a + k) / __gcd(0LL+a+k, 0LL+b+k) * (0LL + b + k), k);
Token = min(Token, NewToken);
}
cout << Token.second << endl;
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(NULL); Input(); Solve();
return 0;
}
```

## 1152D - Neko and Aki's Prank

Author: cdkrot

Development: cdkrot

Theme development: xuanquang1999

Editorialist: cdkrot

**Tutorial**

**Solution (_kun_)**

Submission link: 53260068

**Source code in plain text**

```
// Dmitry _kun_ Sayutin (2019)
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::cerr;
using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;
using std::pair;
using std::make_pair;
using std::tuple;
using std::make_tuple;
using std::get;
using std::min;
using std::abs;
using std::max;
using std::swap;
using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;
#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif
template <typename T>
T input() {
T res;
cin >> res;
LASSERT(cin);
return res;
}
template <typename IT>
void input_seq(IT b, IT e) {
std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}
#define SZ(vec) int((vec).size())
#define ALL(data) data.begin(),data.end()
#define RALL(data) data.rbegin(),data.rend()
#define TYPEMAX(type) std::numeric_limits<type>::max()
#define TYPEMIN(type) std::numeric_limits<type>::min()
const int mod = 1000 * 1000 * 1000 + 7;
int add(int a, int b) {
return (a + b >= mod ? a + b - mod : a + b);
}
const int max_n = 1001;
pair<int, bool> dp[2 * max_n][2 * max_n];
int main() {
std::iostream::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// code here
int n = input<int>();
n *= 2;
assert(n / 2 < max_n);
dp[0][0] = make_pair(0, true);
for (int len = 1; len <= n; ++len) {
for (int bal = 0; bal <= n; ++bal) {
// (len, bal) -> (len - 1, bal + 1)
// (len, bal) -> (len - 1, bal - 1)
int sum = 0;
bool has = false;
if (bal != 0) {
sum = add(sum, dp[len - 1][bal - 1].first);
has = has or dp[len - 1][bal - 1].second;
}
if (bal + 1 <= len - 1) {
sum = add(sum, dp[len - 1][bal + 1].first);
has = has or dp[len - 1][bal + 1].second;
}
if (has)
dp[len][bal] = make_pair(add(sum, 1), false);
else
dp[len][bal] = make_pair(sum, true);
}
}
cout << dp[n][0].first << "\n";
return 0;
}
```

## 1152E - Neko and Flashback

Author: xuanquang1999

Development: xuanquang1999

Theme development: xuanquang1999

Editorialist: xuanquang1999

**Tutorial**

**Solution (xuanquang1999)**

Submission link: 53260100

**Source code in plain text**

```
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
class Indexer {
private:
map<int, int> id;
vector<int> num;
public:
int getId(int x) {
if (!id.count(x)) {
id[x] = num.size();
num.push_back(x);
}
return id[x];
}
int getNum(int id) {
return num[id];
}
int size() {
return id.size();
}
};
struct Edge {
int u, v;
bool avail;
};
class Graph {
private:
int n;
vector<Edge> e;
vector<vector<int> > adj;
vector<int> pos;
list<int> path;
void dfs(list<int>::iterator it, int u) {
for(; pos[u] < adj[u].size(); ++pos[u]) {
int id = adj[u][pos[u]];
if (e[id].avail) {
e[id].avail = false;
int v = e[id].u + e[id].v - u;
dfs(path.insert(it, u), v);
}
}
}
public:
Graph(int n): n(n) {
adj.assign(n, vector<int>());
}
void addEdge(int u, int v) {
adj[u].push_back(e.size());
adj[v].push_back(e.size());
e.push_back({u, v, false});
}
vector<int> eulerPath() {
for(Edge &p: e)
p.avail = true;
path.clear();
pos.assign(n, 0);
vector<int> odd;
for(int u = 0; u < n; ++u)
if (adj[u].size() % 2 == 1)
odd.push_back(u);
if (odd.empty()) {
odd.push_back(0);
odd.push_back(0);
}
if (odd.size() > 2)
return vector<int>();
dfs(path.begin(), odd[0]);
path.insert(path.begin(), odd[1]);
return vector<int>(path.begin(), path.end());
}
};
int main() {
int n;
scanf("%d", &n);
vector<int> bprime(n-1);
for(int i = 0; i < n-1; ++i)
scanf("%d", &bprime[i]);
vector<int> cprime(n-1);
for(int i = 0; i < n-1; ++i)
scanf("%d", &cprime[i]);
Indexer ind;
for(int i = 0; i < n-1; ++i) {
if (bprime[i] > cprime[i]) {
puts("-1");
return 0;
}
bprime[i] = ind.getId(bprime[i]);
cprime[i] = ind.getId(cprime[i]);
}
int k = ind.size();
Graph g(k);
for(int i = 0; i < n-1; ++i)
g.addEdge(bprime[i], cprime[i]);
vector<int> a = g.eulerPath();
if (a.size() < n)
puts("-1");
else {
for(int i = 0; i < n; ++i)
printf("%d ", ind.getNum(a[i]));
puts("");
}
return 0;
}
```

## 1152F1 - Neko Rules the Catniverse (Small Version)

## 1152F2 - Neko Rules the Catniverse (Large Version)

Author: MofK

Development: MofK, xuanquang1999, Akikaze

Theme development: xuanquang1999, Akikaze

Editorialist: MofK, Akikaze

**Tutorial - F1 (Small version)**

**Tutorial - F2 (Large version)**

**Solution F1 (xuanquang1999)**

Submission link: 53260139

**Source code in plain text**

```
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
void add(int &a, long long b) {
a = (a + b) % MOD;
}
int main() {
int n, k, m;
scanf("%d%d%d", &n, &k, &m);
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(k+1, vector<int>(1<<m, 0)));
dp[0][0][0] = 1;
for(int i = 0; i < n; ++i) {
for(int j = 0; j <= k; ++j) {
for(int mask = 0; mask < (1<<m); ++mask) {
int newMask = (mask << 1) % (1<<m);
// Not visit planet i+1
add(dp[i+1][j][newMask], dp[i][j][mask]);
// Visit planet i+1
if (j < k) {
int insertWays = __builtin_popcount(mask) + 1;
add(dp[i+1][j+1][newMask|1], 1LL*insertWays*dp[i][j][mask]);
}
}
}
}
int ans = 0;
for(int mask = 0; mask < (1<<m); ++mask)
add(ans, dp[n][k][mask]);
printf("%d", ans);
}
```

**Solution F2 (xuanquang1999)**

Submission link: 53260164

**Source code in plain text**

```
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
void add(int &a, long long b) {
a = (a + b) % MOD;
}
struct Matrix {
vector<vector<int>> a;
int n, m;
Matrix(int n, int m): n(n), m(m) {
a.assign(n, vector<int>(m, 0));
}
friend Matrix operator * (Matrix a, Matrix b) {
Matrix c(a.n, b.m);
for(int i = 0; i < a.n; ++i)
for(int j = 0; j < b.m; ++j)
for(int k = 0; k < a.m; ++k)
add(c.a[i][j], 1LL * a.a[i][k] * b.a[k][j]);
return c;
}
};
Matrix identity(int n) {
Matrix res(n, n);
for(int i = 0; i < n; ++i)
res.a[i][i] = 1;
return res;
}
void power(Matrix &a, int n, Matrix &b) {
while (n > 0) {
if (n&1) b = a * b;
a = a * a;
n >>= 1;
}
}
int n, k, m;
int toId(int j, int mask) {
return j * (1<<m) + mask;
}
int main() {
scanf("%d%d%d", &n, &k, &m);
Matrix dp((k+1) * (1<<m), 1);
dp.a[0][0] = 1;
Matrix f((k+1) * (1<<m), (k+1) * (1<<m));
for(int j = 0; j <= k; ++j) {
for(int mask = 0; mask < (1<<m); ++mask) {
int newMask = (mask << 1) % (1<<m);
int cur = toId(j, mask);
f.a[toId(j, newMask)][cur] = 1;
if (j < k)
f.a[toId(j+1, newMask|1)][cur] = __builtin_popcount(mask) + 1;
}
}
power(f, n, dp);
int ans = 0;
for(int mask = 0; mask < (1<<m); ++mask)
add(ans, dp.a[toId(k, mask)][0]);
printf("%d", ans);
}
```

**Solution F2 (veryheckingfast by MofK)**

Submission link: 53260183

**Source code in plain text**

```
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
void add(long long &a, long long b) {
a = (a + b) % mod;
}
long long f[2][1005][1024];
int pc[1024];
long long solve(int n, int k, int m) {
memset(f, 0, sizeof f);
f[0][0][0] = 1;
for (int i = 0; i < n; ++i) {
int x = i & 1, y = 1 - x;
memset(f[y], 0, sizeof f[y]);
for (int j = 0; j <= k; ++j) {
for (int mask = 0; mask < (1 << m); ++mask) {
int new_mask = mask >> 1;
add(f[y][j][new_mask], f[x][j][mask]);
add(f[y][j+1][new_mask + (1<<m-1)], f[x][j][mask] * (pc[mask] + 1));
}
}
}
long long ret = 0;
for (int mask = 0; mask < (1 << m); ++mask)
add(ret, f[n&1][k][mask]);
return ret;
}
typedef vector <vector <long long>> mat;
mat operator *(const mat &a, const mat &b) {
mat c(a.size(), vector <long long>(b[0].size(), 0));
for (int i = 0; i < a.size(); ++i)
for (int j = 0; j < b.size(); ++j)
for (int k = 0; k < b[0].size(); ++k)
add(c[i][k], a[i][j] * b[j][k]);
return c;
}
mat operator +(const mat &a, const mat &b) {
mat c = a;
for (int i = 0; i < a.size(); ++i)
for (int j = 0; j < a[0].size(); ++j)
add(c[i][j], b[i][j]);
return c;
}
mat A(int m) {
mat a(1 << m, vector <long long>(1 << m, 0));
for (int i = 0; i < (1 << m - 1); ++i)
a[i][i*2] = a[i][i*2 + 1] = 1;
return a;
}
mat B(int m) {
mat b(1 << m, vector <long long>(1 << m, 0));
for (int i = 0; i < (1 << m - 1); ++i) {
b[i + (1<<m-1)][i*2] = pc[i] + 1;
b[i + (1<<m-1)][i*2 + 1] = pc[i] + 2;
}
return b;
}
mat U(int m) {
mat u(1 << m, vector <long long>(1 << m, 0));
for (int i = 0; i < (1 << m); ++i)
u[i][i] = 1;
return u;
}
mat O(int m) {
return mat(1 << m, vector <long long>(1 << m, 0));
}
void convo(vector <mat> &a, vector <mat> b, int m, int k) {
int sz = min(k + 1, (int)(a.size() + b.size() + 1));
a.resize(sz, O(m));
for (int i = sz - 1; i >= 0; --i) {
a[i] = a[i] * b[0];
for (int j = 1; j <= i && j < b.size(); ++j)
a[i] = a[i] + a[i-j] * b[j];
}
}
long long solve3(int n, int k, int m) {
vector <mat> ans, mul;
--n;
ans = mul = {A(m), B(m)};
while (n) {
if (n & 1) convo(ans, mul, m, k);
convo(mul, mul, m, k);
n >>= 1;
}
long long ret = 0;
for (int i = 0; i < (1 << m); ++i)
add(ret, ans[k][i][0]);
return ret;
}
int main(void) {
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
int n, k, m;
for (int i = 1; i < 1024; ++i) pc[i] = pc[i - (i&-i)] + 1;
while (cin >> n >> k >> m)
cout << solve3(n, k, m) << endl;
return 0;
}
```

**Bonus**

Solve the problem in (or faster than) $$$\mathcal{O} \left( \log(n) \cdot k^2 \cdot {\left( 2^m \right)}^3 \right)$$$.

**Authors' logs (miscellaneous things during our preparations)**

**Log-1**

You said tomorrow, isn't it? Anyway thanks for an awesome contest and a fast editorial. Keep up the great work.

I felt things are nearly complete, so there's no need to actually wait for a day. ;)

Akikaze During the contest I too thought that making the gcd as large as possible might be optimal but we have to minimise the lcm which is equal to product of 2 numbers divided by the gcd. How does maximising the gcd ensures minimum lcm. In the process of maximising the gcd we are also incresing the numbers. Then how is this optimal. What is the mathematical proof for this

You can check my explanation here, many people are getting this wrong idea.

okieeee

Can anyone please let me know how 5 0 7 15 is not the right answer for sample test case 1 of B? It results in 63 as per my calculation. I'm surely missing something.

You need to print

`n`

such that`x`

is xor-ed with`2^n - 1`

, but you are printing`2^n - 1`

.Thanks a lot.

Why does $$$\gcd(a+k,b+k) = \gcd(a+k,b-a)$$$?

Because of the Euclidean Algorithm, if we subtract the smaller number from the larger number the GCD remains the same.

One common way of understanding $$$\gcd(a,b)$$$ is connecting it to the set of all numbers you can make by adding or subtracting $$$a$$$ and $$$b$$$. $$$\gcd(a,b)$$$ can be interpreted as the smallest strictly positive number in this set.

So the question, is $$$\gcd(a+k,b+k) \stackrel{?}{=} \gcd(a+k,b-a)$$$, can simply be answered by noting that they both form the same set. This is true as $$$(a+k) + (b-a) = (b+k)$$$.

Can you explain how iterating the divisor of b-a will lead me to the solution ?

First observation is $$$LCM({a+k},{b+k})=\dfrac{(a+k)\times (b+k)}{GCD({a+k},{b+k})}$$$.

What to do with $$$|b-a|$$$? Basically let $$$g$$$ be $$$GCD({a+k},{b+k})$$$. You then have $$$a+k=x\times g$$$ and $$$b+k=y\times g$$$ ($$$x$$$ and $$$y$$$ are some integers), which means $$$b-a=(y-x)\times g$$$, so $$$g$$$ is a divisor of $$$|b-a|$$$ (we can exclude the case that $$$x=y$$$).

That means with an arbitrary value of $$$k$$$, $$$GCD({a+k},{b+k})$$$ must be a divisor of $$$|b-a|$$$. Thus you don't need to examine all the values of $$$k$$$ since there are finite values of divisors of $$$|b-a|$$$. Instead just focus on finding minimal $$$k$$$ based on our finite divisor set of $$$|b-a|$$$, which are the set of potential $$$GCD({a+k},{b+k})$$$.

With each divisor $$$d$$$ of $$$|b-a|$$$, you can calculate $$$k$$$ by considering $$$d=GCD({a+k},{b+k})$$$ and update the result. However I pass this with another way. I calculate $$$k$$$ by considering $$$d$$$ as the divisor of both $$$a+k$$$ and $$$b+k$$$. Don't know why it passed, maybe I missed something :\

EDIT: Maybe I know why I passed with the other way. Since I consider $$$d$$$ as the divisor of both $$$a+k$$$ and $$$b+k$$$, the $$$k$$$ I calculated surely makes $$$GCD({a+k},{b+k})$$$ not smaller than $$$d$$$. As $$$k$$$ is the minimal to makes $$$d$$$ the divisor of both $$$a+k$$$ and $$$b+k$$$, if you want $$$d$$$ to become $$$GCD({a+k},{b+k})$$$ (if it hasn't been), you need to raise $$$k$$$ to a value $$$k'$$$ which is not smaller than $$$k$$$. Now of course $$$\dfrac{(a+k)\times (b+k)}{GCD({a+k},{b+k})}$$$ is smaller than $$$\dfrac{(a+k')\times (b+k')}{d}$$$, which means we get a better result.

Damn those revisions.

Yeah, I was also confused in the last part that even after considering $$$d$$$ as divisor NOT $$$gcd$$$, the answer remains correct. This hasn't been explained in the editorial but is really an intricate fact. Thank you for sharing it!

Firstly, define $$$d=\gcd(a+k,b+k)$$$.Then it's easy to know that $$$a+k=da',b+k=db'(a',b'\in\mathbb{N_+})$$$. Therefore $$$d|((b+k)-(a+k))=d(b'-a')$$$, $$$\gcd(a+k,b+k)$$$ should be the divisor of $$$b-a$$$.

Secondly, because $$$\text{lcm}(a+k,b+k)=\frac{(a+k)(b+k)}{\gcd(a+k,b+k)}$$$, therefore if $$$\gcd(a+k,b+k)$$$ is known, $$$a+k$$$ and $$$b+k$$$ should be minimum as possible to make least common multiple be minimum as possible, it's not hard to know that $$$a+k=\lceil\frac{a}{d}\rceil d$$$ and $$$b+k=\lceil\frac{b}{d}\rceil d$$$.

All in all, we can enumerate all divisors of $$$b-a$$$ to get all possible answers, and the solution is in them.

Ok i understand till this part that for every divisor

di have to find smallest value of k such that ** gcd(a+k,b+k) = d** . How can i proceed further ?After you find the smallest $$$k$$$, just calculate the least common multiple of $$$a+k$$$ and $$$b+k$$$. The solution has minimum $$$\text{lcm}(a+k,b+k)$$$ and smallest value of $$$k$$$.

This is my code.

53264271

How is a+k = ceil(a/d) * d? (where d is the gcd(a+k, b+k) as you mentioned.

Also, in the editorial author says k = q-a%q. How is that? (q is the divisor of (b-a) here)

Note that

`a + k = ceil(a / d) * d`

has a lot (infinite number) of possible k that satisfies the equation but we need a minimum value from them (with k>=0 at the same time), so we take the minimum value greater than`a`

that is a divisor of d. For example, for`d = 3`

and`a = 6`

k would be 0 because`ceil(a / d)*d = a`

, for`a = 7, d = 3`

k would be 2. The same logic applies in the editorial. Consider some x such that x*q is the greatest value less than a. So it is clear that`x * q <= a <= x * q + q`

. There are 2 possible variants: 1)`a = x * q`

, then k = 0. 2)`a != x * q`

. So a is somewhere between. We are to find such k that`a + k = x * q + q`

. How do we? Well, we already could iterate for all x starting from zero until we get k>=0, but what else we could do is to find`m = a - x * q`

which is`a % q`

by definition. With this m and the total length of the interval`x * q + q - x * q = q`

, we calculate the other part as`k = q - m`

, so`k = q - a % q`

.Thank you so much! I couldn't have asked for a better explanation. This also helped me develop a much better understanding of modulo operations. :)

From Euclid's theorem,

`gcd(a, b) = gcd(b%a, a)`

Now let

`b >= a`

and`x = b - a`

, then`b = a + x`

Take

`gcd(a + k, b + k)`

, which will be`= gcd((b + k) % (a + k) , (a + k))`

`= gcd((a + x + k) % (a + k) , (a + k))`

`= gcd(x, (a + k))`

`= gcd(b - a, a + k)`

if (x==y) gcd(x,y)=x; if (x>y) gcd(x,y)= gcd(x-y,y); if (x<y) gcd(x,y)= gcd(x,y-x)。

Can someone explain this statement for C ? "For each divisor q of b−a, we can use it only if a%q=b%q, therefore adding 0 if a%q=0 and q−a%q otherwise. "

if

`a%q=b%q`

you can add k to each other and make those numbers divisible by q`(a+k)%q == 0 && (b+k)%q == 0`

k is either 0 or q-(a%q)

i dont get this part

`minimize lcm(a+k,b+k), this means that we're going to make gcd(a+k,b+k) as big as possible.`

can anybody help me? why is this true?That's because lcm(a, b) == (a*b) / gcd(a, b) So if gcd is bigger it means the lcm is going to be smaller

you mean k is fixed right? when then gcd means greatest common divisor.. how can we get different value of gcd(x,y)

when we iterate through k ...

there's counter example ( i guess...)

(no offense..)

i'm also confused by the first statement in the editorial but in your example

at k=2

lcm(5,3)=15, gcd(5,3)=1

So I guess it still holds that gcd is minimized at maximum lcm for this example

Maximizing GCD is not the optimal solution — like your example shows.

The steps to get to

`gcd(a + k, |b - a|)`

are pretty clear in above comments. So now you need to find it's value. It's a divisor of |b — a| for sure, and all divisors of this number are pretty easy to find.Given this, you iterate through divisors

dof |b — a|. That may be the most important part I am seeing a lot of people miss. You need to testdas the denominator. Because`d = gcd(a + k, |b - a|)`

forsomed(it not only divides |b — a|, butalso divides (a + k)), we need to change the numbers on the numerator:`(a + (d - a%d))`

and`(b + (d - b%d))`

to make it divisible through addition. This is a very simple step, since we are addingdto a number and removing the necessary amount for it to be divisible.Now, before assigning anything to your answer, check: The obtained LCM (adding

`k = (d - a%d)`

to bothaandb) is smaller than the already stored one? If it is, update it's valueandstore the just used k. If it's equal, you can update the stored kifthe k just used is smaller. That's pretty much everything.Notice that assigning either

`(d - a%d)`

or`(d - b%d)`

to your stored k is the same thing, because since we know thatd| (b + k) andd| (a + k) , then`a mod d = b mod d`

. This is a great step to dwell on if you haven't realized the whole thing yet. You will se a lot of submissions going with`(a + (d - a%d)) * (b + (d - a%d)) [...]`

(notice how a%d is used on both).I was frustrated with this problem during the contest due to all the little things you can easily get tangled on. I hope I didn't mess up my explanation at any point and that you are left with no doubts.

Thanks a lot for the explanation. It clarified all my doubts

Thanks a lot!

let's a=1924 , b = 5834 then b-a = 3910 Also Maximum gcd possible is 3910 But when taking gcd = 3910 , lcm = 7820 ans taking gcd = 1955 , lcm = 5865 . Also in general maximum divisor of (b-a) is (b-a) itself then why we have to iterate over divisors of b-a to get minimum lcm .

Because

`lcm(a+k,b+k) = (a+k)*(b+k)/gcd(a+k,b+k)`

. You are maximising denominaor, but note that lcm depends on numerator also, as k are present both in denominaor as well as numerator.I am confused too....

That part seems to be incorrect.What we should do is to try all divisors of $$$b-a$$$ and find the minimum lcm.

In problem F: The statement says that if you are at current planet x, you can move to planet y <= x + m.

For N = 100000, m =4 If we start at planet x = 500 we can move to planet 504, then from that planet to 508, then 512, 516, 520 etc.

However, the solutions assume that if we start at planet x = 500, We can never make any moves beyond 504, that doesn't apply just for the next move. so we can go to planet 504, but we will never be allowed to move to 505 and beyond. If we move ever move, for example to 490, then after reaching node 490, we don't be allowed to go to 495 and above.

Is this a translation issue, is Russian version of this problem different than english?

No, we do allow to make moves beyond 504, and our solution handles that.

The idea is to insert the planets in decreasing order into the path; it is possible that we first insert 508, then insert 504 before 508, then 500 before 504, which gives the path 500-504-508.

Sorry if any part of the solution confuses you. Hope this clears.

Thanks, I understand it now.

Hey can you pls reply to this comment on this blog. The moderator doesn't seem to reply https://codeforces.com/blog/entry/66696?#comment-507718

For problem A there is no need to define vector space. Directly read a variable and update counter values.

Can anyone explain how MSB(4) = MSB(7) = 2 in question no. 2.

Keep in mind that the most significant bit is the leftmost $$$1$$$ bit of a number written in binary form.When writing the numbers in binary form, we can see that:

and:

If we start counting the exponential of each bit from $$$0$$$ and from the right to the left, we can see that the most significant bit of both cases is the $$$2$$$nd rightmost bit ($$$3$$$rd actually, but again we're counting from $$$0$$$).

Thus, $$$MSB(4) = MSB(7) = 2$$$.

I do not understand the problem D Can someone elaborate to me what this means

"Aki then came up with an interesting problem: What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie?"Just in case, you should read the definition of a trie and maximum matching of a graph.

Generally, a trie is a tree, and as a result, could be considered as a graph (but with a few special attributes) and had some other attributes, including maximum matching.

P/s: Still I think the sentence did quite a good job in explaining the task though.

Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).For problem C, for every divisor q of (b-a) the condition of

`a%q = b%q`

will be true and there is no need for an additional check.Oh, I was overkilling when writing my implementation ;)

Thanks, solution updated. ;)

What is MSB? Could you explain a little bit deeply?(B)

I've written my definition of it right on the tutorial. You can also read this comment.

Then MSB(57)=5 right?

Yes. :)

Found a mistake, a little one. Problem B-> Greedy Solution-> plain text->solve function->while(isCompletion(x)) should be while(!isCompletion(x))

Thanks, fixed. ;)

Problem B Greedy solution. In your loop the third logic with MSB. I can't understand why you would do 2^(MSB(x)+1)−1? What's the logic behind it?

never mind. just understood it. neat one. I was thinking a bit differently. trying to find the leftmost 0 which is after the MSB. Then count its position and xor with 2^(pos+1)-1.

The core idea of this greedy solution is to remove the most significant bit of $$$x$$$ until $$$x$$$ becomes a number of the form we want (well, since even in the worst case, $$$0$$$ is still one correct final value for $$$x$$$).

Assume that we have $$$x$$$ and its $$$MSB(x)$$$. Given the plan I said earlier, we need to find a number to perform operation A to remove that significant bit, without accidentally adding other more significant bits (in case you didn't realize, $$$1 \oplus 1 = 0$$$).

Then, $$$2^{MSB(x)+1} - 1$$$ is a perfect candidate. If you write it out in the binary notation, it consists of $$$MSB(x) + 1$$$ '1' bits, which mean the most significant bit of it is also $$$MSB(x)$$$.

Could you please describe your greedy solution of prob. 2 by an example? Say 39?

I'll just iterate the things as I stated in the tutorial.

Initially, $$$x = 39$$$, neither lower than $$$2$$$ or being of $$$2^m - 1$$$ form.

We'll find its MSB, in this case $$$MSB(x) = MSB(39) = 5$$$.

Thus, we'll choose $$$n = 6$$$, and convert $$$x$$$ into $$$x \oplus (2^6 - 1)$$$ using operation A.

To be precise, $$$x := 39 \oplus 63$$$ or $$$x := 24$$$.

$$$24$$$ is not a correct final number, so we'll perform operation B and return to the beginning of the loop. Now $$$x = 25$$$.

Since $$$25$$$ is also not a correct final number, we'll calculate the MSB again. $$$MSB(x) = MSB(25) = 4$$$.

Perform operation A: $$$x := 25 \oplus (2^4 - 1)$$$ or $$$x := 6$$$.

$$$6$$$ is not a correct number, so we'll perform operation B. Now $$$x = 7$$$.

You can see that $$$7$$$ is a valid number (as $$$7 = 2^3 - 1$$$). Therefore, we stop the loop here.

The output should be:

I have a simpler solution for D(easy to code but hard to understand).

Let $$$f_{i,j}=f_{i-1,j}+f_{i,j-1};f_{1,1}=1$$$,we can easily calc f for $$$j\le i\le n+1$$$in $$$O(n^2)$$$,just use the definition.

Then $$$ans=\sum\limits_{(i+j)\bmod 2=1} f_{i,j}$$$

Now let's explain why it works.

First,here is a way to choose a set of edges which has biggest size:choose all vertices with

evendepth,and choose the edge between each vertex and its father one by one(if its father is stillnot covered).In this way,all vertices withodddepth are covered(theleavesof the trie haveevendepth),and all edegs are between anoddvertex and anevenvertex,so the size of the set has been as big as possible.Now we can see that the ans is equal to

the number of vertices with odd depth,and the solution above just calculates this.Let's think about $$$f$$$,it's easy to see that $$$f_{i,i}$$$ is the i-th Catalan number. As we know,Catalen number equal to the number of correct bracket sequences.And $$$f_{i,j}$$$ equal to the number of bracker swquences which has a lenth of $$$i+j$$$,$$$i$$$ opening brackets and $$$j$$$ closing brackets.So the sum of all $$$f_{i,j},(i+j)\bmod 2=1$$$ is ans we need.

So what's dreamoon_love_AA's solution? I can't understand his dp and combinations. Btw, I was very sleepy and tired during the contest and my rating falls down:(

I have a doubt in problem D.

I wrote a solution to maximize the number of edges using a simple DP with states [1000][1000][2].

The aim was to print (max(number_of_edges)) % mod but apparently the test cases are to maximize(number_of_edges%mod) and not (max(number_of_edges))%mod.

I got WA on case 16 when didn't use mod anywhere but final place. (WA here)

Then I used mod on all the additions and submitted. I did not expect to get a Accepted verdict but I did. (Accepted here)

The Accepted solution is maximizing the modulo-ed value and not finding the maximum edges possible % mod. Please note that these two things are completely different values.

Please look into this. I was confused during the contest of how to find maximum possible edges all at once (as complete answer cannot lie in range of long long int) and then find it's modulo but test cases are to maximizing the modulo-ed value.

Akikaze Please look into this!

We just checked things up again, and the model solution was correct. Maybe the testset could't kill such solutions like your second one (I haven't tried yet actually, MofK even claimed it was even impossible for $$$n \le 1000$$$ due to the atrociously low probability of such to happen).

But still, your first solution won't work, since long long wasn't enough to avoid overflow.

UPD:kun locally tested it forall$$$n$$$ and no counter tests exist for your second solution.Hey!

Yes long long is not enough to prevent the overflow then how can we find the maximum number of leaves without taking mod initially at all? The sample solution takes use of mod before evaluating the final answer and thus how can one know if it works as specified in the question (Take modulo of maximum edges not maximize modulo of number of edges)?

The solution does

notuse any min/max operations, only additions, so it works fine.If you insist on using the standard (take max) solution, comparing them using big integer is the correct way, but you can pass just by using modulo because there's (unsurprisingly) no $$$n \le 1000$$$ such that your solution fails (read my other reply).

Oops! Just read the word dp and assumed they were using standard DP approach. It is a greedy solution so it does work! Thanks for the help. :)

For a rough intuition of why there was no counter-test against your second solution, you can read this comment.

To be fair, we could have killed such solutions if we wanted to, by deliberately choosing a modulo that makes those solutions fail, or including the modulo in the input. But then again it will be unfair because there might be other implementations we are unaware of that avoid this specific counter-test, but fail on other tests.

A close analogy to this situation is: Should we include a test that kills a hash function with modulo $$$10^9 + 7$$$ and base $$$31$$$ just because we can?

Got it! Thanks for the help :D

Killing such solution would mandate the participants to pick on a greedy approach and restrict them from using DP approaches :o

Great thing learnt to enforce greedy :D

Thanks again! :)

I did the same dp as you, and before submitting I realized the mistake.

So I tried to change the dp to not use max, and I was able to do this by leaving the dp kind of greedy.

When you can choose two different sub-trees to place the edge, you can choose the largest subtree, that is, if you have an x quantity of "(" and an y quantity ")" until now, you choose to place the parentheses on the subtree of the minor x or y.

I have not been able to prove formally because it works.

Code

The greedy approach does seem right! Thanks for pointing it out :)

For problem E, I thought that if the number of vertexes whose degree(except for going to oneself) is odd is 2, there is always solution. It was wrong. But I don't know why my thought is wrong. Could anybody explain me?

The graph needs to be connected as well (if you don't count isolated vertices).

!! thank you

I am getting TLE on problem E. Can someone please look into the code. Approach is same as given in editorial.code

Can someone explain the idea of this 53236803 :< Does his dp(i, j) mean number of ways to reach vertex (i, j) ? If it does, so why the ans are the sum of all exist vertices ? P/S : i'm not good at English :v Hope you can understand what i mean :3

`dp[i][j]`

stores the number of nodes at depth`i`

of the trie with the number of opening brackets minus the number of closing brackets equal to`j`

. For the transitions, we can append an opening bracket to the sequence represented by the current nodes and we get a sequence represented by`dp[i + 1][j + 1]`

. If`j`

is positive we can also append a closing bracket which gives us a sequence represented by`dp[i + 1][j - 1]`

. To get the maximum matching, we want to take the edges in every other layer so we take the sum of`dp`

values for every other value of`i`

, excluding the values where`i + j > 2 * n`

because those sequences have too many opening brackets to form a correct bracket sequence of length`2 * n`

.Thank u, I understood. The result is the sum of all odd layers. By someway, I thought it was the sum of both odd and even layers :v

Can someone please explain GRAPH approach (BFS) in 1152B — Neko Performs Cat Furrier Transform .

You can think of an undirected graph, each node is identified by a pair of number $$$(x, parity)$$$, while $$$x$$$ is the current number $$$x$$$, $$$parity$$$ is the parity of the moved that number has gone through: if $$$parity = 0$$$ then the next operation should be operation A, else if $$$parity = 1$$$ then the next operation should be operation B.

Performing xor operations with any bits higher than $$$2^{20}$$$ has no use given the constraints of the problem, therefore the graph will only have $$$2^{21}$$$ nodes.

The edges are drawn as following:

From this point, the graph is complete, and you can do a BFS traverse as normal convention.

Thanks for your awesome tutorial. I think two lines of problem C 's solution by @stefdasca is redundant because it is always a%nr==b%nr. Because nr is divisor of a-b

Extension of Problem E: Drop the condition that b and c have been ordered with the same permutation, i.e. b' and c' represent merely the multiset of all consecutive minimums and maximums, in no particular order. Even though the structural constraint is reduced because now elements on the same index in b' and c' don't have to be generated by the same pair, I think that a greedy construction is still admissable. I wonder if any of you have given it some thought?For problem F, Given fixed values of $$$k, m$$$, the solution $$$f_{k,m}(n)$$$ starting from $$$n \geq k(m+1)$$$ is a polynomial of $$$n$$$ with a rather small degree — at most $$$k$$$. This means that you can use optimized brute-force for small values of $$$n$$$ and then just interpolate. Actually, my brute-force was able to solve any $$$n,k,m$$$ other than $$$k=12, m=4$$$ in under 7 seconds, so I just hardcoded the first 100 values for $$$k=12, m=4$$$ and then interpolated.

Code: 53511773

Nice solution! Actually you can solve for all $$$n$$$ up to $$$k(m+1)$$$ using DP in $$$O(k^2 * m * 2^m)$$$, so this problem can be done for even larger constraints (e.g. $$$k \le 100, m \le 10$$$) than I expected.

Well, this problem was still WIP by the time it was chosen (because something unexpected happened), so I did expect that I may have missed better solutions. But my unfinished idea was very close to this one, so I'm pretty "salty" now :D

can somebody explain the solution to problem D in more detail plz?

For problem D, can anyone explain more in details about the greedy approach? Why does greedy work for this case?

All the leaf nodes have the same depth. So we can do greedy.

Can someone explain D more clearly. Like what is dp[i][j] giving. In tutorial it say's dp[v] is giving no. of edges which we can take in subtree and then it say's we can add a edge upwards. If we are traversing then we should move top to bottom and edge should be added downwards. I am totally confused about what is happening here. Can someone help ?

A more theoretical approach towards problem C , in LCM we tend to find product of distinct factors in the two given numbers initially let d= a-b means if we shift a,b to a number which is multiple of d then we ensure that there are factors those constitute value d thus we can now digress over all the divisors of d keeping a look for the minimum lcm wrt divisor of d

In problem C, can someone help me in understanding the underlying statement:- if some no (x+k) is a multiple of a, then k can be written as a — a % x.

I understand this understand by putting some random values of the variables but is there any mathematical proof thing behind this??

The best editorial ever