Hello Codeforces, I was trying to solve the question : Question. I tried to solve it in a knapsack dp kind of manner. It does not show on what testcase I am going wrong , infact it does not show any testcases apart from the sample test cases. so it's my kind request if anybody can help me regarding this question

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace chrono;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define debug(x...) { cout << "(" << #x << ")" << " = ( "; PRINT(x); } 
template <typename T1> void PRINT(T1 t1) { cout << t1 << " )" << endl; }
template <typename T1, typename... T2>
void PRINT(T1 t1, T2... t2) { cout << t1 << " , "; PRINT(t2...); }
#define all(v) (v).begin(), (v).end()
//(data type to be stored (pair,long long,string,vector),"null_type"(specifically used for set),comparator,underlying tree,class denoting the policy for updating node invaralong longs)
typedef tree < pair<long long,long long>, null_type,less<pair<long long,long long>>,rb_tree_tag,tree_order_statistics_node_update > pbds;
void solve();
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.setf(ios::fixed);
    cout.precision(10);
    long long t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}
bool cmp(pair<long long,long long>&a,pair<long long,long long>&b)
{
    if(a.first==b.first);
    return a.second<b.second;

    return a.first>b.first;
}
void solve()
{
    long long n,m;
    cin>>n>>m;

    vector<pair<long long,long long>>v;
    long long sum=0;
    for(long long i=0;i<n;i++)
    {
        long long x,y;
        cin>>x>>y;
        sum+=y;
        v.push_back({x,y});
    }
    sort(all(v),cmp);
    vector<vector<long long>>dp(n+1,vector<long long>(n+1,-1));
    function<long long(long long,long long)>f=[&](long long i,long long count)->long long{

        if(count>=n)
        {
            return 0;
        }
        if(i==n)
        {
            return (long long)(1e12);
        }
        if(dp[i][count]!=-1)
        return dp[i][count];

        long long res=f(i+1,count);

        res=min(res,v[i].second+f(i+1,min(n,count+v[i].first+1)));

        return dp[i][count]= res;
    };

    long long res=f(0,0);
    // debug(res);
    res=min(res,sum);
    cout<<(sum-res)<<endl;
}

I am getting WA on testcase 2. I am unable to think of any counter test case or what I am doing wrong. It would be really helpful if somebody could help me regarding this question . Thank you in advance.

Hello Codeforces, I came across an interesting error while solving this problem : https://mirror.codeforces.com/contest/1950/problem/G which I am not able to understand as to why this is happening?

https://mirror.codeforces.com/contest/1950/submission/255101098 (This solution did not get accepted but gave runtime error) https://mirror.codeforces.com/contest/1950/submission/255101528 (This solution got accepted)

Note there is very little difference between the two

In the first solution I have initialized vector as : vector<vector<int>>dp(n,vector<int>((1<<n),-1));

In the second solution I have initialized vector as : vector<vector<int>>dp((1<<n),vector<int>(n,-1));

I really don't understand what is causing this error. Any help would be appreciated. Thank you !

Hello codeforces community, I am getting a weird TLE on this problem: https://mirror.codeforces.com/contest/1932/problem/E

Here is my code submission : https://mirror.codeforces.com/contest/1932/submission/250505488

I am sure my solution is linear but still I am getting TLE.

I am unable to find the error which is causing TLE. Please help me. Thank you

Hello codeforces community,

I was trying to solve the problem : https://www.spoj.com/problems/ADAPHOTO/

But I am getting TLE on it

Here is my code:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace chrono;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define debug(x...) { cout << "(" << #x << ")" << " = ( "; PRINT(x); } 
template <typename T1> void PRINT(T1 t1) { cout << t1 << " )" << endl; }
template <typename T1, typename... T2>
void PRINT(T1 t1, T2... t2) { cout << t1 << " , "; PRINT(t2...); }
#define all(v) (v).begin(), (v).end()
//(data type to be stored (pair,long long,string,vector),"null_type"(specifically used for set),comparator,underlying tree,class denoting the policy for updating node invaralong longs)
typedef tree < pair<long long,long long>, null_type,less<pair<long long,long long>>,rb_tree_tag,tree_order_statistics_node_update > pbds;
void solve();
#define MAXLEN 1000010

 constexpr uint64_t mod = (1ULL << 61) - 1;
const uint64_t seed = chrono::system_clock::now().time_since_epoch().count();
const uint64_t base = mt19937_64(seed)() % (mod / 3) + (mod / 3);
 uint64_t base_pow[MAXLEN];
int64_t modmul(uint64_t a, uint64_t b){
    uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
    uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
    uint64_t ret = (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
    ret = (ret & mod) + (ret >> 61);
    ret = (ret & mod) + (ret >> 61);
    return ret - 1;
}
 
void init(){
    base_pow[0] = 1;
    for (int i = 1; i < MAXLEN; i++){
        base_pow[i] = modmul(base_pow[i - 1], base);
    }
}
 
struct chash {
    const int RANDOM = (long long)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
    static unsigned long long hash_f(unsigned long long x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    static unsigned hash_combine(unsigned a, unsigned b) { return a * 31 + b; }
    int operator()(int x) const { return hash_f(x)^RANDOM; }
};
 
struct PolyHash{
    /// Remove suff vector and usage if reverse hash is not required for more speed
    vector<int64_t> pref;
 
    PolyHash() {}
 
    template <typename T>
    PolyHash(const vector<T>& ar){
        if (!base_pow[0]) init();
 
        int n = ar.size();
        pref.resize(n + 3, 0);
 
        for (int i = 1; i <= n; i++){
            pref[i] = modmul(pref[i - 1], base) + ar[i - 1] + 997;
            if (pref[i] >= mod) pref[i] -= mod;
        }
    }
    /*https://usaco.guide/gold/string-hashing?lang=cpp*/
    /*  pref[r+1]=( p^r+1 + a[0]*p^(r) + a[1]*p^(r-1) + a[2]*p^(r-2) + ..+ a[l-1]*p^((r+1)-(l-1+1))+a[l]*p^((r+1)-(l+1))  .. a[r-1]*p + a[r] )
        pref[l]=( p^l + a[0]*p^(l-1) + a[1]*p^(l-2) + a[2]*p^(l-3) + ...a[l-2]*p +  a[l-1])

        p^(r-l+1)*pref[l] = ( a[0]*p^(r) + a[1]*p^(r-1) +.... + a[l-1]*p^(r-l+1) )

        pref[r+1]-(p^(r-l+1))*pref[l]=a[l]*p^(r-l)+ a[l+1]*p^(r-l-1)+.... + a[r-1]*p + a[r]

    */
    PolyHash(const char* str)
        : PolyHash(vector<char> (str, str + strlen(str))) {}
 
    uint64_t get_hash(int l, int r){
        int64_t h = pref[r + 1] - modmul(base_pow[r - l + 1], pref[l]);
        return h < 0 ? h + mod : h;
    }
};
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.setf(ios::fixed);
    cout.precision(10);
        solve();
}
void solve()
{
    string a;
    cin>>a;
    string b;
    cin>>b;
    
    int n1=a.length();
    int n2=b.length();
     
    const char *c1=a.c_str();
    const char *c2=b.c_str();
   PolyHash s1(c1);
   PolyHash s2(c2);
   
   int low=1;
   int res=0;
   int high=min(n1,n2);

   while(low<=high)
   {
      int mid=(low+high)/2;
      
       cc_hash_table<uint64_t,uint64_t,chash>mp;
       int flag=0;
    // unordered_map<long long,long long>mp2;
        for(int i=0;i+mid-1<n1;i++)
        {
            uint64_t x=s1.get_hash(i,i+mid-1);
            // debug(x,mid,1);
            if(mp.find(x)==mp.end())
            mp[x]++;
        }
        for(int i=0;i+mid-1<n2;i++)
        {
            uint64_t x=s2.get_hash(i,i+mid-1);
            // debug(x,mid,2);
            if(mp[x]>0)
            {
                flag=1;
                break;
            }
        }
      if(flag)
      {
        // cout<<mid<<endl;
        res=mid;
        low=mid+1;
      }
      else
      {
        high=mid-1;
      }
   }
   cout<<res<<endl;

}

any help would be appreciated. Thank you in advance!