Link
I got the main idea of the solution but I implemented the update function in a different way:
I used three segment trees:
1. stsum : for finding the sum in the range
2. st1 : for finding number of ones in the range
3. st2 : for finding number of twos in the range

void update(int l, int r) {
    if (r < l) return;
    if (n1(l, r) + n2(l, r) == r - l + 1) return;
    if (r - l <= 1) {
        for (int i = l; i <= r; ++i) {
            stsum.update(i, d[a[i]]);
            a[i] = d[a[i]];
            if (a[i] == 2) {
                st2.update(i, 1);
            }
        }
        return;
    }
    int mid = (r + l) / 2;
    update(l, mid);
    update(mid + 1, r);
}

Above, functions n1(l, r): returns number of 1's in the range l to r and n2(l, r) returns the number of 2's in the range.
I'm calling this function whenever there is update query.
What is the correct time complexity of the solution using this function for update?

Link
According to the editorial, the function becomes linear for n>=12. I dont understand why does this happen . Can someone elaborate?

Link
I tried solving this using the ordered_set gnu pbds
I did dfs along with using swap and move methods for merging the sets of each node's children. The time complexity should be nlogn but why is it giving TLE on test 15?

ordered_set dfs(int p, int e) {
    d[p] = w[p] + d[e];
    ordered_set ret;
    for (auto u : adj[p]) {
        if (u != e) {
            auto x = dfs(u, p);
            if (x.size() > ret.size()) {
                swap(x, ret);
            }
            for (auto u : x) {
                ret.insert(u);
            }
        }
    }
    //compute the answer for nope p
    ans[p] = ret.order_of_key({d[p], INF});
    ret.insert({d[p] - a[p], p});
    return move(ret);
}

link

void solve() {
    int n, m; cin >> n >> m;
    vector<pair<int, int> > v; v.reserve(n * m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            v[m * (i - 1) + j - 1] = {i, j};
        }
    }
    bool low = true;
    int l = 0, r = m * n - 1;
    while (r >= l) {
        pair<int, int> u;
        if (low) {
            u = v[l]; l++;
            low = false;
        }
        else {
            u = v[r]; r--;
            low = true;
        }
        cout << u.first << " " << u.second << endl;
    }
}

As the constraint is m*n<=10^6, this solution should work under 1 second but it's taking about 1871 ms in one of the TLE'd test case. Why could this be happening?

Problem Link

<---------------------Editorial Solution start-------------------->
If there are multiple people with the same set of skills (i.e., the same values of a), it's optimal to take each of them to the camp as they won't think they're better than everyone else.

Now consider a person i which has a different set of skills than everyone else.

If they have a strictly smaller set of skills than someone already in the group, they can safely be included in the group. If they don't, we can prove that they can't ever be included in the group. This allows us to implement a simple O(n2) solution: first take all people that have an equal set of skills as someone else, and then include everyone else who has a strictly smaller set of skills than someone already in the group.

<---------------------Editorial Solution end-------------------->

Here, let n=6 , and denoting students as A,B,C,D,E,F
a values : A,B: 01100111 , C,D : 00110100 , E: 10100011, F: 10010100
b values : anything
Now according to the editorial, we will take A,B,C,D first as they occur multiple times. But we won't take E or F because they are not "smaller" than those already present in the group(their most significant bit is set).
But I think we can take all of them without any problem as E and F have the most significant bit in common.
I don't see how all together they will not satisfy the given condition..

Link

    ll n, c;
    cin>>n>>c;
    vector<pair<ll, ll> > v;
    for(int i=0; i<n; ++i)
    {
        ll a,b,p;
        cin>>a>>b>>p;
        v.push_back({a, p});
        v.push_back({b+1, -p});
    }
    sort(v.begin(), v.end());
    ll ans = 0;
    ll accum = 0;
    for(int i=0; i<2*n; ++i)
    {
        ll a = v[i].first, p = v[i].second;
        accum += p;
        if(i+1<2*n)
        {
            ans += min(accum*(v[i+1].first-a), c*(v[i+1].first-a));
        }
    }
    cout<<ans<<endl;

After submitting this solution, there is a single test case out of 28 which is giving WA. And I don't see what's wrong with this solution. I don't think the problem is with constraints either.

Link I found the number of possible ways of having sum between a and b using dp. The problem is that this number can exceed the long long limits and hence for larger values, my solution is not working.

Problem :Link I applied the sparse table algorithm here, but I'm somehow getting a runtime error in one of the test cases. Also, I tried to see where is it going wrong, and in the code, the first "here" is printing, and the second "here" after the declaration of the minimum_query array(mq) is not running(for the test case which is giving runtime error). So I guess that the problem should be somewhere there?

void solve()
{

    int n, q;
    cin>>n>>q;
    int sz = n+1;
    vector<int> a(sz);
    for(int i=1; i<=n; ++i)
    {
        cin>>a[i];
    }
    **cout<<"here"<<endl;**
    
    //sparse table algorithm
    int mq[sz][sz];

    **cout<<"here"<<endl;**

    for(int i=1; i<=n; ++i)
        mq[i][i]=a[i];
    int log2n = floor(log2(n));
    for(int k=0; k<=log2n; ++k)
    {
        int gap = 1<<k;
        int till = n-gap;
        for(int i=1; i<=till; ++i)
        {
            int u=i;
            int v=u+gap, w=gap/2;
            mq[u][v]=min(mq[u][u+w], mq[u+w+1][v]);
        }
    }

    while(q--)
    {
        int u,v;
        cin>>u>>v;
        int len = v-u;
        if(v==u)
        {
            cout<<mq[u][v]<<endl;
            continue;
        }
        int k = 1<<((int)(log2(len)));
        int ans = min(mq[u][u+k], mq[v-k][v]);
        cout<<ans<<endl;
    }
}

Problem : Link. I simply did bfs from node 1 and found the maximum distance from this node to all other nodes

const int INF = 1e9;
const int sz = 1e5+1;
int n,m;
vector<int> last(sz);
vector<vector<int> > adj(sz);
vector<int> d(sz,0);
void solve()
{
    cin>>n>>m;

    for(int i=0; i<m; ++i)
    {
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
    }

    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int s = q.front();
        q.pop();

        for(auto u : adj[s])
        {
            if(d[s]+1>d[u])
            {
                d[u]=1+d[s];
                last[u]=s;
                q.push(u);
            }
        }
    }
    if(d[n]==0)
    {
        cout<<"IMPOSSIBLE"<<endl;
        return;
    }
    vector<int> ans;
    int k=n;
    while(k!=1)
    {
        ans.push_back(k);
        k=last[k];
    }
    ans.push_back(1);
    reverse(ans.begin(), ans.end());
    cout<<1+d[n]<<endl;
    for(int i=0; i<ans.size(); ++i)
        cout<<ans[i]<<" ";
    cout<<endl;
}
int main()
{
    solve();
}

So the solution is O(n+m) but still, there is TLE in one case. Why?

Pproblem: Link. I have already seen the

and I did the required changes. But still, there are 3 test cases that are not passing.

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
const int sz = 1e5+1;

int n,m;
vector<bool> prd(sz);
void dijkstra(vector<vector<pair<int, int> > >& adj, vector<ll>& dist, int k)
{
    for(int i=1; i<sz; ++i)
    {
        prd[i]=false;
    }
    priority_queue<pair<int, int> > q;
    dist[k]=0;
    q.push({0,k});
    while(!q.empty())
    {
        int a = q.top().second;
        q.pop();
        if(prd[a])continue;
        prd[a]=true;
        for(auto u : adj[a])
        {
            int b = u.first, w = u.second;
            if(dist[a]+w<dist[b])
            {
                dist[b]=w+dist[a];
                q.push({-dist[b],b});
            }
        }
    }
}
void solve()
{
    cin>>n>>m;
    vector<vector<pair<int, int> > > adj(sz), adj1(sz);
    vector<tuple<int, int, int> > edges;
    for(int i=0; i<m; ++i)
    {
        int a,b,w;
        cin>>a>>b>>w;
        adj[a].push_back({b,w});
        adj1[b].push_back({a,w});
        edges.push_back({a,b,w});
    }
    vector<ll> dist(sz, LINF), dist1(sz,LINF);
    dijkstra(adj, dist,1);
    dijkstra(adj1, dist1,n);
    ll ans = LINF;
    for(auto e : edges)
    {
        int a,b,w;
        tie(a,b,w) = e;
        ans = min(ans, dist[a]+dist1[b]+w/2);
    }
    cout<<ans<<endl;
}

int main()
{
    solve();
}

Problem Link

Here is my implementation: * Here, sn and en stands for starting node and ending node respectively, and mini_map is the 2d array showing path of shortest distance from starting node to all other reachable nodes. Rest is Breadth-First Search.

I don't see whats making this solution so long

char a[1001][1001];
bool visited[1001][1001];
char mini_map[1001][1001];

bool valid(int i, int j)
{
    if(i>=0 && i<n && j>=0 && j<m && a[i][j]!=-1 && visited[i][j]==false) return true;
    else return false;
}
void solve() {
    cin>>n>>m;
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j)
        {
            char x;
            cin>>x;
            if(x=='.')a[i][j]=0;
            else if(x=='#') a[i][j]=-1;
            else if(x=='A')
            {
                a[i][j]=1;
                sn_i = i;
                sn_j = j;
            }
            else
            {
                a[i][j]=2;
                en_i = i;
                en_j = j;
            }
            visited[i][j]=false;
            mini_map[i][j]='0';
        }
    }
    queue<pair<int, int> > q;
    q.push({sn_i, sn_j});
    while(!q.empty())
    {
        pair<int, int> s = q.front();
        int sf = s.first, ss = s.second;
        q.pop();
        if(valid(sf+1,ss))
        {
            visited[sf+1][ss] = true;
            mini_map[sf+1][ss] = 'D';
            q.push({sf+1,ss});
        }
        if(valid(sf-1,ss))
        {
            visited[sf-1][ss]=true;
            mini_map[sf-1][ss]='U';
            q.push({sf-1,ss});
        }
        if(valid(sf,ss+1))
        {
            visited[sf][ss+1]=true;
            mini_map[sf][ss+1]='R';
            q.push({sf,ss+1});
        }
        if(valid(sf,ss-1))
        {
            visited[sf][ss-1]=true;
            mini_map[sf][ss-1]='L';
            q.push({sf,ss-1});
        }
    }
    int cnt = 0;
    string res = "";
    int i=en_i, j = en_j;
    while(i!=sn_i || j!=sn_j)
    {
        char x = mini_map[i][j];
        if(x=='R') j--;
        else if(x=='L') j++;
        else if(x=='U') i++;
        else if(x=='D') i--;
        else
        {
            cout<<"NO"<<endl;
            return;
        }
        res = res+x;
        cnt++;
    }
    reverse(res.begin(), res.end());
    cout<<"YES"<<endl<<cnt<<endl<<res<<endl;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

This is the problem I am talking about, although this has happened with some other problems as well. The solution is straightforward using dp, but I was getting TLE for 2 test cases, and the time complexity was O(n*x) so I thought some optimization was required, so I then looked at his stream and he did exactly the same as me, Only minor differences, which I changed in my solution to make it look exactly like him. But Still! It's still showing TLE while his was accepted! Here is the solution:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll N =1e9+7;
int main()
{
    int n, x;
    cin>>n>>x;
    int a[n];
    for(int i=0; i<n; ++i)
    {
        cin>>a[i];
    }
    ll cnt[x+1]={0};
    cnt[0]=1;
    for(ll i=1; i<=x; ++i)
    {
        for(ll j = 0; j<n; ++j)
        {
            if(i>=a[j])
            cnt[i] = (cnt[i]+cnt[i-a[j]])%N;
        }
    }
    cout<<cnt[x];
}

this is the problem. Here is what my solution was:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        ll queued=0;
        bool gotit = false;
        for(ll i=0; i<n; ++i)
        {
            ll x;
            cin>>x;
            queued= queued + (x-k);
            if(queued<0)
            {
                cout<<i+1<<endl;
                gotit = true;
                break;
            }
        }
        if(gotit)
            continue;

        if(queued>0)
        {
            cout<<n+1+queued/k<<endl;
        }
        else cout<<n+1<<endl;
    }
}

and as expected, it was giving correct results in test cases except for one, which was giving runtime error, the error which comes by the division of 0. (and to be sure, I even tried running infinite loop if k==0, and then it showed TLE at the same test case.) Now the thing is it is given k>0 and when I tried a little different technique, it was accepted. So what is the problem here?

Problem Here is what I tried:

#include<iostream>
#include<vector>
#include<string>
using namespace std;
using ll = long long;

int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        string s;
        cin>>s;
        vector<ll> len, p;
        ll i=0, j=0;
        while(i<n && j<n)
        {
            while(j<n && s[i]==s[j])
                j++;
            p.push_back(j-i);
            i=j;
        }
        ll ans = 0;
        for(ll i=0; i<p.size(); ++i)
        {
            if(p[i]<2)
            {
                ans++;
                i++;
            }
            else
                ans++;
        }
        cout<<ans<<endl;
    }
}

Can someone briefly explain where am I going wrong?

here is the problem. At first, I couldn't solve it on my own so I took help from the editorial and this is what I came up with:

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
using ll=long long;
int main()
{
    ll n;
    cin>>n;
    vector<ll> c;
    for(ll i=0; i<n; ++i)
    {
        ll x;
        cin>>x;
        c.push_back(x);
    }
    vector<string> vec;
    for(ll i=0; i<n; ++i)
    {
        string f;
        cin>>f;
        vec.push_back(f);
    }
    ll dp[n][2];
    for(ll i=0; i<=n; ++i)
    {
        for(ll j=0; j<2; ++j)
        {
            dp[i][j] = numeric_limits<ll>::max()/2;
        }
    }
    dp[0][0]=0;
    dp[0][1]=c[0];
    ll n1 = 0, n2 = 0;
    for(ll i=1; i<n; ++i)
    {
        n1 = 0;
        n2 = 0;
        if(vec[i]>=vec[i-1])
            dp[i][0]=min(dp[i][0],dp[i-1][0]);
        else n1++;
        reverse(vec[i-1].begin(), vec[i-1].end());
        if(vec[i]>=vec[i-1])
            dp[i][0]=min(dp[i][0], dp[i-1][1]);
        else n1++;
        reverse(vec[i-1].begin(), vec[i-1].end());
        reverse(vec[i].begin(), vec[i].end());
        if(vec[i]>=vec[i-1])
            dp[i][1]=min(dp[i][1],dp[i-1][0]+c[i]);
        else n2++;
        reverse(vec[i-1].begin(), vec[i-1].end());
        if(vec[i]>vec[i-1])
            dp[i][1]=min(dp[i][1], dp[i-1][1]+c[i]);
        else n2++;
        reverse(vec[i-1].begin(), vec[i-1].end());
        reverse(vec[i].begin(), vec[i].end());
        if(n1==2 && n2==2)
            break;

    }
    if(n1==2 && n2==2)
        cout<<-1;
    else cout<<min(dp[n-1][0], dp[n-1][1]);
}

but it's giving me wrong answer.Can anyone help with whats wrong?