count function calculates the number of distinct numbers from 1 to x(inclusive) which have a divisor 2 or 3 or 5 or 7.

ll count(ll x) {
    vector<int> primes = {2, 3, 5, 7};
    int n = primes.size();
    ll res = 0;
    // Using Inclusion-Exclusion Principle to count numbers divisible by any of the primes
    for (int mask = 1; mask < (1 << n); ++mask) {
        ll curr_lcm = 1;
        int bits = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                curr_lcm = lcm(curr_lcm, primes[i]);
                ++bits;
            }
        }
        ll term = x / curr_lcm;
        if (bits % 2 == 1) res += term;
        else res -= term;
    }
    return res;
}

The position of set bits in binary representation of mask tells the number currently under consideration from {2, 3, 5, 7}. If mask has only one set bit then you are basically considering only one number in the array and its contribution should be added. Otherwise if it has more bits then you are considering their lcm which should be removed from contribution

Should have done this (I haven't done this in contest either )-

You want to compare two expressions:

2^x + 2^y vs 2^a + 2^b

Instead of computing powers directly, you can exploit the properties of exponentials.

If x > a, then 2^x > 2^a and dominates the sum

If x < a, then 2^a > 2^x => done

If x == a, then compare the second term, i.e., 2^y vs 2^b => again y > b => greater

Missed this (crying)

The solution code for Problem C shows "you are not allowed to view this page" error. If it opens for anyone, can they share the code in comments!

Waiting for the logic explanation! Someone who understood the solution please explain

In the first claim, can you check if you have got it right-

1. if $$$f(x,y)=0$$$ and we assume that $$$a_{i} \leq y$$$, then $$$min(a) \geq x$$$ implies that $$$a_{i} \geq min(a) \geq x$$$ which gets us $$$x \leq a_{i} \leq y$$$ and hence $$$f(x,y) \neq 0$$$ contradiction.

I tried to find the assumptions which would hold true. Can you check if I got them right —

1. If $$$f(x,y)$$$ is $$$0$$$ , then $$$f(x+1,y)$$$ is also $$$0$$$. If any $$$a_{i}$$$ was $$$ \gt y$$$, then both outputs would be $$$0$$$. So assume that $$$a_{i} \leq y$$$, then $$$f(x,y)=0$$$ and $$$a_{i} \leq 0$$$ implies $$$min(a) \lt x$$$, so $$$min(a) \lt x+1$$$ and hence $$$f(x+1,y)=0$$$ whenever $$$f(x,y)=0$$$.
2. If $$$f(x,y)$$$ is $$$0$$$, then $$$f(x,y-1)$$$ is also zero.

I was thinking the same thing. I tried out few test cases and maybe this will clear answer you question —

Not every operation will cost you 2 queries. Say you start your query with "0", if there is no substring "0", then we are looking at a string "11..11" as answer and this will take exactly 2*n queries. On the contrary, one can argue that answer string can be of the form "011..11", then too if you start your query with "0", you only take one query to get the one substring 2 queries for each character in the other "11..11" part.

Basically, your suffix of size n-1 will take 2*(n-1) queries only if they are the opposite of the character that you are querying for first( example- answer string — "100000" and you query first for t+"1" and then t+"0" ). But if the first character of answer string is the same as the character you are querying first then you get the whole string and not the suffix ( your answer builds as "10.." )

I hope I was able to explain!

Very well explained. This should be a part of the editorial! Thanks bruh

Yes. I did the same. F with DSU.

In problem C, can you explain what difference it makes logically (in dp transition) if we replace the original transition,

F[i][0] = min( F[i-1][0]+y[i-1]*x[i],F[i-1][1]+x[i-1]*x[i] ); F[i][1] = min( F[i-1][0]+y[i-1]*y[i],F[i-1][1]+x[i-1]*y[i] ); to this transition,

F[i][0] = min( F[i-1][0]+x[i-1]*x[i],F[i-1][1]+y[i-1]*x[i] ); F[i][1] = min( F[i-1][0]+x[i-1]*y[i],F[i-1][1]+y[i-1]*y[i] ); The answer for the second transition is coming different from the original answer but both of the transitions seem correct to me logically.

In problem C, can anyone explain what difference it makes logically (in dp transition) if we replace the original transition,

F[i][0] = min( F[i-1][0]+y[i-1]*x[i],F[i-1][1]+x[i-1]*x[i] );
F[i][1] = min( F[i-1][0]+y[i-1]*y[i],F[i-1][1]+x[i-1]*y[i] );

to this transition,

F[i][0] = min( F[i-1][0]+x[i-1]*x[i],F[i-1][1]+y[i-1]*x[i] );
F[i][1] = min( F[i-1][0]+x[i-1]*y[i],F[i-1][1]+y[i-1]*y[i] );

The answer for the second transition is coming different from the original answer but both of the transition seem correct to me logically.

In question C , on using unordered_map<int,int> , I am getting TLE whereas using map<int,int> accepts the solution. Can anyone please tell why it is so? My both submissions : Accepted Solution using map [problem:C][TLE submission using unordered_map](https://mirror.codeforces.com/contest/1682/submission/158110821)