can someone explain me B problem editorial again, am not able to picture the suggested approach?

In editorial for problem F, "dp[i]=max(dp[i],dp[j]+1)", shouldn't it be min instead of max, as we desire for the minimum number of operations. Correct me, if I am wrong.

About problem F:

1. I have seen some solution for F passes in $$$O(xloglogx)$$$ time per query.
2. You can do F in $$$O(tlogt+xlogx)$$$ using offline processing and sieve (link).
3. F appeared as one of our training problems (I didn't actually do it, might as well be a coincidence).
4. This DP looks exactly like shortest path on DAG, I solved it using BFS instead.

In the Tutorial of F, it should be min(dp[i], dp[j]+1), not max.

D was all about implementation and the editorial code is a bit tough to understand for beginners. So, you can refer the code below.

The main idea here is to find the highest and second highest extremes in all four directions — up, down, right and left. Now, the problem is reduced to removing the extreme most monster in all 4 directions one by one and place inside the rectangle formed by taking second most extreme in that direction and extremes in other 3 directions for eg. rectangle area considering second most right extreme, and up,down,left extreme points.

But here it may be possible that a point is extreme for two adjecent directions, ie. a point on top-right corner is extreme for both right and up directions. So here, the rectangle area is considering the extremes in left and down directions and second most extreme in up and right directions. The two if-elses in AreaC() functions check these 4 corner points.

The Areak() function also takes care of the case where the rectangle is already full ,i.e., the monster removed from one of the extremes cannot be placed inside the proposed smaller rectangle, in this case either the width or the height need to increased by 1 to accomodate the ONE monster that is removed.

Note that each of the variables up, down, right and left are a pair of the highest and second highest extremes in the respective direction.

Feel free to suggest any improvements.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define forn(i,a,n) for(int i=a; i<n; i++)
#define sv(v) sort(v.begin(),v.end());
#define print(x) cout<<x<<endl;
#define inp2(n,m)  long long n,m; cin>> n>> m;

ll n;
ll Areak(pll ri, pll le, pll up, pll down){
  ll w = ri.ff-le.ff+1;
  ll h = up.ff-down.ff+1;
  ll a = w*h;
  if(a==n-1) a = min(w*(h+1),(w+1)*h);
  if(a<=0) a= LONG_LONG_MAX;
  return a;
}

ll AreaC(pair<pll,pll> ri, pair<pll,pll> le, pair<pll,pll> up, pair<pll,pll> down){
  ll ans = LONG_LONG_MAX;
    if(ri.ff.ss==up.ff.ss)
      ans = min(ans,Areak(ri.ss,le.ff,up.ss,down.ff));
    else if(ri.ff.ss==down.ff.ss)
      ans = min(ans,Areak(ri.ss,le.ff,up.ff,down.ss));
    if(le.ff.ss==up.ff.ss)
      ans = min(ans,Areak(ri.ff,le.ss,up.ss,down.ff));  
    else if(le.ff.ss==down.ff.ss)
      ans = min(ans,Areak(ri.ff,le.ss,up.ff,down.ss));
    ans = min(ans,Areak(ri.ss,le.ff,up.ff,down.ff));
    ans = min(ans,Areak(ri.ff,le.ss,up.ff,down.ff));
    ans = min(ans,Areak(ri.ff,le.ff,up.ss,down.ff));
    ans = min(ans,Areak(ri.ff,le.ff,up.ff,down.ss));
    return ans;     
}

int main(void){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin>>t;
while(t--){
  cin >> n;
  vector<pair<ll,ll>> x;
  vector<pair<ll,ll>> y;
  forn(i,0,n){
    inp2(a,b)
    x.pb({a,i});
    y.pb({b,i});
  }
  if(n==1){
    print(1)
    continue;
  }
  sv(x)
  sv(y)
  pair<pll,pll> up = {y[n-1],y[n-2]};
  pair<pll,pll> down = {y[0],y[1]};
  pair<pll,pll> left = {x[0],x[1]};
  pair<pll,pll> right = {x[n-1],x[n-2]};
  print(AreaC(right,left,up,down));
}
}

Not able to understand F, please help.

I am trying to do it using prime factorisation, but i say comment that for ~20 we can't do bitmask dp, so i'm getting tle with that approach

For problem E, I have no idea why I missed the point that path is towards root during contest, and I solved a delusional version for path starting from each node by rerooting...

I'm actually surprised about how weak problem C's tests were. The fact that some people who use vector.erase() still passes the contest testcases is crazy

G is a cool problem!

In D, correct me if I'm wrong, but it is enough to consider at most 4 monsters, with regard to the relocation. By this I mean, the ones on the extremes in all 4 directions. In the worst scenario, you store at most 4 monsters that you want to move and for each, you brute force normally the min and max coordinates for each axis. No need for a multi-set. For me, way easier to implement.

In question E, it can also solved by the dp relation f(v) = max(av,av−a(v-1)+f(v-2)) where f(v) — the maximum value of the threat of the vertex and v-1 and v-2 represent the parent and grandparent of node v. We can keep track of both parent and grandparent in vector as we do bfs or dfs down from vertex.

what is a^2 in problem F?

Problem F with sieve of eratosthenes+dp
Time complexity:$$$O(n\sqrt{n})$$$
Sample code:321647158
Observation:First try to make so simple observation,you can see that if there is a prime number $$$p$$$ exist at $$$x$$$ but not in $$$y$$$ then we need to divide it,similarly for multiply,so first we know is if the $$$p \gt k$$$ we have not solution,so let us define two number $$$I$$$ and $$$J$$$,$$$I$$$ is the number x need to multiply and $$$J$$$ is the number x need to divide,if we can get $$$I$$$ and $$$J$$$ then the problem of us will reduce to how i use the number not greater than k to construct the $$$I$$$ and $$$J$$$.
I believe most of you already know the trick,for a standard sieve of eratosthenes(short form SIE),we can build an array in $$$O(NloglogN)$$$ to check a number is a prime or not,but additional we can extend the SIE to built an array $$$minprime[i]$$$ denoted the minimum prime factor in number i,so after this you can just simply do a while loop to prime factolization a number in $$$O(logN)$$$,so first prime factorize $$$x$$$ and $$$y$$$ then compare their prime factor from low to high,if they share common prime factor then just calculate it should be multiply or divide,if they don't share the prime factor also do the same thing then you can get $$$I$$$ and $$$J$$$
After this the problem of us is how to construct $$$I$$$ and $$$J$$$ will least factor such that $$$\forall factor \le k$$$,I will introduce a dp solution,we define $$$dp[i]$$$ is the minimum number to construct number i by using factor less equal than k,then the transition is $$$dp[i]=min(dp[i],dp[j]+1),\forall j\mid i\;and\;\frac{i}{j}\le k$$$ why?,the logic here is we observe that if we want to get $$$i$$$ first we need to reach the factor of $$$i$$$ then we multiply a number and reach $$$i$$$,so if $$$j$$$ can completely divide $$$i$$$ and $$$\frac{i}{j}\le k$$$ then obviously the minimum number to reach $$$j$$$ + one step to $$$i$$$,so we can just brute force the dp solution,and the reason it work and won't TLE is for a number $$$num\le 10^{6}$$$ there is at most 240 factor,so $$$240^2$$$ of a dp solution won't TLE.

1. Editorial isn't linked on contest page.

2. I don't understand this hate for D. It was simple to do in constant time, no? 🤥 it took me 5 minutes to do it. Submission

can somebody explain me the problem D? I am not able to understand how we are finding the maximum coordinates

I solved problem 2114F - Small Operations using simulated annealing, which is certainly not the best way, but it was interesting. My solution 321712725. I create arrays of prime factors to divide and multiply our number by, and then try to greedily divide them into groups with product less than k, starting from the beginning of the array.

how do we prove that the greedy way above of finding the max number of operations for G is correct ? why cant we do it in more operations ?

In problem G, we can calculate $$$x$$$ using c&-c in $$$O(1)$$$ time, then the algorithm can be finished in $$$O(n)$$$.

Problem F, as some people have already mentioned, can be reduced to this problem. However, I did not see any comment explaining a good way to apply this standard technique to the problem F.

The main simplification is the fact that our bits in bitmasks correspond to prime factors of $$$x$$$, and each mask represents multiplication of these prime numbers, which is some factor of $$$x$$$. This way we can get rid of actual bitmasks and bits, and consider only factors and prime factors of $$$x$$$.

Now, the transitions are the pretty much the same as in the linked problem. For each factor of $$$x$$$ we divide it for each prime factor, and update our $$$dp$$$ state for this factor, which is the total number of subsets, and value of the current subset. This gets us $$$O(d(x) * p(x) + sqrt(x))$$$ solution where $$$d(x)$$$ is the number of factors of $$$x$$$, and $$$p(x)$$$ is the number of distinct prime factors of $$$x$$$. Here is my code, but it's pretty messy. Hope this helps.

For problem F, why is this solution giving TLE ??

vector<int> p;

void sieve(){
    int n = 1e6+100;
    vector<bool> prime(n, 1);
    for(int i=2; i*i<n; i++){
        if(prime[i] == 0) continue;
        for(int j=i*i; j<n; j+=i){
            prime[j] = 0;
        }
    }

    for(int i=2; i<n; i++){
        if(prime[i]){
            p.pb(i);
        }
    }
}

void solve() {
    ll x, y, k;
    cin>>x>>y>>k;

    ll g = __gcd(x, y);
    x /= g;
    y /= g;

    ll x1 = x, y1 = y;

    int n = p.size();

    for(int i=0; i<n; i++){
        int f1 = 0, f2 = 0;
        if(x%p[i] == 0){
            f1 = 1;
        }

        if(y%p[i] == 0){
            f2 = 1;
        }

        if(p[i] > k && (f1^f2)){
            cout << -1 << endl;
            return;
        }
    }

    ll a = 1,cnt1 = 0;
    if(x1 > 1){
        for(int i=1; i<30; i++){
            a *= k;
            if(a >= x1){
                cnt1 = i;
                break;
            }
        }
    }


    ll b = 1,cnt2 = 0;
    if(y1 > 1){
        for(int i=1; i<30; i++){
            b *= k;
            if(b >= y1){
                cnt2 = i;
                break;
            }
        }
    }


    cout << cnt1 + cnt2 << endl;



    return;
}



int main() {
    boost
    int t = 1;
    sieve();
    cin >> t;
    for (int i = 1; i <= t; i++) {
        // cout << "Case #" << i << ": \n";
        solve();
    }
    return 0;
}

322437145

c can be simply solved with stack and returning the size of stack just implementation question of stack