Hello Codeforces community,

I've been working on a problem involving queue dynamics and chair allocation, and I'm seeking your expertise to find an efficient solution that fits within tight constraints.

Problem Statement: Description: You are given a queue of n people, numbered from 1 to n. Each person i has an initial preferred chair number Pi, which is a positive integer. There is an infinite number of chairs, labelled with positive integers starting from 1.

The queue operates under the following rules: Queue Processing: People are processed in the order they appear in the queue.

Chair Allocation Process: When a person reaches the front of the queue, they attempt to sit on their current preferred chair Pi.

If the chair Pi is unoccupied: They sit on chair Pi and leave the queue.

If the chair Pi is already occupied: They are sent to the end of the queue and their preferred chair number increases by 1. They will attempt to sit on this new preferred chair when they reach the front of the queue again.

This process continues until all people have been allocated a chair.

Objective: Determine the chair number allocated to each person, in the order of their original positions in the queue (from person 1 to person n).

Input Format: The first line contains an integer n (1 <= n <= 10^5), the number of people in the queue. The second line contains n space-separated positive integers P1, P2, ..., Pn. (1 <= Pi <= n), where Pi is the initial preferred chair number of the i-th person.

Output: n space-separated integers, where the i-th integer represents the chair number allocated to the i-th person.

Here is the problem link: Problem Link: Minimum Cost to Convert String II

Here, I treated each string in the original and changed vectors as unique graph nodes. This involved computing the hash value for every string and subsequently compressing these values. Then I used Floyd-Warshall algorithm to facilitate the establishment of connections between these compressed nodes.

Since, the combined number of unique strings in the original and changed vectors would not exceed 200. We can easily apply Floyd-Warshall.

Now, having precomputed hash values for both the source and target strings, I can easily find the hash value of any substring in constant time, as it is a crucial step during dynamic programming (DP) transitions. The time complexity in the DP phase is O (string. length^2). Overall, our time complexity can reach a maximum of N^2*logN, comfortably below the given time limit.

Why am I still getting TLE?

MY CODE:

map<int,int>comp;
vector<vector<ll>>dist;
const static int N= 1001;
int powers[N];
int invPowers[N];

int n;
const ll INF= 1e13;
vector<ll>dp;

const int mod= 1e9+9;
const int pr= 29;

int binExp(int a, int b, int mod){
int ans=1;
while(b>0){
    if(b&1ll)ans=(ans*1ll*a)%mod;
    a=(a*1ll*a)%mod;
    b>>=1ll;
}
return ans;
}
void precompute(){
    powers[0]=1;
    powers[1]=pr;
    for(int i=1;i<N; i++)powers[i]= (pr*1ll*powers[i-1])%mod;
    invPowers[0]=1;
    for(int i=1; i<N; i++)invPowers[i]= binExp(powers[i], mod-2,mod);
}
void rollingHash(string &s, vector<int>&hashS){
    int sz= s.size();
    for(int  i=0; i<sz; i++){
        int hash= (powers[i]*1ll*(s[i]-'a'+1))%mod;
        hashS.push_back(hash);
    }
    for(int i=1; i<sz; i++)hashS[i]= (hashS[i]+hashS[i-1])%mod;
}
ll findSubstringHash(int &i, int &j, vector<int>&hashArr){
    ll inv= invPowers[i];
    ll val= (hashArr[j]-(i==0?0:hashArr[i-1]));
    if(val<0)val+= mod;
    val=(val*inv)%mod;

    return val;
}

ll f(int i, string &s, string &t, vector<int>&hashS, vector<int>&hashT){
    if(i>=n)return 0;

    if(dp[i]!=-1)return dp[i];
    ll ans= INF;

    for(int j=i; j<n; j++){
        int hash1= findSubstringHash(i,j,hashS);
        int hash2= findSubstringHash(i,j,hashT);
        if(hash1==hash2)ans=min(ans, f(j+1,s,t,hashS,hashT));
        else if(comp.find(hash1)!=comp.end() && comp.find(hash2)!=comp.end()){
            int i1= comp[hash1], j1= comp[hash2];
            ans=min(ans, dist[i1][j1]+ f(j+1,s,t,hashS,hashT));
        }    
    }

    return dp[i]= ans;
}

long long minimumCost(string s, string t, vector<string>& org, vector<string>& ch, vector<int>& cost) {
    int sz= org.size();
    vector<int>hashS, hashT;
    precompute();
    rollingHash(s,hashS);
    rollingHash(t,hashT);
    vector<int>storeHashes1, storeHashes2;
    for(int i=0; i<sz; i++){
        vector<int>a,b;
        rollingHash(org[i],a);
        rollingHash(ch[i],b);
        storeHashes1.push_back(a.back());
        storeHashes2.push_back(b.back());
        comp[a.back()];
        comp[b.back()];
    }

    int ptr=0;
    for(auto &ele: comp)ele.second=ptr++;

    dist.resize(ptr,vector<ll>(ptr,INF));

    for(int i=0; i<ptr; i++)dist[i][i]=0;


    for(int i=0; i<sz; i++){

        int i1= comp[storeHashes1[i]];
        int j1= comp[storeHashes2[i]];

        if(dist[i1][j1]>cost[i])
        dist[i1][j1]= cost[i];
    }

   //10^6
    for(int k=0; k<ptr; k++){
        for(int i=0; i<ptr; i++){
            for(int j=0; j<ptr; j++){
                if((dist[i][k]!=INF && dist[k][j]!=INF) && dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]= dist[i][k]+dist[k][j];
            }
        }
    }

    n=s.size();

    dp.resize(n+1,-1);
    ll ans= f(0,s,t,hashS,hashT);

    if(ans>=INF)return -1;
    return ans;

}

Hi All, In the Spoj Problem ABCPATH- ABC Path, I am not able to figure out: why my code is getting runtime error?

Here is the link to problem: ABC PATHhttps://www.spoj.com/problems/ABCPATH/

Here is my code: ~~~~~

pragma GCC optimize("O3,unroll-loops")

pragma GCC optimize(3, "Ofast", "inline")

include<bits/stdc++.h>

using namespace std; using namespace chrono;

define endl "\n"

define _USE_MATH_DEFINES

include

ifndef M_PI

#define M_PI 3.14159265358979323846

endif

define int long long int

define pb push_back

define mk make_pair

define ppb pop_back

define pf push_front

define ppf pop_front

define all(x) (x).begin(),(x).end()

define ub upper_bound

define lb lower_bound

define uniq(v) (v).erase(unique(all(v)),(v).end())

define sz(x) (int)((x).size())

define fr first

define sc second

define pii pair<int,int>

define rep(i,a,b) for(int i=a;i<b;i++)

define mem1(a) memset(a,-1,sizeof(a))

define mem0(a) memset(a,0,sizeof(a))

define ppc __builtin_popcount

define ppcll __builtin_popcountll

int const N=2*1e5+10; //int const INF=1e18; int mod=1e9+7; int mod1=998244353; const int INF=1e4;

define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int r,c; int dx[]={1,1,-1,-1,0,0,1,-1}; int dy[]={1,-1,1,-1,1,-1,0,0}; bool vis[60][60]; vector<vector>grid; int mx=0;

bool is_valid(int i, int j){ return (i>=0 && j>=0 && i<r && j<c); }

void dfs(int i, int j, int l){ if(vis[i][j])return;

vis[i][j]=1; mx=max(mx,l);

rep(k,0,8){ int x=i+dx[k]; int y=j+dy[k]; if(vis[x][y] || !is_valid(x,y))continue;

if(grid[x][y]-grid[i][j]==1)
  dfs(x,y,l+1);

} }

void solve(){ int k=0; while(cin>>r>>c){ if(!r && !c)break;

grid.resize(r,vector<char>(c));
// vis.resize(r,vector<bool>(c,false));
// cout<<grid.size()<<" "<<grid[0].size()<<endl;
rep(i,0,r){
  string s; cin>>s;
  rep(j,0,c){
    grid[i][j]=s[j];
   // cout<<vis[i][j]<<" ";
  }
 // cout<<endl;
}
memset(vis,false,sizeof(vis));

// mx=0;

rep(i,0,r){
  rep(j,0,c){
    if(grid[i][j]=='A')dfs(i,j,1);
  }
}

cout<<"Case "<<++k<<": "<<mx<<endl;
mx=0;

} return; }

signed main(){ #ifndef ONLINE_JUDGE freopen("INPUT1.txt","r",stdin); freopen("out1.txt","w",stdout); #endif

fastio();
auto start1 = high_resolution_clock::now();
int t=1;
//cin>>t;

// precompute();

//fill_dp();
while(t--){
  solve();
}
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
cout << "Time: " << duration . count() / 1000 <<"ms"<<endl;
#endif

return 0; }

~~~~~

`