ECJN207 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sunita Sen
Tester: Soham Chakrabarti
Editorialist: Sunita Sen

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Dynamic Programming - Digit DP

PROBLEM:

Given a string S ,count the number of strings which come before string S( including S) in the dictionary and are of the same length as S such that total sum of character values at prime position is a prime number.

EXPLANATION:

This problem can be solved using Digit DP.
However, instead of digits here we are using characters.

This is a really cool blog explaining Digit DP.

Detailed editorial will be updated soon.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define dfor(i,a,b) for(ll i=(a);i>=(b);i--)
#define mem(u, vis) memset(u, vis, sizeof(u))
#define ll long long
#define ull unsigned long long
#define MOD  1000000007
#define MAX  1e9
#define pb   push_back
#define F    first
#define S    second


ll dp[2000][10000][2];
// smaller ? 0 - no 1: yes
vector<bool> isprime(100000, true);

void prime(int n){
	isprime[0] = isprime[1] = false;
	for (int i = 2; i <= n; i++) {
	    if (isprime[i] && (long long)i * i <= n) {
	        for (int j = i * i; j <= n; j += i)
	            isprime[j] = false;
	    }
	}
}

ll calc_dp(string s, ll pos, ll sum, ll smaller){
	if(pos == s.length()){
		if(isprime[sum]){
			return 1;
		}
		return 0;
	}
	if(dp[pos][sum][smaller] != -1){
		return dp[pos][sum][smaller];
	}
	ll limit = 'z' - 'a';
	ll res = 0;
	bool primepos = isprime[pos];

	if(!smaller){
		limit = s[pos] - 'a';
	}

	for(ll i = 0; i <= limit ; ++i){
		ll ns;
		if(i < limit){
			ns = 1;
		}
		else
			ns = smaller;
		if(primepos){
			res = (res   + calc_dp(s, pos + 1, sum + i, ns)%MOD)%MOD;
		}
		else{
			res = (res + calc_dp(s, pos + 1, sum, ns)%MOD)%MOD;
		}
	}

	dp[pos][sum][smaller] = res;
	return res;
}


signed main() {
	ll t=1;
	cin>>t;
	prime(100000);
	while(t--){
		string s;
		cin>>s;
		mem(dp,-1);
		cout<<(calc_dp(s,0,0,0))%MOD<<endl;
	}
	
}
Tester's Solution
/* nuttela - Soham Chakrabarti */
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define all(v) v.begin(),v.en()
#define pb push_back
#define ins insert
#define rep(i,j,k) for(ll i=j;i<k;i++)
#define per(i,j,k) for(ll i=j;i>=k;--i)
#define scan(a,n) rep(i,0,n)cin>>a[i]
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define error freopen("error.txt","w",stderr)
#define ff first
#define ss second
 
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <ll,ll> pll;
 
const int N = 1e6+6;
const int M = 5000;
const int LIM = 1e3;
const int SUM = 5000;
const int ALPHA = 26;
const int EDGE = 2;
const int inf = INT_MAX;
const int mod = 1e9+7;

vector<int> primes;
ll nI[N],fI[N],fact[N],dp[LIM][EDGE][SUM];
string s;
int len;

ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
ll gcd(ll a,ll b){while(b){ll t=a;a=b;b=t%b;}return a;}     
ll lcm(ll a,ll b){return (max(a,b)/gcd(a,b))*min(a,b);}
ll power(ll a,ll b){ll r=1;while(b){if(b&1)r*=a;a=a*a;b>>=1;}return r;}
bool isPrime(ll n){if(n<=1)return 0;if(n<=3)return 1;if(n%2==0||n%3==0)return 0;for(ll i=5;i*i<=n;i+=6)if(n%i==0||n%(i+2)==0)return 0;return 1;}
void find_primes(ll n=M){ll limit=floor(sqrt(n))+1;vector<int> test;test.pb(2),primes.pb(2);for(ll i=3;i<limit;i+=2)if(isPrime(i))test.pb(i),primes.pb(i);ll lo=limit,hi=2*limit;bool p[limit];while(lo<n){if(hi>n)hi=n;memset(p,true,sizeof(p));for(int i=0;i<test.size();++i){ll mn=(lo/test[i])*test[i];if(mn<lo)mn+=test[i];for(ll j=mn;j<hi;j+=test[i])p[j-lo]=0;}rep(i,0,limit)if(p[i] && i+lo<hi)primes.pb(i+lo);lo+=limit,hi+=limit;}}
ll modmult(ll a,ll b){ll r=0;a%=mod;while(b){if(b&1)r=(r+a)%mod;a=(a<<1)%mod;b>>=1;}return r;}
ll modexpo(ll a,ll b){ll r=1;a%=mod;while(b){if(b&1)r=(r*a)%mod;a=(a*a)%mod;b>>=1;}return r;}
ll nCr(ll n,ll r){ll res=1;if(r>n>>1)r=n-r;rep(i,0,r){res=(res*(n-i))%mod;res=(res*modexpo(i+1,mod-2))%mod;}return res;}
void binomial_pre(){nI[0]=nI[1]=fI[0]=fI[1]=fact[0]=1;rep(i,2,N)nI[i]=nI[mod%i]*(mod-mod/i)%mod;rep(i,2,N)fI[i]=(nI[i]*fI[i-1])%mod;rep(i,1,N)fact[i]=(fact[i-1]*i)%mod;}
ll binomial(ll n,ll r){if(n<r)return 0;return ((fact[n]*fI[r])%mod*fI[n-r])%mod;}

ll work(ll idx,ll edge,ll sum) { //edge - {1,0}
    //cout<<idx<<' '<<edge<<' '<<sum<<endl;
    if(idx==len) {
        if(isPrime(sum))
            return 1;
        return 0;
    }
    ll ans=dp[idx][edge][sum],tot=0,hi,e;
    if(ans!=-1)return ans;
    bool isp=isPrime(idx);
    if(edge)
        hi=s[idx]-'a'+1;
    else
        hi=ALPHA;
    rep(i,0,hi) {
        if(isp) {
            tot=(tot+work(idx+1,(i<hi-1?0:edge),sum+i)%mod)%mod;
        }
        else {
            tot=(tot+work(idx+1,(i<hi-1?0:edge),sum)%mod)%mod;
        }
    }
    dp[idx][edge][sum]=tot;
    return tot;
}

int32_t main() {
    io;
    // input; output;
    find_primes();
    int t;
    cin>>t;
    while(t--) {
        cin>>s;
        len=s.size();
        memset(dp,-1,sizeof(dp));
        cout<<work(0,1,0)%mod<<endl;
    }   
    return 0;
} 
 
2 Likes

Please tell the test case where the code is failing:
https://www.codechef.com/viewsolution/34851175

Your code is failing the very first test case.
The smallest example would be
abcde
Correct Output: 5387
Your Output: 5382