1152A - Neko Finds Grapes
Author: xuanquang1999
Development: xuanquang1999, AkiLotus, GreenGrape
Theme development: AkiLotus, GreenGrape
Editorialist: xuanquang1999
Submission link: 53259456
#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: AkiLotus
Development: AkiLotus, xuanquang1999
Theme development: AkiLotus
Editorialist: AkiLotus
Submission link: 53259692
#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;
}
Submission link: 53259743
#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, AkiLotus
Theme development: xuanquang1999, neko_nyaaaaaaaaaaaaaaaaa
Editorialist: stefdasca
Submission link: 53259956
#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;
}
Submission link: 53270277
#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
Submission link: 53260068
// 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
Submission link: 53260100
#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, AkiLotus
Theme development: xuanquang1999, AkiLotus
Editorialist: MofK, AkiLotus
Submission link: 53260139
#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);
}
Submission link: 53260164
#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);
}
Submission link: 53260183
#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;
}
Solve the problem in (or faster than) O(log(n)⋅k2⋅(2m)3).
xuanquang1999 actually proposed ~10 problems yet our dear cdkrot denied half of them.
I also proposed 4 and got denied 3 first one as well :-P
Problem B is the last invented problem. I was walking around the computer labs, thinking of some photoshopped Catzilla cat memes, which led to me thinking of enlarging cute kittens, then coming up with this problem.
Ironicly though, my model greedy solution would actually shrink the cats instead.
Anyway, I forgot this picture about longcat:
neko_nyaaaaaaaaaaaaaaaaa and I after I finished writing statements of B:
MofK went haywire after seeing first AC of problem F2 by dreamoon_love_AA. Poor MofK, he wrote a superbly veryheckingfast solution for F2 and was still outmatched. :<
P/s: Funny, in Codeforces both solutions have the same max execution time :D
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. ;)
AkiLotus 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.
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 thatx
is xor-ed with2^n - 1
, but you are printing2^n - 1
.Thanks a lot.
Why does gcd?
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 d i 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 thana
that is a divisor of d. For example, ford = 3
anda = 6
k would be 0 becauseceil(a / d)*d = a
, fora = 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 thatx * 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 thata + 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 findm = a - x * q
which isa % q
by definition. With this m and the total length of the intervalx * q + q - x * q = q
, we calculate the other part ask = q - m
, sok = 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
andx = b - a
, thenb = 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..)
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) , thena 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
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 .
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://mirror.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 2nd rightmost bit (3rd 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 AkiLotus (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+1in 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.
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.
AkiLotus 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 for all 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 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).
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 depthi
of the trie with the number of opening brackets minus the number of closing brackets equal toj
. For the transitions, we can append an opening bracket to the sequence represented by the current nodes and we get a sequence represented bydp[i + 1][j + 1]
. Ifj
is positive we can also append a closing bracket which gives us a sequence represented bydp[i + 1][j - 1]
. To get the maximum matching, we want to take the edges in every other layer so we take the sum ofdp
values for every other value ofi
, excluding the values wherei + j > 2 * n
because those sequences have too many opening brackets to form a correct bracket sequence of length2 * 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
Could you explain why the answer is such a polynomial? I have been trying to prove it for a long time but there's no progress.
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 ?