There are a number of blogs which describe the implementation of ordered_set using Fenwick trees.

Is there any way to implement fenwick tree struct using ordered_set? And could that be extended to the 2D case?

Motivation: I really suck at fenwick trees, and always get around by segtree templates... So, I'm trying to find a way to solve when I don't have access to templates... :(

We know that in python, we can use the following to get a list of integers (space separated) in a line:

arr = list(map(int,input().split()))

This doesn't require us to input the number of integers in the line before. In C++ however, it is not that easy. But fortunately for us, most cp questions give the input n (size of the vector).

What if we don't get the size beforehand, huh? Here's a possible fix....

#define ll long long

istream& operator>>(istream& stream,vector<ll>& a) {
    string line;
    getline(stream, line);
    istringstream lineStream(line);
    ll x;
    while(lineStream >> x) a.push_back(x);
    return stream;
}

.

vector<ll> a;    // empty vector
cin.ignore(); // Use only b/w a normal cin and the above overloaded cin, otherwise ignore this line
cin>>a;          // Vector now contains all the space separated integers of that line
n = a.size();

Alternatively we can use the following template and normally take vector input: (credit: -is-this-fft)

template<typename T>
istream& operator>> (istream& stream, vector<T> &a) {
  a.clear(); // remove whatever was in a before
  
  string line;
  do {
    if (stream.eof())
      return stream; // if the stream has ended, just let a be empty
    
    getline(stream, line);
  } while (line.empty());
  
  istringstream line_stream (line);
  T x;
  while(line_stream >> x)
    a.push_back(x);
  
  return stream;
}

P.S: I have tried my best to keep it error-free, but if you find any mistakes, feel free to highlight in the comment section...

This is my first time actually trying to contribute something, so please go easy on me....

Hello Codeforces! After a long time of search for a cure for precision errors in C++ while dealing with just integers, I was motivated to write a blog for a curated collection of one. Sure some common ones do already exist in the previous blogs, some really cool ones can be found while browsing other programmers' templates, but why not have a blog which saves the time of search and makes it easier for CP Enthusiasts to improve?

I have implemented a few as follows (may include the common ones):

1) ceil(a/b) and floor(a/b): Handling negative division as well...

ll divceil(ll a,ll b){ return a/b+(a%b>0);}
ll divfloor(ll a,ll b){ return a/b-(a%b<0);}

2) power(a,b):

ll binpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res*=a;
        a*=a,b>>=1;
    }
    return res;
}

3) Floor(logb(x)):

ll lg(ll x,ll b=2){
    if(b==1) return -1; //Modify this as per need
    if(b==2) return 63-__builtin_clzll(x); //O(1) for log2
    ll p=1,ans=0;
    while(true){
        if(p>x) return ans-1;
        if(p>LLONG_MAX/b) return ans;
        p*=b,ans++;
    }
}

4) nth-root (general): Thanks to LeoPro for the trick to deal with overflows

const ll INF = LLONG_MAX  // You may change ll to ull and LLONG_MAX to ULLONG_MAX 

ll mult(ll a,ll b){
    if(b==0) return 0;
    return a>INF/b?INF:a*b;
}

ll binpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a),b>>=1; 
    }
    return res;
}

ll bin_nth_rt(ll x,ll n){
    if(x==1||n==1) return x;
    if(x==INF) x--;    // Doesn't make a difference in answer, and check function fails for INF 
    ll l=0,r=x,m;
    while(r-l>1){
        m=l+(r-l)/2;
        if(binpow(m,n)>x) r=m;
        else l=m;
    }
    return l;
}

Please feel free to highlight any errors, or areas with room for improvement in performance, handling overflows, divide by zero, etc and contributing your own in the comments.

Thanks for reading!

UPD: Changed divfloor and divceil according to bicsi 's idea.

UPD: nth-root has now been updated to handle entire integer range.

Today, I was asked in an interview to build a data structure as follows:

Let there be some elements and some groups. Each element associated to 'exactly 1' group has a score. The data structure must support the following operations:

1. insert(el_id,grp_id,x): Insert element with id el_id with a score x to group with group_id grp_id
2. set(el_id,x): change the score of element with id el_id to x.
3. set(grp_id,x): change the score of all elements in the group with id grp_id to x.
4. print(grp_id): print the max score element's id in that group. (Return any if multiple exist)

Constraints:

1 <= no_of_elements <= 1e6
1 <= no_of_groups <= 5
1 <= score <= 5

I couldn't solve it during the interview and also couldn't think of any solution later. Would someone please help?

Recently, I have encountered many situations in which I was asked the complexity of std::sqrt() in C++. Since my early cp days, I have known the time complexity of std::sqrt() to be O(sqrt(n)), the reason being this and a few other youtube channels. I was using C++17 at that point.

A friend of mine suggested it to be O(logn) in C++20 after he tested it by printing cout<<sqrtl(N), where N was set as 1e18. The code compiled in 10 ms, giving the correct ans.

Later on, I ran the same code in C++14 in ideone and the code still compiled in 10 ms. This made me really confused...

I would really appreciate if someone helps me with this. I looked it up in cpp-reference but couldn't find it.

Recently, I was solving the Graphs section of the CSES problemset and encountered this problem. I used dijkstra algorithm to solve it.

I generally use the template from here, but in this question, this implementation gave me WA. When I used another implementation using visited array, it gave AC.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<pair<ll,ll>>> adj,adj_rev;
vector<ll> d1,d2;
 
void dijkstra(){
    set<pair<ll,ll>> st;
    st.insert({0,1});
    d1[1]=0;
    while(!st.empty()){
        ll node=st.begin()->second;
        st.erase(st.begin());
        for(auto it:adj[node]){
            ll child=it.first,wt=it.second;
            st.erase({d1[child],child});
            if(d1[child]>d1[node]+wt){
                d1[child]=d1[node]+wt;
                st.insert({d1[child],child});
            }
        }
    }
}
 
void dijkstra1(){
    set<pair<ll,ll>> st;
    ll n=adj.size()-1;
    st.insert({0,n});
    d2[n]=0;
    while(!st.empty()){
        ll node=st.begin()->second;
        st.erase(st.begin());
        for(auto it:adj_rev[node]){
            ll child=it.first,wt=it.second;
            st.erase({d2[child],child});
            if(d2[child]>d2[node]+wt){
                d2[child]=d2[node]+wt;
                st.insert({d2[child],child});
            }
        }
    }
}
 
int main(){
    ll n,m;
    cin>>n>>m;
    adj=adj_rev=vector<vector<pair<ll,ll>>>(n+1);
    d1=d2=vector<ll>(n+1,1e18);
    while(m--){
        ll a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj_rev[b].push_back({a,c});
    }
    dijkstra();
    dijkstra1();
    ll ans=1e18;
    for(int i=1;i<=n;i++){
        for(auto it:adj[i]){
            ans=min(ans,d1[i]+d2[it.first]+it.second/2);
        }
    }
    cout<<ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<pair<ll,ll>>> adj,adj_rev;
vector<ll> d1,d2;
 
void dijkstra(){
    set<pair<ll,ll>> st;
    ll n=adj.size()-1;
    vector<bool> vis(n+1,false);
    st.insert({0,1});
    d1[1]=0;
    while(!st.empty()){
        ll node=st.begin()->second;
        st.erase(st.begin());
        if(vis[node]) continue;
        vis[node]=true;
        for(auto it:adj[node]){
            ll child=it.first,wt=it.second;
            if(d1[child]>d1[node]+wt){
                d1[child]=d1[node]+wt;
                st.insert({d1[child],child});
            }
        }
    }
}
 
void dijkstra1(){
    set<pair<ll,ll>> st;
    ll n=adj.size()-1;
    vector<bool> vis(n+1,false);
    st.insert({0,n});
    d2[n]=0;
    while(!st.empty()){
        ll node=st.begin()->second;
        st.erase(st.begin());
        if(vis[node]) continue;
        vis[node]=true;
        for(auto it:adj_rev[node]){
            ll child=it.first,wt=it.second;
            if(d2[child]>d2[node]+wt){
                d2[child]=d2[node]+wt;
                st.insert({d2[child],child});
            }
        }
    }
}
 
int main(){
    ll n,m;
    cin>>n>>m;
    adj=adj_rev=vector<vector<pair<ll,ll>>>(n+1);
    d1=d2=vector<ll>(n+1,1e18);
    while(m--){
        ll a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj_rev[b].push_back({a,c});
    }
    dijkstra();
    dijkstra1();
    ll ans=1e18;
    for(int i=1;i<=n;i++){
        for(auto it:adj[i]){
            ans=min(ans,d1[i]+d2[it.first]+it.second/2);
        }
    }
    cout<<ans;
    return 0;
}

Naturally, I adopted the visited array approach and discarded the one before.

Now, using the visited array approach on this, I encountered WA again.

#include<bits/stdc++.h>
using namespace std;
 
void dijkstra(vector<int> adj[],vector<int> &dist,vector<int> &par){
    set<pair<int,int>> st;
    par[1]=dist[1]=0;
    st.insert({0,1});
    int n=dist.size()-1;
    bool vis[n+1]={false};
    while(!st.empty()){
        auto itr=*st.rbegin();
        int node=itr.second,d=itr.first;
        st.erase(prev(st.end()));
        if(vis[node]) continue;
        vis[node]=true;
        for(auto it:adj[node]){
            if(d+1>dist[it]){
                st.insert({d+1,it});
                dist[it]=d+1;
                par[it]=node;
            }
        }
    }
}
 
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> adj[n+1];
    vector<int> dist(n+1,INT_MIN);
    vector<int> par(n+1,-1);
    while(m--){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
    }
    dijkstra(adj,dist,par);
    if(par[n]==-1){
        cout<<"IMPOSSIBLE\n";
        return;
    }
    vector<int> ans;
    int x=n;
    while(x){
        ans.push_back(x);
        x=par[x];
    }
    reverse(ans.begin(),ans.end());
    cout<<ans.size()<<'\n';
    for(auto it:ans) cout<<it<<' ';
}   
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

Now I am very confused about what template to use for dijkstra, being a newbie to graphs. I would highly appreciate if someone helps.

In the recent few days the number of spam blogs have increased too much. This has led to the number of relevant blogs to the community become quite obscure.

MikeMirzayanov Please implement a functionality to lessen this, or if possible, stop this.

I don't have the knowlegde for possible a fix for this, but if anyone does, please feel free to mention in the comments so that MikeMirzayanov can look into it.

This is how I implement matrix exponentiation 190118918 (in this example, for the problem Fibonacci)

But I encountered this problem before and got TLE after implementing matrix exponentiation.

My solution code was:

#include<bits/stdc++.h>
using namespace std;

#define nl "\n"
#define ll long long
#define fo(i,n) for(i=0;i<n;i++)
#define fop(i,x,n) for(i=x;i<=n;i++)
typedef vector<int> vi;
typedef vector<ll> vl;

const int mod = 1e9+7;
const int N = 2e5+5;

vector<vl> mul(vector<vl> a,vector<vl> b){
    ll n=a.size(),i,j,k;
    vector<vl> ans(n,vl(n,0));
    fo(i,n) fo(j,n) fo(k,n) ans[i][j]=(ans[i][j]+a[i][k]*b[k][j]%mod)%mod;
    return ans;
}

vector<vl> mpow(vector<vl> a,ll b){
    ll i,n=a.size();
    vector<vl> res(n,vl(n,0));
    fo(i,n) res[i][i]=1;
    while(b){
        if(b&1) res=mul(res,a);
        a=mul(a,a);
        b>>=1;
    }
    return res;
}

void solve(int test){
    ll n;
    char c;
    cin>>n>>c;
    if(n==3&&c=='g'){
        cout<<4<<nl;
        return;
    }
    if(n==3&&c=='f'){
        cout<<5<<nl;
        return;
    }
    if(n==4&&c=='f'){
        cout<<11<<nl;
        return;
    }
    if(n==1){
        cout<<1<<nl;
        return;
    }
    if(n==2){
        cout<<2<<nl;
        return;
    }
    vector<vl> v={{1,2,1,1,0},{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0}};
    v=mpow(v,n-4);
    vector<vl> v1={{2,0,1},{1,0,0},{0,1,0}};
    v1=mpow(v1,n-3);
    if(c=='f'){
        cout<<(11*v[0][0]+5*v[0][1]+2*v[0][2]+v[0][3]+v[0][4])%mod<<nl;
    }else{
        cout<<(4*v1[0][0]+2*v1[0][1]+v1[0][2])%mod<<nl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int i,t=1;
    cin>>t;
    fo(i,t){
        solve(i+1);
    }
    return 0;
}

According to me, it should run in O(QlogN), which should pass, but it gave TLE in almost all testcases. Please let me know why it failed

P.S:- The recurrences after solving came out to be: f(n)=f(n-1)+2*f(n-2)+f(n-3)+f(n-4) g(n)=2*g(n-1)+g(n-3)

Hi everyone!

I recently submitted a solution on Codeforces and got WA on 2122nd testcase. It is not possible to view it as after a few testcases it shows '...'

Would someone please help me to debug? What I tried to do is brute all possible values of a[j] for a given a[i]. I stored the original indices in a map because sorting the array would change it.

Problem Link

My submission: 178126818

Hello guys,

I recently submitted a problem which generated the following error:

Diagnostics detected issues [cpp.clang++-diagnose]: =================================================================
==3304==ERROR: AddressSanitizer: global-buffer-overflow on address 0x00282658 at pc 0x00161cd6 bp 0x1085faf4 sp 0x1085faf0
READ of size 1 at 0x00282658 thread T0
    #0 0x161cd5 in solve K:\codeforces71\098eeebfbac393649f6c79d4673741ac\compile-36d3577b3eaacceb8ba51a42a87e5d9a\p71.cpp:45
    #1 0x162380 in main K:\codeforces71\098eeebfbac393649f6c79d4673741ac\compile-36d3577b3eaacceb8ba51a42a87e5d9a\p71.cpp:59
    #2 0x1dbda1 in __scrt_common_main_seh f:\dd\vctools\crt\vcstartup\src\startup\exe_common.inl:283
    #3 0x7633343c in BaseThreadInitThunk+0x11 (C:\Windows\syswow64\kernel32.dll+0x7dd7343c)
    #4 0x770f9831 in RtlInitializeExceptionChain+0x62 (C:\Windows\SysWOW64\ntdll.dll+0x7dea9831)
    #5 0x770f9804 in RtlInitializeExceptionChain+0x35 (C:\Windows\SysWOW64\ntdll.dll+0x7dea9804)

0x00282658 is located 40 bytes to the left of global variable 'std::num_get<char>::id' defined in 'C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.11.25503\include\xlocnum:1231:60' (0x282680) of size 4
0x00282658 is located 0 bytes to the right of global variable 's' defined in 'p71.cpp:32:12' (0x282640) of size 24
SUMMARY: AddressSanitizer: global-buffer-overflow K:\codeforces71\098eeebfbac393649f6c79d4673741ac\compile-36d3577b3eaacceb8ba51a42a87e5d9a\p71.cpp:45 in solve
Shadow bytes around the buggy address:
  0x30050470: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x30050480: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x30050490: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x300504a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x300504b0: 00 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 f9
=>0x300504c0: 00 00 00 f9 f9 f9 f9 f9 00 00 00[f9]f9 f9 f9 f9
  0x300504d0: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
  0x300504e0: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
  0x300504f0: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
  0x30050500: 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
  0x30050510: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==3304==ABORTING

I looked up online and found an article saying this arises due to segmentation fault. When I declared all variables globally, the error persisted.

The only difference was that instead of WA I got RTE. Could someone pls help me with this issue?

P.S: The submission ID is #177257400 and the problem statement is this

Hi Everyone,

Today I encountered a new type of problem which involved an interactive task. The problem link is as follows:

https://atcoder.jp/contests/abc269/tasks/abc269_e

These kind of problems are new to me. Nevertheless, I tried solving it and here is my solution (in C++):

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
    ll t,i,n,a[4];
    cin>>n;
    while(true){
        for(i=0;i<4;i++) a[i]=(rand()%n)+1;
        cout<<"? "<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<endl;
        // cout<<flush;
        cin>>t;
        if(t==0){
            cout<<"! "<<a[1]<<" "<<a[3]<<endl;
            // cout<<flush;
            exit(0);
        }
        if(t==-1) exit(0);
    }
    return 0;
}

I received WA after submitting this solution. I also tried adding "cout<<flush" which are commented now, but that did not help.

Can someone pls help me to correct the solution?