STONED - Editorial

PROBLEM LINK:

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

Author: Ashish Vishal, Aditya Kumar Singh
Tester: Shikhar Sharma, Daanish Mahajan

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Data structures

PROBLEM:

Given an array of N stones each of some height.
For each query, we are given two positions and we have to output the total
number of stones visible from both positions.

EXPLANATION:

While maintaining a stack we can easily determine the number of stones
visible from each position in linear time.

Thereafter we can calculate the height and position of the maximum stone
present between stones A and B.

It is not tough to see that the number of stones visible from this position
is also the number of stones that are visible from both positions A and B.

As for the implementation details we can use a segment Tree to determine the
maximum between A and B.
Also we maintain a map where for each height we store a pair of position
and size of stack (which corresponds to the number of visible stones from this position).

Finally we can just use lower_bound to find out the exact position of the maximum.

SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define is insert
#define rep1(i,a,b) for(long long i=a;i<=b;i++)
#define F first
#define S second
#define file ifstream fin(“input.txt”);ofstream fout(“output.txt”);
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(n) for(long long i=0;i<n;i++)
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long int ll;
typedef long double ld;
typedef vector vi;

ll n,m,l,r,siz;
vi h,tree,sgr;

void build_segtree()
{
    
    tree.resize(2*siz,0);

    rep(i,siz,2*siz)
        tree[i]=i-siz+1;

    for(int i=siz-1;i>0;i--)
    {
        if(h[tree[2*i]]>h[tree[2*i+1]])
            tree[i]=tree[2*i];
        else
            tree[i]=tree[2*i+1];
    }
}

ll query(ll node,ll l,ll r,ll x,ll y)
{
    if(l>r || y<l || x>r)
        return 0;

    if(x<=l && r<=y)
        return tree[node];

    ll id1=query(2*node,l,(l+r)/2,x,y);
    ll id2=query(2*node+1,1+(l+r)/2,r,x,y);
    if(h[id1]>h[id2])
        return id1;
    else 
        return id2;

}

void right_next_gr()
{
    sgr.resize(n+1,0);

    stack<ll>st;

    for(int i=n;i>0;i--)
    {
        while(!st.empty()&&h[i]>=h[st.top()])
            st.pop();

        if(!st.empty())
            sgr[i]=1+sgr[st.top()];

        st.push(i);
    }
}

void solve()
{
    cin>>n>>m;
    siz=pow(2,ceil(log2(n)));

    h.clear();
    tree.clear();
    sgr.clear();


    h.resize(siz+1,0);
    rep(i,1,n+1)cin>>h[i];

    build_segtree();

    right_next_gr();


    fr(m)
    {
        cin>>l>>r;
        if(l>r)
            swap(l,r);
        ll ind=query(1,1,siz,l,r);
        cout<<sgr[ind]<<"\n";
    }    

}
int32_t main()
{
    #ifndef ONLINE_JUDGE
    freopen("inputf.in", "r", stdin);
    freopen("outputf.in", "w", stdout);
    #endif
    fast;
    ll t=1;
    cin>>t;
    while(t--)
    solve();
    return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define FAST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define F first
#define S second
#define mp make_pair

////-------------------------------------------------------------------------
#define int long long ////////////
////--------------------------------------------------------------------------
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(s)         (int)((s).size())
#define rep(i,a,n)  for(int i=a ; i<n ; i++)
#define nl "\n"
const int N = 2e5+5;

 
void construct_segment_tree(vector<int>& segtree, vector<int>& a, int n)
{
    for (int i = 0; i < n; i++)
        segtree[n + i] = a[i];
 
    for (int i = n - 1; i >= 1; i--)
        segtree[i] = max(segtree[2 * i],
                         segtree[2 * i + 1]);
}
 
void update(vector<int>& segtree, int pos, int value, int n)
{
    pos += n;
 
    segtree[pos] = value;
 
    while (pos > 1) {
        pos >>= 1;
 
        segtree[pos] = max(segtree[2 * pos],
                           segtree[2 * pos + 1]);
    }
}
 
int range_query(vector<int>& segtree, int left, int right, int n)
{
    left += n;
    right += n;
 
    int ma = INT_MIN;
 
    while (left < right) {
 
        if (left & 1) {
            ma = max(ma, segtree[left]);
 
            left++;
        }
 
        if (right & 1) {
 
            right--;
 
            ma = max(ma, segtree[right]);
        }
 
        left /= 2;
        right /= 2;
    }
    return ma;
}
 
//-------------------------------------------------------------------------------
void do2win(int test)
{ 
  int n,m;  cin>>n>>m;
  vi h(n);
  rep(i,0,n)  cin>>h[i];
 
  vi segtree(2*n);
  construct_segment_tree(segtree,h,n);
 
  map< int, set<pii> > M;
 
  stack<int> st;
  for(int i=n-1;i>=0;i--)
  {
    while((!st.empty())&&(st.top()<=h[i]))
        st.pop();
 
    st.push(h[i]);
 
    M[h[i]].insert(mp(i,sz(st)));
 
  }
 
  while(m--)
  {
    int k,l;  cin>>k>>l; k--,l--;
    if(k>l) swap(k,l);
 
    int mx=range_query(segtree,k,l+1,n);
 
    auto it=M[mx].lower_bound(mp(k,0));
  
    pii p=*it;
 
    int ans=p.S-1;
 
    cout<<ans<<nl;
 
  }
}
//-------------------------------------------------------------------------------
 
signed main()
{
 
   #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt","w", stderr);
   #endif

///+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   FAST; 
cout<<fixed<<setprecision(20);
 
///+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 
   int test;  test=1;    
    cin>>test;
 
    for(int i=1;i<=test;i++)
    { 
      do2win(i);
    }
 
   return 0;
}
3 Likes

I think you meant this.

While maintaining a stack we can easily determine the number of stones visible from each position in linear time. Thereafter we can calculate the height and position of the maximum stone present between stones A and B.It is not tough to see that the number of stones visible from this position is also the number of stones that are visible from both positions A and B.

As for the implementation details we can use a segment Tree to determine the maximum between A and B.Also we maintain a map where for each height we store a pair of position and size of stack (which corresponds to the number of visible stones from this position).
Finally we can just use lower_bound to find out the exact position of the maximum.

People have also solved it using LCA. Made an edge between an element and its next greater element on the right and calculated lca in each query and answer is its distance from rightmost node.
e.g CodeChef: Practical coding for everyone
I think there is a deque approach too . Someone has done that too
CodeChef: Practical coding for everyone

1 Like

yeah that is also one solution

yes exactly

Somebody plz tell me why in the sample test case

3 10 20 20 5 50

no. of stones visible from 4 and 4 is just 1, not 2 (5 ,50)
Or Am i reading d problem wrong

As 5<20, so from index 4, We cannot see the stone of height 5 at index 5. Only stone at index 6 will be visible from index 4 because 50>20.

1 Like

Anyone give me a test case where my code fails.

It seems like my solution is different. I will describe it here.

Code: Code for STONED

Using a stack, for each index i, let’s first precompute the index of the closest element to the left of it, that is greater than or equal to it. We’ll store this in array “idx”. We’ll actually store the index of the element incremented by 1. Consider the element at index 0 to be INFINITY for simplicity.

We maintain a Fenwick Tree or Segment Tree.

We want to process our queries in reverse. That is, in decreasing order of i. So we iterate from N to 1. We we are at index i, we increment position idx[i] in the Fenwick Tree by 1. Doing this, the answer for queries with “B” equal to i is the prefix sum upto and including “A”.

Note that at a given i, you will first answer all your queries and then only increment the position idx[i] by 1 in the Fenwick Tree.

3 Likes

Where should I get the python based solution ?

Beautiful

I don’t really have a test for which your code fails, but I’d suggest not using binary search. It will just make the process much simpler. To remove binary search, instead of keeping maximum elements in sparse table, just keep indeces in it. Then, just find the maximum index on the range and use the precomputed count array. I know it’s not of great help, but will at least remove the possibility of wrong code in binary search.

I misunderstood the problem and thought we have to consider both i > j and i < j. tried to understand where my code failing but never succeeded.

3 Likes

1
6 1
3 10 20 20 5 50
5 5
it gives output as 1.
it should give 2.

1 is correct output in this case, so no - this is not a case that fails. Only piles on the right side are considered.

Need help… Couldn’t find out why runtime error… Code: CodeChef: Practical coding for everyone

can anyone please explain why this code gives tle

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template using pbset=tree<T, null_type, less, rb_tree_tag,tree_order_statistics_node_update> ;
#define f(i,a,b) for(long long i=a;i<b;i++)
#define rf(i,a,b) for(long long i=a;i>=b;i–)
#define ll long long
#define mp make_pair
#define pb push_back
#define vll vector
#define vvl vector
#define pll pair<ll,ll>
#define vc vector
#define fi first
#define se second
#define lb lower_bound
#define gcd __gcd
#define p_q priority_queue
#define pqmax priority_queue
#define pqmin priority_queue<int,vector,greater>
#define all(x) x.begin(),x.end()
#define inc(x,start) iota(x.begin(),x.end(),start)
#define pi M_PI
#define inf LONG_LONG_MAX
#define setbits(x) __buitin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define endl ‘\n’
#define IOS ios_base::sync_with_stdio(0)
#define tie cin.tie(NULL)
const int mod = 1e9 + 7;

void buildTree(vc &tree,vll a,int Node,int start,int end)
{
if(start==end)
{
tree[Node].fi=a[start];
tree[Node].se=start;
return;
}
int mid=(start+end)/2;
buildTree(tree,a,2Node,start,mid);
buildTree(tree,a,2
Node+1,mid+1,end);

    tree[Node]=tree[Node*2].fi>tree[Node*2+1].fi?tree[Node*2]:tree[Node*2+1];

}
pll query(vc tree,vll a,int Node,int start,int end,int leftRange,int rightRange)
{ //No overlap // start and end are the index of arr
if(end<leftRange || rightRange<start)
return {INT_MIN,INT_MIN};
//complete overlap
if(leftRange<=start && end<=rightRange)
return tree[Node];

    //partial overlap
    int mid=(start+end)/2;
    pll q1=query(tree,a,Node*2,start,mid,leftRange,rightRange);
    pll q2=query(tree,a,Node*2+1,mid+1,end,leftRange,rightRange);
    return q1.fi>q2.fi?q1:q2;
}

int main()
{
IOS;tie;
int T;
cin>>T;
while(T–)
{
int n,m;
cin>>n>>m;
vll a(n);
f(i,0,n)
cin>>a[i];
vll maxi(n);
stack s;
ll count=-1;
rf(i,n-1,0)
{
if(s.empty())
{
s.push(a[i]);
count++;
}
else
{
ll t=s.top();
if(t>a[i])
{
s.push(a[i]);
count++;
}
else
{
while(!s.empty())
{
t=s.top();
if(t<a[i])
{
s.pop();
count–;
}
else
break;
}
if(t!=a[i])
{s.push(a[i]);
count++;
}
}
}
maxi[i]=count;
}
vc tree(4*n);
buildTree(tree,a,1,0,n-1);
while(m–)
{
int x,y;
cin>>x>>y;
if(x>y)
swap(x,y);
pll q=query(tree,a,1,0,n-1,x-1,y-1);
cout<<maxi[q.se]<<endl;

  }

}
return 0;
}