Codeforces Round #554 (Div. 2) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

1152A - Neko Finds Grapes

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

Tutorial

Solution (xuanquang1999)

1152B - Neko Performs Cat Furrier Transform

Author: AkiLotus
Development: AkiLotus, xuanquang1999
Theme development: AkiLotus
Editorialist: AkiLotus

Tutorial

Solution 1 - Greedy (Akikaze)

Solution 2 - BFS (Akikaze)

1152C - Neko does Maths

Author: stefdasca
Development: stefdasca, AkiLotus
Theme development: xuanquang1999, neko_nyaaaaaaaaaaaaaaaaa
Editorialist: stefdasca

Tutorial

Solution (implemented by stefdasca)

Solution (implemented by Akikaze)

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, AkiLotus
Theme development: xuanquang1999, AkiLotus
Editorialist: MofK, AkiLotus

Tutorial - F1 (Small version)

Tutorial - F2 (Large version)

Solution F1 (xuanquang1999)

Solution F2 (xuanquang1999)

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

Authors' logs (miscellaneous things during our preparations)

Comments (82)

Show archived | Write comment?

rudr

6 years ago, # |

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

→ Reply

AkiLotus

6 years ago, # ^ |

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

nik7

← Rev. 2 →

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

GustavoGuerra

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

PrakharJain

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.

the.mentalist

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.

theBanzaiPredicament

+10

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

jef

← Rev. 4 →

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

pajenegod

+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)$$$.

meiniak

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

ContestDestroyer

← 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.

Damn those revisions.

manish_joshi

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!

BLUESKY007

+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.

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

iprakhar22

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)

fox_mulder

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

opooopooo

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

f20160445

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. "

INMAK

← Rev. 5 →

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?

nihaawop

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

← 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..)

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.

CodAR

5 years ago, # ^ |

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

dhakaji

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 .

lonelywind

I am confused too....

Cain

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

pmnox

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?

MofK

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.net/blog/entry/66696?#comment-507718

ashutoshjv661

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

sourabh.maj

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

-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$$$.

_abcd_

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

SAKT

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.

-8

Oh, I was overkilling when writing my implementation ;)
Thanks, solution updated. ;)

anancodec

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

dont_ask_my_name

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:

4
6 5

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.

meaningIess

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

mridul1809

← Rev. 3 →

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! :)

jlr.terceiro

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

knon0501

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

Gingka

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

uet_wannabered

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

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

sanket

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:

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.

Hd7

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

conquistador

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?

ivan100sic

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

luoxiaohei

22 months ago, # ^ |

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.

Believe

4 years ago, # |

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 ?