SpartanWarrior's blog

Help in Edu : Two pointers , Step 2 , Problem G
By SpartanWarrior, history, 4 years ago, In English

Can someone please help me on how to approach this Problem

Thanking you in anticipation.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for query you can use sparse table or segment tree

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Hint
Solution
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved it this way: https://github.com/actium/cf/blob/master/edu/09/2g.cpp

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I actually am not able to understand with this is O(n). At first glance it seemed O(n^2) to me.

    What I thought was, for every j, the remove function in the tutorial in worst case removes no elements, which is analoguous here to moving the i pointer from j to the start (j times).

    So the no of iterations in the worst case: 1+2+3...n = O(n^2)

    Please let me know if I have made any mistake at any point... Would really appreciate the help...

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In tutorial, we can easily get max/min when adding an element, but it's hard to remove an element.

How does the tutorial solve it?

It uses two stacks to implement the queue, and get the result of max/min from two of the stack to get the result.

Can we just replace it with other merge function?

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define ll long long 
using namespace std;
 
class Stack {
    public:
    vector<ll> vals, gcds;
 
    void push(ll a){
        ll cur;
        if(gcds.empty()) cur=a;
        else cur = __gcd(gcds.back(), a);
        vals.pb(a);
        gcds.pb(cur);
    }
 
    ll pop(){
        ll x = vals.back();
        vals.ppb();
        gcds.ppb();
        return x;
    }
 
    ll gcd(){
        return gcds.back();
    }
 
    ll val() {
        return vals.back();
    }
} s1,s2;
 
void remove(){
    if(s2.vals.empty()){
        while(!s1.vals.empty()) s2.push(s1.pop());
    }
    s2.pop();
}
 
ll tot_gcd(){
    if(s1.gcds.empty() && s2.gcds.empty()) return -1;
    if(s1.gcds.empty()) return s2.gcd();
    if(s2.gcds.empty()) return s1.gcd();
    return gcd(s1.gcd(), s2.gcd());
}
 
void solve()
{
    ll n;
    cin>>n;
 
    vector<ll>v(n);
    for(auto &it : v) cin>>it;
 
    ll l = 0;
    ll ans = INT_MAX;
    for(auto r=0;r<n;r++){
        s1.push(v[r]);
        while(tot_gcd() == 1){
            ans = min(ans, r-l+1);
            remove();
            l++;
        }
    }
 
    if(ans == INT_MAX) cout<<-1<<nline;
    else cout<<ans<<nline;
}

This was my solution, I suggest that you read through the theory in step 2 segment with small spread. It's sad to see that there is no proper editorial for the problems in edu.

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    saisumith770 Can you please clarify will these work for problem like, to find the smallest segment with all gcds in it to be 10 , if not then -1.

    Suppose

    n=6 arr = [15,30,10,20,30,40] and gcd of all in segment should be 10

    Here the ans will be 1 with [10] as segment .

    Will this code work for anything other than 1 as gcd ?

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And also even if it is to find the gcd as 1, it wont work , suppose n=5 arr = [3,6,9,4,6]

    here ans should have been 3 but it is giving -1.

    Your code is considering only those segments which start from first ele .

    → Reply