D can also be solved by using GCD convolution.

i think i was tooo close to solve c. damn it , i will see it next time

It says tutorial is not available, so I'll write about what I solved myself.

A: Digit sum can be found in $$$O(\log x)$$$. $$$y$$$ is at most $$$x + 2k$$$. Time complexity $$$O(k \log x)$$$.

B: If there are $$$a$$$ digit with $$$1$$$ in the $$$k$$$ smallest digits, you can shift them all to the $$$k$$$ rightmost position to make a multiple of $$$2^{k-a}$$$. Try for all $$$k$$$, utilizing prefix sum to not make time complexity $$$O(n^2)$$$. Time complexity $$$O(n)$$$

D: If there is an integer $$$x$$$ that $$$a_i$$$ and $$$a_j$$$ are both divisible by, then they are not good pairs, only if $$$x$$$ is present in $$$a$$$. However if $$$2$$$ and $$$3$$$ is present but $$$6$$$ is not, then you need to subtract duplicates in multiples of $$$6$$$. Therefore, you must use Inclusion-Exclusion, but exclusively on elements of $$$a$$$ and their multiples. Because $$$a_i$$$ is bounded by $$$n$$$, time complexity is $$$O(n \log n)$$$ due to the harmonic lemma.

EDIT: Tutorial is up. You might better link it to the contest as well

fast editorial

thanks for fast editorial ! pE too hard and interesting !!

what a hard div 2!

I didn't solve C . But I cant realise the solution . someone help me to understand !

What's wrong in this solution for problem D — 229186378 ? Any help is appreciated.

I would have become CM today. Screw sets bro.

Submission for D using sets: (TLE >2000ms) https://codeforces.com/contest/1884/submission/229175001

Submission for D with array: (AC ~700ms) https://codeforces.com/contest/1884/submission/229192264

:(

In problem C, I cant understand why

From this, it follows that the minimum will either occur at position 1 or at position m

can't the minimum occur somewhere in between

What is the reason behind the name of the second problem?

even though i couldnt solve any but problem A was beautiful

Can anyone pls help me identify my mistake in Div2D link? Any help would be appreciated.

"Now let's understand which gcd values are not suitable. If there is a number x in the array (i.e., cntx>0 ), then all g multiples of x are not suitable"

Can someone please elaborate the meaning of the above statement in the editorial for problem D? 'not suitable' for what?

Can Someone Explain the Solution for Problem C. Most Importantly the Part From this, it follows that the minimum will either occur at position 1 or at position m

I am new to Competitive Programming. Is there any guideline for me? Any path I can follow?

There is a bit flaw in problem E's tutorial, in the second paragraph there should be b_{pos} not $$$b_pos$$$

Here is another way to solve D.

Let us call $$$f_x$$$ mean that is there $$$a_i$$$ is its factor.We can get the values in $$$\Theta(n\ln{n})$$$.

And than we can get the answer:

The last $$$\sum$$$ we can solve it in $$$\Theta(n\ln{n})$$$.

So we can solve the problem in $$$\Theta(n\ln{n})$$$.

record link:https://codeforces.com/contest/1884/submission/229180049.

Can anyone please show me why my code for B goes wrong

Why this code gives wrong answer for problem D — 229186378

Any small hint for D? I am stuck over 10 hours on it.

I had some idea, but it ended up working 30 seconds on random data and up to 80 seconds on test #15 (2, 3, 4, 5 ... 1000000) — much better than naive O(N^3), but nearly not fast enough.

Can anyone explain E in detail? I cannot understand the editorial.

what is sweep algorithm mentioned in C?

I don't know why I get wa for D use inclusion-exclusion, who can help me

(https://codeforces.com/contest/1884/submission/229407443)

Can anyone explain what is sweep line algorithm?

Can anyone explain me how would we implement the logic of B problem as explained in editorial , like its easy to maintain cnt_1 and sum_1 but how would we find cnt_1 number of zeroes after every index ? I tried storing the indisces in a vector and then find the sum of first cnt_1 for every index but that gave me a TLE. Someone pls explain

I believe I have a solution for E that differs slightly from the editorial. We also consider the inverted array $$$B$$$. Let $$$f(l, r)$$$ be the cost to reduce $$$B[l, r]$$$ to all zeros. If we could compute the prefix/suffix values $$$f(1, i)$$$ and $$$f(i, N)$$$, we could compute the $$$i$$$'th answer as $$$f(i, N) + f(1, i-1)$$$. Note this doesn't necessarily work because we might have to consider wrapping around the end of the array--consider an array like 2 0 1, for instance. However, the prefixes/suffixes can be computed independently if $$$B_1 = 0$$$, and since $$$B$$$ always contains a $$$0$$$, we can rotate $$$B$$$ such that $$$B_1 = 0$$$.

Thus the problem reduces to finding the values of $$$f(1, i)$$$ ($$$f(i, N)$$$ can be computed in the same manner by reversing $$$B$$$). We process them in increasing order of $$$i$$$. The number of operations is just $$$\sum_{j=1}^i \max(0, B_j - B_{j-1})$$$. The cost can be maintained using a monotonic stack.

got stuck on A for half the comp because i missed k <= 10 and tried finding ways to optimize the solution... I need to be more careful.

can anyone please debug my code for the problem C(counting rythm). It is giving wrong solution on test case 3..I can't figure out that hidden test case. Below is the code -> int n,m; cin>>n>>m;

set<int> index;
        map<int,int> end;
        map<int,pair<int,int>> start;

        for(int i=0; i<n; i++){
            int l,r;
            cin>>l>>r;
            index.insert(l); index.insert(r);
            start[l].first++; end[r]++;
            if(r==m) start[l].second++;
        }

        ll cnt1 = 0, cnt2 = 0, res1 = 0, res2 = 0;
        for(auto &idx : index){
            if(idx != 1){
                cnt1 += start[idx].first;
                if(end[idx]){
                    res1 = max(res1,cnt1);
                    cnt1 -= end[idx];
                    // if(cnt1<0) cnt1 = 0;
                }
            }

            if(idx != m){
                cnt2 += start[idx].first-start[idx].second;
                if(end[idx]){
                    res2 = max(res2,cnt2);
                    cnt2 -= end[idx];
                    // if(cnt2<0) cnt2 = 0;
                }
            }
        }

        cout<<max(res1,res2)<<endl;

// My logic is that — i m counting how many segments are starting before an end and if a segment ends at m then substract that segment.

In question E , why the answer should add a value (s+n-i+1)^2+(bi-bli) rather than (s+n-1-l)^2+(bi-bli)?

How to solve B using Binary Search?

Can anyone give a counter test case for this solution of Problem C: Medium Design link

Nice editorial

Can anyone help me know why my code of div2 D is giving me wrong answer in test 5? Thanks in advance.

10 dislike? why bro why. I just told you how to solve this problem. Is it my mistake? Or to support Palestine on my profile