Problem B could be solved with XOR's as well. Here's a somewhat related problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=1232

I solved B using DP 234444052

Nice problems, I liked the contest. I had a different solution (which generalises to harder versions easily) for D though.

thanks for the tutorial with hints problem E was one of the best problems i have seen live in a contest

Great editorial ! It is always appreciated to have hint based editorials.

Btw I might have been a bit rash in my feedback. Considering the amount of solves by div2 contestants, E made the job a div2 E should do (also, the bonus task looks super cool!!). Also, after thinking a bit more about it, I think it's not that bad to have a div2 C which isn't adhoc as it gives all contestants the opportunity to solve "algorithmic" problems and not "1-observation" problems. I'm interested in others advice

really enjoyed the round, THANKS. Looking forward to more from you!!

I'm facing a problem with solving problems with number theory tags and focused on GCD, can I have a resource to learn from so I can pass this kind of problems faster please?

bruh why is D so tough. Can someone simplify please..

I had a slightly different solution for D. I iterated over i from 1 to maxi in order to compute x[i] (which is defined in the editorial). To compute each individual x[i], I had a list of indices of numbers in the sorted array divisible by i and I started from the third element in this list all the way to the last element. Something interesting is that if you pick some value for C with an index in the interval (x, y] in the sorted array where x and y are the indices of 2 multiples of i with no multiples of i between them with an index in that interval, then the number of possible choices for a and b such that both are divisible by i will always be the same. So you can iterate through the list of indices of multiples of i and get the #of ways to pick A and B and multiply this by the length of the current interval that tells us the #of ways to pick C. A nice implementation trick is to add the index n-1 to the end of every list of indices of multiples in order to catch all possible values of C for all x[i]. Once you've computed that, the rest of my solution is the same.

234519989

Can someone help me understand the solution to Problem D? I have been trying to understand the solution for a bit but I just can't understand it at all. Can someone give a simpler explanation because my brain just can't understand the solution for whatever reason?

Problem B, I try to test 1 1 11 in everybody AC code and all code print 1 1 1, that a wrong answer.

In problem C, I was able to identify the need for DFS. I wrote my code in both Python and C++. Tried both. But got TLE on pretest 2 in Python and TLE on pretest 5 in C++.

Python — https://mirror.codeforces.com/contest/1900/submission/234466578

C++ — https://mirror.codeforces.com/contest/1900/submission/234467214

Any kind of help is greatly appreciated.

Problem C.Anji's Binary Tree Solution Link : HERE

Anyone solved D using Mobius inversion?

infinite water source ftw

D could solved in O(MlogM) without factorizing. Just do the normal trick of counting gcd pairs and count in the contribution of c.

ABC was too easy this contest.

Problem B. If all numbers are odd or all are even. Then [1,1,1] since you can make any of them after some operations. Else pick the index of the number which has the unique parity. [1,2,1] pick two, [2,1,2] pick one. [1,2,3] pick two.

Operatio on [1,2,3]

[1,2,2,3,3,3] -> [&1&,2,2,&3&,3,3] -> [2,2,3,3,2] -> [2,2,&3&,&3&,2] -> [2,2,2,2].

Magic as described by the author.

234542604

Hi , can smb tell me whats wrong with dfs that returns the answer in task C , because I have TLE in pretest 5.

include <bits/stdc++.h>

using namespace std;

define endl '\n'

int dfs(int x, int kount,string s, vector<pair<int,int>> v){ if(v[x].first==0 && v[x].second==0) return kount; int ans=1000000000; if(v[x].first!=0){ if(s[x-1]=='L') ans=min(ans,dfs(v[x].first,kount,s,v)); else ans=min(ans,dfs(v[x].first,kount+1,s,v));

}
if(v[x].second!=0){
    if(s[x-1]=='R')
        ans=min(ans,dfs(v[x].second,kount,s,v));
    else
        ans=min(ans,dfs(v[x].second,kount+1,s,v));

}
return ans;

}

void solve(){ int n; cin>>n; string s; cin>>s; vector<pair<int,int>> v(n+1); for(int i=1; i<=n; i++) cin>>v[i].first>>v[i].second; cout<<dfs(1,0,s,v)<<endl;; }

int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }

P.S it works O(n) and n from the text is <=3*10^5 , I can't understand why it's TL

can some one please tell why it is giving TLE on test case 5 and please correct it.

https://mirror.codeforces.com/contest/1900/submission/234547330

Problem D can be solved by mobius inversion formula.

Which can be solved in $$$O(n\log n + n \sqrt{m} + m\log m)$$$. Code: 234463754

Note that we need to solve

Use the equation

We have

Pretreatment Euler function so that we can solve the equation in time complexity $$$\mathcal{O}(n\sqrt{n})$$$

234478574

Thanks for the fast editorial !

Are the "Bonus problems" somewhere for us to submit them??

.

Hey! guys, I'm new to competitive programming. I tried to implement anji's tree solution but I got a TLE, but when I passed the string by reference to the dfs function it worked Could someone explain to me how passing an argument by reference influence the run time. This is my code: https://mirror.codeforces.com/contest/1900/submission/234732141

Problems C and E are just... weird... Nothing really to solve, just implement standard algorithms.

Can anyone explain why this approach doesnt work for Problem D?

So i was iterating over A, and at index i i'm considering that to be middle value of triplet that is b. So as per question i need to find value of a and c now. I initialized currentIndexAns = 0 for this loop. Since a index has to be less than index of middle that is i for current loop. In an inner loop of i, i'm iterating A again. In this case if my inner loop index that is j. (j<i), then i will check if a[j]<=a[i], where i index is my assumed middle value, i will calculate its gcd(a[j], a[i]). And add it to currentIndexAns answer. After this i will have sum of all possible gcd values which can have i index as middle. Then i will multiply this currentIndexAns with count of indexes that is above i, so, j>i and a[j]>=a[i]. Let's call this count as countMaxLeftMiddle. Then i will multiply this, with currentIndexAns * countMaxLeftMiddle. To get contributions of triplets which have i as middle index.

Here is my code:

#include <bits/stdc++.h>

using namespace std;

class Solution {
    int gcd(int a, int b) {
        if (!a || !b)
            return a | b;
        unsigned shift = __builtin_ctz(a | b);
        a >>= __builtin_ctz(a);
        do {
            b >>= __builtin_ctz(b);
            if (a > b)
                swap(a, b);
            b -= a;
        } while (b);
        return a << shift;
    }

    public:
    long solve(int* a, int n) {
        long ans = 0, subPrblmAns;
        int greaterEqMidCntOnRight, mid;

        for (int i=0; i<n; i++) {
            mid = a[i];

            subPrblmAns = 0;
            greaterEqMidCntOnRight = 0;
            for (int j=0; j<n; j++) {
                if (i > j) {
                    if (mid >= a[j]) {
                        subPrblmAns += gcd(mid, a[j]);
                    }        
                } else if (i < j) {
                    if (mid <= a[j]) {
                        greaterEqMidCntOnRight++;
                    }
                }
            }
            cout << subPrblmAns << " " << greaterEqMidCntOnRight << endl;

            ans += (subPrblmAns * greaterEqMidCntOnRight);
        }

        return ans;
    }
};

int main() {
    int t, n;
    int *a = NULL;
    Solution sol = Solution();

    cin >> t;
    for (; t>0; t--) {
        cin >> n;

        a = new int[n];

        for (int i=0; i<n; i++) {
            cin >> a[i];
        }

        cout << sol.solve(a, n) << endl;

        delete(a);
        a = NULL;
    }
    return 0;
}

when you dont try E, because of stucking in d :(((

Seems easy for me the E one. (I solved it in one go)

I cannot understand this part in tutorial for E : The edge will have a weight equal to the size of the SCC that it is going into.

Why is that ? Shouldnt all the weights of edges be 0 ? and find the longest path by vertex numbers ?

In D how to create that divisor array in NlogN. i am doing it in NrootN.

Hi, I have a question related to the time limit in problem C (Anji's Binary Tree).

I got many TLE in submissions like 235439131, 235440112, 235441383. The idea was fine, but after reading some of the comments, I realized that removing some things like memset, global variables, and setting reference variables will get me to the AC (235443694).

I would like to know what kind of aspects I have to think when I want to use memset or other kinds of stuff. Why do the last submissions differ in seconds to each other? What are the technical aspects related to the stuff that I have used in the first submissions? Thanks!

Can someone Please explain why I am getting a TLE in this solution for problem C 234510811

even after lot of modifications and changes, I am getting memory limit exceeded on test case 3 where n = 200000, m = 200000.I think it is due to DFS3() call but couldn't think for it's substitute. This function calculates the maximum length simple path and then for that length path minimum value. this is my submission link.

There might be some other reason for TLE but I have gone through other submissions and they have also allocated same complexity of memory.( vectors and arrays for graphs )

Problem D can be solved without the constant of 128.

Firstly notice swapping the indexes doesn't influence the sum. Then swap the indexes to a sorted state.

Then, for each $$$g$$$, we want to know, $$$dp[g] = $$$ how many indexes tuples that $$$i < j < k$$$, that $$$\gcd(a[i], a[j]) = g$$$. Similar to the question, we first calculate $$$cnt[g] = $$$ number of tuples $$$i < j < k$$$ that $$$a[i] = a[j] = 0 \pmod{g}$$$, then minus $$$dp[2g] + dp[3g] + ... dp[\text{max multiplier} \times g]$$$ to $$$cnt[g]$$$

Because we are in a sorted state, we can work on those $$$pg$$$ for each $$$p = 1 .. \text{max multiplier}$$$.

Notice that, there are two cases. The first case is $$$a[i] < p g$$$. In this case, $$$pg$$$'s contribution to $$$cnt[g]$$$ is #$$$(i) * S(pg)$$$. $$$S(pg)$$$ is the number of tuples $$$(j, k)$$$ that $$$j < k$$$ and $$$a[j] = pg$$$. #$$$(i)$$$ is the number of index $$$i$$$s that $$$a[i] < a[j], a[i] = 1g .. (p-1)g$$$ (notice $$$i < j$$$ is obvious because we sorted it).

The second case is $$$a[i] = a[j] = pg$$$. In this case, the sum is $$$T(pg) = \Sigma_{l \in \text{first } pg \text{ index} .. \text{last } pg \text{ index} } (l - \text{first } pg \text{ index}) (N - l) $$$.

Both $$$S(pg)$$$ and $$$T(pg)$$$ are able to be precomputed by walking through the sorted array. So we can result a time complexity in $$$O(N \log N)$$$

In question 1 , in 5th test case

10

...#..#.

someone pls explain how the output is 2 ?

In Problem C, Test case 3: I can just change the string to LRLR by modifying R -> L and U-> R and reach Vertex 2, that takes 2 modification but Why the answer is 3? Can anyone explain that bit to me?

Why the BFS soln is not working?? Isn't it O(n)

Can Anyone explain solution with code of F local deletions ??

include<bits/stdc++.h>

define ll long long int

define llq __int128 using namespace std;

define level 18

define mod 1000000007

define lim 100008

define lldb double

define ln "\n"

const int U = (1 << 30) — 1; // bit operator

int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); ll t; cin>>t; while(t--) { ll n,m; cin>>n; string s; cin>>s; vectorans(n+1,0); ll sol=INT_MAX; vectorleaf; for(ll i=1;i<=n;i++) { ll x,y; cin>>x>>y; if(s[i-1]=='R') { ans[x]+=ans[i]+1; ans[y]=ans[i];

}
     else if(s[i-1]=='L')
     {
        ans[y]+=ans[i]+1;
        ans[x]=ans[i];
     }
     else{
        ans[x]+=ans[i]+1;
        ans[y]+=ans[i]+1;
     }

     if(x==0 && y==0) leaf.push_back(i);
  }
  // for(ll i=0;i<n;i++) cout<<ans[i+1]<<" ";
  for(ll i=0;i<leaf.size();i++)
  {
     sol=min(sol,ans[leaf[i]]);
  }
  cout<<sol<<endl;

}

}

Why this is wrong answer ,I am just updating distance from root according to given condition?? can any give me test case ?? @C Question

In Problem C, I used memorization to calculate the answer. Although being of time complexity of O(n), It is giving Time limit exceeded for n=10^5. Can someone suggest me the problem?

https://mirror.codeforces.com/contest/1900/submission/239971869

Did anyone tried Problem F? I didnt understand the editorial here

Did anyone do Problem F? I do not understand the tutorials provided

can anyone explain me that how are we getting 2 in question A's 5th test case

haha infinite water glitch go brrr

Solution for the problem D Link

can someone help why i am getting TLE int this submission[submission:284642031]

ohkk i might be making a very dumb mistake but in question A solutions says if the string contain substring '...' then answer is 2 otherwise no. of empty cell. ohkk but how will the distant 2 consecutive empty cell and 1 cell separated by blocks can be filled up