SHR44's blog

By SHR44, history, 2 years ago, In English

When I try to submit a problem in the credit suisse global coding challenge, it says the following

Oops — Something's Gone Wrong Sending the Code to the Server Request Failed with Status Code: 400

Message: https://api.github.com/repos/CS-CodingChallenge/gcc-2022-{name} {"message":"Not Found","documentation_url":"https://docs.github.com/rest/reference/repos#get-a-repository"}

What should I do now??

Full text and comments »

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

By SHR44, history, 2 years ago, In English

Sparse Table is a very powerful data structure especially for making range max and min queries. Here is my sparse table class.

#include <bits/stdc++.h>
using ll=long long;
#define f(i,x,a) for(ll i=ll(x);i<ll(a);i++)
#define LOG(x) 63-__builtin_clzll(x)
class sparse_table{
    public:
    std::vector<std::vector<ll>>st;
    std::vector<ll>a;
    sparse_table(ll n){
        st.resize(25,std::vector<ll>(n));
    }
    void buildst_min();
    void buildst_max();
    void buildst_sum();
    ll range_min_query(ll l,ll r);
    ll range_max_query(ll l,ll r);
    ll range_sum_query(ll l,ll r);
};
void sparse_table::buildst_max(){
    ll n=a.size();
    f(i,0,n){
        st[0][i]=a[i];
    }
    f(i,1,25){
        for(ll j=0;j+(1<<(i-1))<n;j++){
            st[i][j]=std::max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
        }
    }
}
void sparse_table::buildst_min(){
    ll n=a.size();
    f(i,0,n){
        st[0][i]=a[i];
    }
    f(i,1,25){
        for(ll j=0;j+(1<<(i-1))<n;j++){
            st[i][j]=std::min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
        }
    }
}
void sparse_table::buildst_sum(){
    ll n=a.size();
    f(i,0,n){
        st[0][i]=a[i];
    }
    f(i,1,25){
        for(ll j=0;j+(1<<(i-1))<n;j++){
            st[i][j]=st[i-1][j]+st[i-1][j+(1<<(i-1))];
        }
    }
}
ll sparse_table::range_max_query(ll l,ll r){
     return std::max(st[ll(LOG(r-l+1))][l],st[ll(LOG(r-l+1))][r+1-(1<<ll(LOG(r-l+1)))]);
}
ll sparse_table::range_min_query(ll l,ll r){
    return std::min(st[ll(LOG(r-l+1))][l],st[ll(LOG(r-l+1))][r+1-(1<<ll(LOG(r-l+1)))]);
}
ll sparse_table::range_sum_query(ll l,ll r){
    std::vector<ll> power_sum;
    ll k=r-l+1;
    for(ll i=25;i>=0&&k>0;i--){
        ll power=ll(pow(2,i));
        if(power<=k){
            power_sum.push_back(i);
            k-=power;
        }
    }
    ll ans=0;
    ll cur=0;
    for(auto x:power_sum){
        ans+=st[x][l+cur];
        cur+=ll(pow(2,x));
    }
    return ans;
}

You can use this if u find it useful and please do suggest improvements.

Full text and comments »

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