Great problems

Good stuff, I liked C a lot, it made me think of LCM in a new way

Thanks for the editorial

Mathforces!

This one requires a lot more math, but it's not friendly to younger participants. And, this is an algorithm competition, not a math competition.

Great Round, Great problems. Statements were short and crisp problem "C" is my personal favourite. Looking forward to see more such rounds. Thank you!!!

Although I didn't participate, I also think the problems especially C and D are wonderful!

When I was solving B, for some reason I typed "a^x" as "a*x" and spent almost all round to understand why extended euclidian algorithm doesn't work. Moral of the story: Don't tunnel vision, do your math.

Great round!

I spent over an hour on b since I put (n % (a ^ k))%b == 0 instead of (n — (a ^ k))%b == 0.

Nonetheless the problems were good, and I enjoyed the round

I think B is harder to think than D.

Imagine C is harder to think than D...

Can someone explain the second paragraph of $$$B$$$ tutorial?

I had a slightly different approach for problem C. So I will explain my solution and thinking process.

Initially I was not able to solve the problem. Then I remembered one thing that factorial of even small numbers is very large (like $$$50!$$$). So, this gave me direction to think that $$$f(n)$$$ cannot be very large. So I ran a test to see that when we multiply prime numbers up to $$$50$$$, it will exceed $$$10^{16}$$$.

I still had no clue how to solve this problem. Then I randomly wrote a number in prime factorization form. I saw that $$$f(n)$$$ can only be some power of only a single prime i.e. $$$f(n) = p^k$$$ where $$$p$$$ is some prime and $$$k$$$ is its power. I was able to prove this.

Now, I knew that $$$f(n)$$$ can only be some power of prime up to $$$50$$$. So, now if $$$f(n)=p^k$$$, then $$$n$$$ must have exactly $$$p^{k-1}$$$ in its prime factorization form because otherwise $$$p^{k-1}$$$ will be $$$f(n)$$$. Now, I had to think what else should $$$n$$$ must have in its prime factorization form. I observed that for some other prime $$$q$$$ its power $$$m$$$ must be such that $$$q^{m+1} > p^k$$$ because otherwise $$$q^{m+1}$$$ can be answer. Then I found a number $$$D$$$ satisfying the above requirements. Now, the number of multiples of $$$D$$$ minus the number of multiples of $$$D*p$$$ would give the numbers for which $$$f(n) = p^k$$$. Then I would just add contribution to answer. Note that we have to handle a corner case i.e. when $$$D$$$ exceeds $$$n$$$, then we don't take any contribution from $$$p^k$$$.

#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
using namespace std;
using namespace __gnu_pbds;
// Policy based data structure 
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
#define gin(x) cerr<<#x<<" : "<<x<<" ";
#define fin cerr<<endl;
#define inf 1e18
#define mod 1000000007
#define N 200009
void sout(){
    cout<<endl;
}
template <typename T,typename... Types>
void sout(T var1,Types... var2){
    cout<<var1<<" ";
    sout(var2...);
}

#define int long long int

bool isPrime(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0)
            return false;
    }
    return true;
}

void solve(){
    int n;
    cin>>n;
    vector<int> pr;
    for(int i=2;i<=50;i++){
        if(isPrime(i))
            pr.push_back(i);
    }
    if(n<=50){
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n+1;j++){
                if(i%j!=0){
                    ans=ans + j;
                    break;
                }
            }
        }
        cout<<ans<<endl;
        return;
    }
    int ans=0;
    for(const auto &p:pr){
        int k=p;
        while(k<=n){
            unsigned int D=1;
            bool can=true;
            for(const auto &q:pr){
                if(q>n)
                    break;
                int x=1;
                if(q==p){
                    while(x*q<k){
                        x*=q;
                    }
                } else{
                    while(x*q<=k){
                        x*=q;
                    }
                }
                D*=x;
                if(D>n){
                    can=false;
                    break;
                }
            }
            if(!can){
                k*=p;
                continue;
            }
            int loc=n/D - n/(D*p);
            // sout(k,D,loc);
            loc=loc*k;
            loc=(loc%mod + mod)%mod;
            ans=ans + loc;
            ans=(ans%mod + mod)%mod;
            k*=p;
        }
    }
    cout<<ans<<endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    clock_t t1=clock();
    int t;
    cin>>t;
    // t=1;
    while(t--){
        solve();
    }
    cerr<<"Time elapsed: "<<(double)(clock()-t1)/1000<<" s"<<endl;
}

Any idea why this solution to B gives TLE? Is it some silly mistake? Cause I've pretty much followed the editorial.

void solve(int testcase) {
    int n, a, b; cin >> n >> a >> b;
 
    if (a == 1) {
        cout << ((n - 1) % b == 0 ? "Yes\n": "No\n");
        return;
    }
 
    int m=1;
    bool res=false;
    while (m <= n) {
        if (m % b == n % b) {
            res = true;
            break;
        }
        m *= a;
    }
 
    cout << (res ? "Yes\n": "No\n");
}

Can anyone analysis the time complexity of problem C for me pls?

Can someone please guide me through the equivalence of both formulas in C?

math math math math math maTh MaTH MATH MATH MATH MATH MATH MATH MATH AAAAAAAAAAAAAAAAAAAA!!!!1!!!11!!!

These format of spoilers hurt my eye really bad, can you make it like this ? It will look much better.

Really a great contest! Kudos!

Nice contest.
- Team Atcoder Fan, 2021

in the C Tutorial : "Since f(n)= i means lcm(1,2,...,i−1) ≤n " why? I don't understand this, can you explain it to me?

why chinese people think,that math problems are more interesting than algorithmic or data structure?

Can someone help me understand how they thought of this DP (and it's states) in problem D?

The current editorial focuses more on implementation, less on the idea.

Look at my code for B, it's very funny compared to the original solution, but still my code passed all the tests. Here is the link: https://mirror.codeforces.com/contest/1542/submission/121210576

What are $$$p1$$$ and $$$q1$$$ in E1 editorial? And what do you mean by enumerating $$$p1$$$ and $$$q1$$$? feecIe6418

Hi, I don't understand the editorial of problem B. Can someone please explain it to me?

Thanks

Does anyone have a different solution for E1?

froggyzhang had given a solution for e2 by using generating functions which i think is much easier than the official tutorial(which is also great!). Unluckily, it's in Chinese. And if anyone want to read it you can find it here.

Is there any recursive approach to solve D

In B, is it true that if $$$n$$$ is equal to some power of $$$a$$$ then $$$n$$$ belongs to the set?

I had the following condition in my code:

if( n % a == 0) {
    cout << "Yes\n";
    continue;
}

and for some reason this gives a wrong answer. My reasoning was the following. If $$$1$$$ and $$$1 \cdot a$$$ are in the set then $$$1 \cdot a \cdot a$$$ must also be in the set and other powers e.g. $$$1 \cdot a \cdot a \cdot a$$$ as well. So if $$$a$$$ divides $$$n$$$ i.e. $$$n \pmod a == 0$$$ then $$$n$$$ should be in the set. Am I missing something trivial ????

Can someone explain in better/different words what the states in the DP for D actually represent? The editorial is not at all clear to me.

What a nice math contest!(C is really nice)

Brilliant Problems!! Thanks for such a nice contest.

Could anyone explain why I got a time limit exceed in problem B test 2?

Thank you so much.

#include <iostream>
using namespace std;

int main() {
    int tcs, tc, n, a, b, i;
    bool f;
    cin >> tcs;
    for (tc = 0; tc < tcs; tc++) {
        cin >> n >> a >> b; 
        if (a == 1) cout << (n % b == 1 ? "Yes" : "No") << endl;
        else {
            i = 1; f = false;
            while (i <= n) {
                if ((n - i) % b == 0) {f = true; break;}
                i *= a;
            }
            cout << (f ? "Yes" : "No") << endl;
        }
    }
    return 0;
}

Someone please explain solution of D. I am unable to comprehend the tutorial solution.

Can anyone explain me div 2 D solution

when coming up with dp solutions of taskE1 would you write the initial statements first(for(int i=1;i<=n*(n-1)/2;i++)s[0][i]=1;) or figure it out after the recursive statements? Because I had a hard time writing the initial statements,not knowing how many elements in the array should I initialize(Like why is s[0][0]=1 not needed). Please share some tips! and sorry for my bad English

I'M THE ONLY ONE FST ON D!!!!!!!!!!!!! :(

Let me introduce froggyzhang's idea of problem E in English. You can find the original edition here(in Chinese).

I recommend you read the first and second paragraph of the official tutorial of E2 and the official tutorial of E1 before reading the following part of this article.

Assume $$$p_{i+1}=a$$$ and $$$q_{i+1}=b$$$, $$$a,b$$$ are their rank in their permutations.

So $$$inv(p)> inv(q)\Leftrightarrow inv(p[i+2,\dots n])-inv(q[i+2\dots n]\ge b-a+1$$$. So we just want to find the number of the pairs of permutations $$$p,q$$$ of length $$$n-i-1$$$ and $$$inv(p)-inv(q)\ge b-a$$$.

Precalculate $$$f(i,j)$$$ the number of the pairs of permutations $$$p,q$$$ and $$$inv(p)-inv(q)=j$$$. You can insert the numbers to the permutation from small to big and you can do it in $$$O(n^4)$$$ or $$$O(n^5)$$$ by using brute force(which is also mentioned in the official tutorial of E2).

You will find inserting number $$$i$$$'s generating function is as follow:

About the above part we can write it in to DP functions($$$a\to b$$$ means we add the value of $$$a$$$ to $$$b$$$).

And $$$\frac{1}{(x-1)^2}$$$ means we want to roll back twice. Just think what do you do when you $$$\times (x-1)^2$$$. So we can calculate $$$f$$$ in $$$O(n^3)$$$(both time and memory). We can only keep two layers of transition to optimize the memory to $$$O(n^2)$$$. And we can calculate suffix sum and the answer of the same prefix in $$$O(n^2)$$$.

You can read froggyzhang's code in his blog. You can find other details of coding in his code if you need.

In the implementation of problem D, why is the additional if (i!=t) : f[i][j]=(f[i][j]+f[i-1][j])%mod there at the end of innermost for loop? Isn't the case where we skip the ith element already considered in each case?

Can anyone explain problem D. I didn't understand the solution in editorial.

This is my code for Div2 D

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long double lld;
const lli  M1 = 1e9 + 7;
const lli M = 998244353;
const lli M2 = 1000000000000000001;
lli mod(lli x){   return (x%M);}
lli mod_minus(lli a, lli b){ lli ans= (mod(a)-mod(b)); if(ans<0) ans=mod(ans+M); return ans;}
lli mod_mul(lli a,lli b){  return mod(mod(a)*mod(b));}
lli mod_add(lli a,lli b){ return mod(mod(a)+mod(b));}
#define FOR(i,l,u) for(lli i=l;i<=u;i++)
#define FAST ios_base :: sync_with_stdio (false); cin.tie (NULL)
void solve(){
    lli n;cin>>n;
    lli A[n];
    FOR(i,0,n-1){
        char c;cin>>c;
        if(c=='-'){
            A[i] = -1;
        }
        else{
            cin>>A[i];
        }
    }
    lli ans = 0;
    FOR(i,0,n-1){
        if(A[i]!=-1){
            vector<vector<lli>> dp(n , vector<lli>(n+10,0));
            if(i==0)
               dp[0][0] = 1;
            else{
                if(A[0]==-1 || A[0]>A[i])
                    dp[0][0] = 2;
                else if(A[0]<=A[i])
                {
                    dp[0][0] = 1;
                    dp[0][1] = 1;
                }
            }
            FOR(j, 1 , n-1){
                FOR(k, 0 , n){
                    if(A[j] == -1){
                        dp[j][k] = mod_add(dp[j - 1][k] , dp[j - 1][k + 1]);
                        if(k == 0 && j < i)
                           dp[j][k] =  mod_add(dp[j][k] , dp[j - 1][k]);
                    }
                    else if((A[j]>A[i])||(A[j]==A[i] && j < i)){
                        dp[j][k] = mod_add(dp[j - 1][k] , dp[j - 1][k]);
                    }
                    else if(A[j]<A[i]||(A[j]==A[i] && j>i)){
                        dp[j][k] = mod_add(dp[j][k] , dp[j - 1][k]);
                        if(k>=1){
                            dp[j][k] = mod_add(dp[j][k] , dp[j - 1][k - 1]);
                        }
                    }
                    else if(A[j] == A[i] && j == i){
                        dp[j][k] = mod(dp[j - 1][k]);
                    }
                }
            }
            //cout<<ans<<"\n";
            FOR(k,0,n){
                ans = mod_add(ans , mod_mul(A[i],dp[n-1][k]));
            }    
        }
    }
    cout<<mod(ans)<<"\n";
}
int main()
{
    FAST;
    // #ifndef ONLINE_JUDGE
    // // for getting input from input.txt
    // freopen("input.txt", "r", stdin);
    // // for writing output to output.txt
    // freopen("output.txt", "w", stdout);
    // #endif
    lli t=1;//cin>>t;
    while(t--)
      solve();
}

Someone please provide me any small testcase for debugging.

Hey I don't know why I am wrong answer on test 2 of Problem B. This is my submission: https://mirror.codeforces.com/contest/1542/submission/121246560 Can you tell me what I am wrong. Thanks you

Edit: Understood my mistake.

Can someone tell me what's wrong in my logic for B: I observed a pattern for f(n) over numbers. Till every 6th number f(n) is 2 3 2 3 2, and for every 6th number, if the divisor upon dividing the number by 6 if odd then f(n) is 4 otherwise 5. So if n = 12, f(n) = 2 + 3 + 2 + 3 + 2 + 4 + 2 + 3 + 2 + 3 + 2 + 5 = 33. This logic is not working for the pretest 1 (10^16). Can anyone tell what's wrong in this?

in tutorial for C, why ∑i>1i(⌊n/lcm(1,2,...,i−1)⌋−⌊n/lcm(1,2,...,i)⌋) is equal to ∑i≥1⌊n/lcm(1,2,...,i)⌋+n?

Sorry,I'm not sure abount Problem D.If there are multiple smallest elements and then we execute an erasing operation,what will happen?Will we erase all the smallest elements or just erase one of them?

Problem $$$E1$$$ is very nice. I have an alternative solution, which to me at least makes more sense.

In a lot of these problems where we have $$$p < q$$$ for some permutation/array $$$p, q$$$, we can break up $$$p, q$$$ into some interval $$$[1, \dots i]$$$ in which $$$p_j = q_j \forall j \in [1, i]$$$, $$$p_{i + 1} < q_{i + 1}$$$ and then an arbitrary permutation from $$$i + 2$$$ onwards. Perhaps my notation is a bit pedantic; maybe an example will help:

$$$p = 1 3 4 5 2$$$

$$$q = 1 3 2 4 5$$$

In this case, $$$p$$$ and $$$q$$$ share a common prefix of length $$$2$$$. Then, after that, we have that $$$4 > 2$$$, so we know that $$$p > q$$$. $$$[5, 2]$$$ and $$$[2, 5]$$$ can be respectively remapped to a new permutation ($$$[2, 5] \to [1, 2]$$$).

Okay, so let's assume that $$$p, q$$$ share some prefix of length $$$len$$$. Then, we know that $$$p_{len + 1} > q_{len + 1}$$$, so we can iterate over pairs $$$p_{len + 1} < q_{len + 1}$$$, which serve as a sort of distinguisher. If we let $$$dp[n][k]$$$ be the number of permutations of length $$$n$$$ with $$$k$$$ inversions, then we see that $$$ans[inv]$$$ — the number of pairs $$$p, q, p < q$$$ such that $$$\text{inv} (p) > \text{inv} (q)$$$ — can be written as:

$$$ans[inv] = ans[inv] + dp[N - len - 1][inv + q_{ind + 1} - p_{ind + 1}] \cdot \frac{N!}{(N - len)!}$$$

It remains to find $$$dp[n][k]$$$. The editorial has a good explanation on that, so I omit that detail.

Also needs some optimization since this is $$$\mathcal{O}(N^5)$$$. Can be optimizes if we iterate over $$$q_{ind + 1} - p_{ind + 1}$$$ instead.

Cheers!

EDIT: SAME IDEA CAN SOLVE E2 LET'S GOOOO: 145998673 First 2700 problem solved w/o editorial!!

In problem C,

I think there is an interesting pattern to observe...

Look...

For all Odd numbers,

x will always be 2.

For even numbers,

Please correct me If I am wrong...

For C :- — We need to min positive integer for each number 1 , 2 ... N which doesn't divide it.

-  We can do grouping of numbers ( of x ).


   lets take an example first 
   -> N / 2 = number of elements divisible by 2
   -> N / 3 = number of elements divisible by 3

   -> N / 6 = number of elements divisible by 6  
            = number of elements divisible by 2 and 3
            = number of elements divisible by lcm(1,2,3) ie lcm(1,2,..i) elements                 

  N / lcm(1..i) -> numbers in N which are divisible by first i elements
  N / lcm(1...i-1) -> numbers in N which are divisible by first (i - 1) elements
  so  N / lcm(i...i) - N / lcm(1.. i-1)  = no of elements not divible by  I.


 we can do it for all numbers till 42
 since lcm of first 42 elements > 1e16.