Akikaze's blog

By Akikaze, history, 22 months ago,

1152A - Neko Finds Grapes

Author: xuanquang1999
Development: xuanquang1999, Akikaze, GreenGrape
Theme development: Akikaze, GreenGrape
Editorialist: xuanquang1999

Tutorial
Solution (xuanquang1999)

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)

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)

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)

Source code in plain text
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
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)

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_)

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)

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<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) {
}

void addEdge(int u, int v) {
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)

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


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)

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) {
int newMask = (mask << 1) % (1<<m);

// Not visit planet i+1

// Visit planet i+1
if (j < k) {
int insertWays = __builtin_popcount(mask) + 1;
}
}
}
}

int ans = 0;

printf("%d", ans);
}

Solution F2 (xuanquang1999)

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) {
int newMask = (mask << 1) % (1<<m);
int cur = toId(j, mask);

f.a[toId(j, newMask)][cur] = 1;
if (j < k)
}
}

power(f, n, dp);

int ans = 0;

printf("%d", ans);
}

Solution F2 (veryheckingfast by MofK)

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) {
}
}
}
long long ret = 0;
for (int mask = 0; mask < (1 << m); ++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)
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)
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

• +115

 » 22 months ago, # |   +6 You said tomorrow, isn't it? Anyway thanks for an awesome contest and a fast editorial. Keep up the great work.
•  » » 22 months ago, # ^ |   0 I felt things are nearly complete, so there's no need to actually wait for a day. ;)
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +4 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
•  » » » » 22 months ago, # ^ |   0 You can check my explanation here, many people are getting this wrong idea.
•  » » 19 months ago, # ^ |   0 okieeee
 » 22 months ago, # |   0 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.
•  » » 22 months ago, # ^ |   +8 You need to print n such that x is xor-ed with 2^n - 1, but you are printing 2^n - 1.
•  » » » 22 months ago, # ^ |   0 Thanks a lot.
 » 22 months ago, # |   +10 Why does $\gcd(a+k,b+k) = \gcd(a+k,b-a)$?
•  » » 22 months ago, # ^ | ← Rev. 4 →   +6 Because of the Euclidean Algorithm, if we subtract the smaller number from the larger number the GCD remains the same.
•  » » 22 months ago, # ^ |   +18 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)$.
•  » » » 22 months ago, # ^ |   0 Can you explain how iterating the divisor of b-a will lead me to the solution ?
•  » » » » 22 months ago, # ^ | ← Rev. 20 →   +12 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.
•  » » » » » 22 months ago, # ^ |   0 Damn those revisions.
•  » » » » » 22 months ago, # ^ |   0 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!
•  » » » » 22 months ago, # ^ |   +11 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.
•  » » » » » 22 months ago, # ^ |   0 Ok i understand till this part that for every divisor d i have to find smallest value of k such that ** gcd(a+k,b+k) = d** . How can i proceed further ?
•  » » » » » » 22 months ago, # ^ |   0 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$.
•  » » » » » » 22 months ago, # ^ |   0 This is my code.53264271
•  » » » » » 22 months ago, # ^ |   +1 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)
•  » » » » » » 22 months ago, # ^ |   +1 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.
•  » » » » » » » 22 months ago, # ^ |   0 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. :)
•  » » 22 months ago, # ^ |   +3 From Euclid's theorem,  gcd(a, b) = gcd(b%a, a) Now let b >= a and x = b - a, thenb = a + xTake 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)
•  » » 22 months ago, # ^ |   0 if (x==y) gcd(x,y)=x; if (x>y) gcd(x,y)= gcd(x-y,y); if (x
 » 22 months ago, # |   0 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. "
•  » » 22 months ago, # ^ | ← Rev. 5 →   0 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 == 0k is either 0 or q-(a%q)
 » 22 months ago, # |   +9 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?
•  » » 22 months ago, # ^ |   0 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
•  » » » 22 months ago, # ^ | ← Rev. 6 →   +15 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...) when a = 3, b = 1 least lcm is 3 when k = 0 and gcd(1, 3) = 1 if k = 1 : gcd(2, 4) = 2 and lcm is 4 (no offense..)
•  » » » » 22 months ago, # ^ |   0 i'm also confused by the first statement in the editorial but in your exampleat k=2lcm(5,3)=15, gcd(5,3)=1So I guess it still holds that gcd is minimized at maximum lcm for this example
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +3 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 d of |b — a|. That may be the most important part I am seeing a lot of people miss. You need to test d as the denominator. Because d = gcd(a + k, |b - a|) for some d (it not only divides |b — a|, but also 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 adding d to 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 both a and b) is smaller than the already stored one? If it is, update it's value and store the just used k. If it's equal, you can update the stored k if the 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 that d | (b + k) and d | (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.
•  » » » » » 14 months ago, # ^ |   0 Thanks a lot for the explanation. It clarified all my doubts
•  » » » » » 5 weeks ago, # ^ |   0 Thanks a lot!
•  » » » 22 months ago, # ^ |   0 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 .
•  » » » » 22 months ago, # ^ |   0 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.
•  » » 22 months ago, # ^ |   0 I am confused too....
•  » » 22 months ago, # ^ |   +9 That part seems to be incorrect.What we should do is to try all divisors of $b-a$ and find the minimum lcm.
 » 22 months ago, # | ← Rev. 2 →   +10 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?
•  » » 22 months ago, # ^ |   +3 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.
•  » » » 22 months ago, # ^ |   0 Thanks, I understand it now.
•  » » » » 22 months ago, # ^ |   +1 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
 » 22 months ago, # |   +7 For problem A there is no need to define vector space. Directly read a variable and update counter values.
 » 22 months ago, # |   0 Can anyone explain how MSB(4) = MSB(7) = 2 in question no. 2.
•  » » 22 months ago, # ^ |   -6 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: ${4}_{(10)} = {100}_{(2)}$and: ${7}_{(10)} = {111}_{(2)}$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$.
 » 22 months ago, # |   +1 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?"
•  » » 22 months ago, # ^ |   0 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.
 » 22 months ago, # |   0 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
 » 22 months ago, # |   +1 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.
•  » » 22 months ago, # ^ |   -8 Oh, I was overkilling when writing my implementation ;)Thanks, solution updated. ;)
 » 22 months ago, # |   0 What is MSB? Could you explain a little bit deeply?(B)
•  » » 22 months ago, # ^ |   0 I've written my definition of it right on the tutorial. You can also read this comment.
•  » » » 22 months ago, # ^ |   0 Then MSB(57)=5 right?
•  » » » » 22 months ago, # ^ |   0 Yes. :)
 » 22 months ago, # |   0 Found a mistake, a little one. Problem B-> Greedy Solution-> plain text->solve function->while(isCompletion(x)) should be while(!isCompletion(x))
•  » » 22 months ago, # ^ |   0 Thanks, fixed. ;)
 » 22 months ago, # |   0 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?
•  » » 22 months ago, # ^ |   0 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.
•  » » 22 months ago, # ^ |   0 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)$.
 » 22 months ago, # |   0 Could you please describe your greedy solution of prob. 2 by an example? Say 39?
•  » » 22 months ago, # ^ |   +1 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: 4 6 5 
 » 22 months ago, # |   +9 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 even depth,and choose the edge between each vertex and its father one by one(if its father is still not covered).In this way,all vertices with odd depth are covered(the leaves of the trie have even depth),and all edegs are between an odd vertex and an even vertex,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.
 » 22 months ago, # |   0 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:(
 » 22 months ago, # | ← Rev. 3 →   0 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!
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 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 for all $n$ and no counter tests exist for your second solution.
•  » » » 22 months ago, # ^ |   0 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)?
•  » » » » 22 months ago, # ^ |   +1 The solution does not use 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).
•  » » » » » 22 months ago, # ^ |   -8 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. :)
•  » » 22 months ago, # ^ |   +1 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?
•  » » » 22 months ago, # ^ |   0 Got it! Thanks for the help :DKilling 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 :DThanks again! :)
•  » » 22 months ago, # ^ |   0 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
•  » » » 22 months ago, # ^ |   +3 The greedy approach does seem right! Thanks for pointing it out :)
 » 22 months ago, # |   0 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?
•  » » 22 months ago, # ^ |   +1 The graph needs to be connected as well (if you don't count isolated vertices).
•  » » » 22 months ago, # ^ |   0 !! thank you
•  » » » 20 months ago, # ^ |   0 I am getting TLE on problem E. Can someone please look into the code. Approach is same as given in editorial.code
 » 22 months ago, # | ← Rev. 2 →   0 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
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 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 dpvalues 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.
•  » » » 22 months ago, # ^ |   0 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
 » 22 months ago, # |   0 Can someone please explain GRAPH approach (BFS) in 1152B — Neko Performs Cat Furrier Transform .
•  » » 22 months ago, # ^ |   +12 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: For each node $(x, 1)$ ($0 \le x < 2^{20}$), there is an edge between $(x, 1)$ and $(x+1, 0)$. For each node $(x, 0)$ and for each n ($0 \le x \le 2^{20}$, $1 \le n \le 21$), there is an edge between $(x, 0)$ and $(x \oplus (2^n - 1), 1)$. From this point, the graph is complete, and you can do a BFS traverse as normal convention.
 » 22 months ago, # | ← Rev. 2 →   0 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
 » 22 months ago, # |   0 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?
 » 22 months ago, # |   +15 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
•  » » 22 months ago, # ^ |   +15 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
 » 21 month(s) ago, # |   0 can somebody explain the solution to problem D in more detail plz?
 » 15 months ago, # |   0 For problem D, can anyone explain more in details about the greedy approach? Why does greedy work for this case?
•  » » 15 months ago, # ^ |   0 All the leaf nodes have the same depth. So we can do greedy.
 » 9 months ago, # |   0 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 ?
 » 8 months ago, # |   0 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
 » 6 months ago, # |   0 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??
 » 4 months ago, # |   0 The best editorial ever