CF Round 714 Problem D

Problem - D - Codeforces

I am not able to understand how to find edges ?

@akshitm16 @ssjgz

It’s really simple. If you can use edge q, q < p on some segment [l, r], you can notice that it does not matter how we order the edges, there will always be just r - l edges, which adds (r - l) \cdot q to the final answer. So we realize that either you use DSU with some weird technique or derive a simple greedy - connect i_{th} vertex with (i + 1)_{th} vertex, for every l \leq i < r. This way we can mark the left vertex of each edge as used and finally traverse the whole array and for each vertex that is not connected using our greedy connect it with the vertex coming after it and add + p to the final answer.

I hope this removes your doubt, if you still don’t get it - here’s my submission solving using greedy: Submission #112771939 - Codeforces

1 Like

How to find that q ?

Ok, think about it this way. Let q_1 be the GCD on segment [l_1, r_1] and q_2 be the GCD on segment [l_2, r_2] such that the two segments intersect and q_1 is less than q2. This implies that although we could use an edge q2 on the parts that intersect it’s more optimal to use the lower value \implies q_1 is to be used on the part that intersects.

How do we find every pair q_1 and q_2? Firstly notice that q can only have value of some element of the array, because gcd of segment is equal to some element of array (the minimum one).

We can notice that if segments covered by q_1 and q_2 intersect, and q_1 \leq q_2, q_1 must be a divisor of q_2. So it’s enough to simply sort all the elements of array and consider them as q. For every q traverse to the right and find the longest subarray such that all the elements are divisible by q and such that it does not contain any of the already visited vertices (it’s enough to break the loop once we visit any of the already visited vertices, which ensures we do not visit any of the vertices more than once). Why is this correct? Well suppose we included an already visited vertex in our current calculation with q, there would exist some r such that r divides q since it’s already visited.

We do the same process to the left of every q. There are multiple ways to maintain the relative order of q elements, out of which I’ve decided to keep elements of array as pairs in an array (first element in pair is the value and the second the index of array).

I hope this is decently explained (I suck at explanatiosn :stuck_out_tongue:), so if there are parts that are unclear still, feel free to ask about it. :slight_smile:

1 Like

If we sort the array then index will change. Now, how can we consider subarray as the segment [l..r]

Instead of sorting the original array we’ll keep a temporary array of pairs: first element keeps the value of i_{th} element and the second element of pair keeps its original index i.

To consider [l, r] segments we loop through array of pairs and for every element go to the right until we reach a vertex we’ve already connected to the vertex after it using an edge.

By doing this we save ourselves from comparing every possible segment [l, r]. If some r was gcd of some segment [l_2, r_2] such that l_2 > l and l_2 < r and r_2 > r then there’s no need to consider already visited ones as r is ceratinly less than q, because the array is sorted.

We apply the same process to the left.

Consider the following example:

9, 3, 6, 24, 12, 4, 8

We start by considering 3 and go the right until we can. We mark 3-6, 6-24 and 24 - 12 as edges of length 3. We do the same to the left and get the edge 9 - 3 of length 3.

Now the next number is 4. Go to the right and add an edge 4 - 8 of length 4. Do the same to the left, but since we’ve already seen 12:

  • either r (in our case 3) was a divisor of 4, in that case we would have visited 4 so it’s certainly not right
  • r (in our case 3) was not a divisor of 4, so if some subarray ending at 12 contains mutliples of 4 they must be visited, if they weren’t visited than 12 wouldn’t be visited either since r is not a divisor of q (in our case 3 is not divisor of 4) thus subarray would not be contiguous, so we have contradiction

This means break out of loop at 12 and don’t consider any elements before it. Then when we reach 6, it has been visited already so we conclude that all the multiples of it to its right or left have already been visited (as divisor of 6 is also a divisor of its multiples). The story is similar for 8, 9, 12 and 24.

So it’s actually not needed to visit every single range [l, r] but just the prefixes/suffixes of some ranges. I hope it’s clear now. Still not, no problem feel free to ask more. :smiley:

2 Likes

Thanks a lot :bowing_man:

1 Like

No problem, glad I could help! :slight_smile:

1 Like

What else am I missing?

#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
//#pragma GCC optimize("Ofast")
// #pragma GCC optimize "trapv"

#define ll long long 
#define lld long double



int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    cin>>t;
    while(t--)
    {
        ll n,p;
        cin>>n>>p; 
        
        vector <pair<int,int>> v;
        int arr[n+1];
        
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
            v.push_back({arr[i],i});
        }
        sort(v.begin(),v.end());
        
        ll ans=p*(n-1);
        int mark[n]={0};
        int i=0;
        
        while(i<n && v[i].first<p)
        {
            int j=v[i].second;
            ll val=v[i].first,cnt=0;
            
            mark[i]=1;
            
            while(j+1<n && arr[j+1]%val==0 && !mark[j+1])
            {
                j++;
                cnt++;
                mark[j]=1;
            }
            j=v[i].second;
            while(j-1>=0 && arr[j-1]%val==0 && !mark[j-1])
            {
                cnt++;
                j--;
                mark[j]=1;
            }
            //cout<<cnt<<" "<<i<<"\n";
            ans=ans-cnt*p+cnt*val;
            i++;
        }
        cout<<ans<<"\n";
    }
}

You’re making the same mistake I made during the contest. We don’t mark vertices, we find an alternative way to mark edges which is explicitly to connect i_{th} to (i + 1)_{th}. So when we connect i to i - 1 we actually mark i - 1, not i as it comes after. Try figuring out on your own, in case you still have problems - post new code.

So to conclude - don’t mark vertix i automatically, but rather in while loop if j and j - 1 is not visited mark j - 1, and in the other loop we check whether j is marked, not j + 1. I hope this helps.

To further clarify - it’s a bit confusing if you think of mark as regular visited/marked array. Instead it describes whether i_{th} vertex is connected to the next vertex. So changin “mark” to “connected_to_next” may make it easier to understand.

1 Like

Finally done

1 Like