DP Recipe

Changing Parameter

Make the value of DP a new parameter and make one of the existing parameters the value of DP

Problem: Brand New Problem
Discussion: The official editorial describes the technique very well. Go through the official editorial here
For Implementation see this.

TLE Solution

/*
 * DATE : 2017-05-30
 * Algo : dp
*/
#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define FOR(I,A,B)              for(long long I = (A); I < (B) ; ++ I)
#define REP(i,n)                for( long long i=0 ; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define F                       first
#define S                       second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define in(x)                   input(x)
#define in2(x,y)                input(x), input(y)
#define in3(x,y,z)              input(x), input(y),input(z)
#define ins(x)                  scanf("%s",x)
#define ind(x)                  scanf("%lf",&x)
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define IO                      ios_base::sync_with_stdio(0);cin.tie(0)
#define READ                    freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE                   freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)

template<class T > void input(T &x){
    char c = getchar();x = 0;
    for(;(c<48 || c>57);c = getchar());
    for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}
}
inline long long bigmod(long long p,long long e,long long M){
    long long ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/***************************** END OF TEMPLATE *******************************/

const int N = 6e5+5;
char str[N];
int n,m;
int id = 0;
map<string,int> Map;
int getId(string s)
{
    if(Map.count(s)) return Map[s];
    return Map[s] = id++;
}
vector<int> num;
vector<int> v[11];

int dp[2][1<<15];

int pre[1<<15][15];
int calc(int idx)
{
    memset(dp,63,sizeof dp);
    dp[0][(1<<n)-1]=0;
    int nv= 0;
    for(int i=v[idx].size()-1;i>=0;i--){
        nv = nv ^1;
        int now = v[idx][i];
        for(int mask=0;mask < 1<<n; mask ++ ){
            dp[nv][mask] = dp[nv^1][mask];
            if(now < n && (mask & (1<< now)) == 0 ) {
                int cnt = pre[mask][now];
                dp[nv][mask] = min(dp[nv][mask], cnt + dp[nv^1][mask | (1<<now)]);
            }
        }
        //for(int j=0 ;j < 1<<n; j++) printf("dp[%d][%d] = %d\n",i,j,dp[nv][j]);
    }
    return dp[nv][0];
}
int main()
{

    in(n);
    for(int i=0;i<1<<n;i++){
        int cnt=0;
        for(int j=n-1;j>=0;j--){
            pre[i][j] = cnt;
            if(i&(1<<j)) cnt++;
        }
    }
    for(int i=0;i<n;i++){
        scanf("%s",str);
        num.push_back(getId(str));
    }
    in(m);
    for(int i=0;i<m;i++){
        int k;
        in(k);
        for(int j=0;j<k;j++){
            scanf("%s",str);
            v[i].push_back(getId(str));
        }
    }

    int sum = 1<<20;
    int id = -1;
    for(int i=0;i<m;i++){
        int v = calc(i);
        if(v < sum ) {
            sum = v;
            id = i;
        }
    }
    if(id==-1) printf("Brand new problem!\n");
    else {
        cout << id + 1<<endl;
        int p = n*(n-1)/2 - sum + 1;
        printf("[:");
        REP(i,p) printf("|");
        printf(":]\n");
    }
    return 0;
}

Accepted Solution

/*
 * DATE : 2017-05-30
 * Algo : dp
*/
#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define FOR(I,A,B)              for(long long I = (A); I < (B) ; ++ I)
#define REP(i,n)                for( long long i=0 ; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define F                       first
#define S                       second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define in(x)                   input(x)
#define in2(x,y)                input(x), input(y)
#define in3(x,y,z)              input(x), input(y),input(z)
#define ins(x)                  scanf("%s",x)
#define ind(x)                  scanf("%lf",&x)
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))
#define IO                      ios_base::sync_with_stdio(0);cin.tie(0)
#define READ                    freopen("/Users/matrixcode/Desktop/in.txt","r",stdin)
#define WRITE                   freopen("/Users/matrixcode/Desktop/out.txt","w",stdout)

template<class T > void input(T &x){
    char c = getchar();x = 0;
    for(;(c<48 || c>57);c = getchar());
    for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}
}
inline long long bigmod(long long p,long long e,long long M){
    long long ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/***************************** END OF TEMPLATE *******************************/

const int N = 6e5+5;
char str[N];
int n,m;
int id = 0;
map<string,int> Map;
int getId(string s)
{
    if(Map.count(s)) return Map[s];
    return Map[s] = id++;
}
vector<int> num;
vector<int> v[11];

int pre[1<<15][15];
int Next[N][15];

int last[15];
int dp[1<<15][225];
int calc(int id)
{
    for(int i=0;i<n;i++) last[i]=1<<20;
    for(int i=int(v[id].size())-1;i>=0;i--){
        if(v[id][i]<n) last[v[id][i]] = i;
        for(int j=0;j<n;j++) Next[i][j] = last[j];
    }
    for(int i= 0;i <= n*(n-1)/2; i++ ) dp[0][i] = 1<<20;
    dp[0][0]=0;
    for(int i=1;i<1<<n;i++) {
        for(int j=0;j<=n*(n-1)/2;j++) {
            dp[i][j] = 1<<20;
            for(int k = 0;k < n ; k ++ ) {
                if(i&1<<k){
                    int added = pre[i][k];
                    int inv = j-added;
                    if(inv < 0) continue;
                    int pos = dp[i^(1<<k)][inv];
                    if(pos >= v[id].size()) continue;
                    int t = Next[pos][k];

                    dp[i][j] = min(dp[i][j], t+1);
                }
            }
        }
        //for(int j=0;j<=n*(n-1)/2;j++) printf("dp[%d][%d]= %d\n",i,j,dp[i][j]);
    }
    for(int i=0;i<=n*(n-1)/2;i++) {
        if(dp[(1<<n)-1][i] <= v[id].size()) return i;
    }
    return 1<<20;
}
int main()
{

    in(n);
    for(int i=0;i<1<<n;i++){
        int cnt=0;
        for(int j=n-1;j>=0;j--){
            pre[i][j] = cnt;
            if(i&(1<<j)) cnt++;
        }
    }
    for(int i=0;i<n;i++){
        scanf("%s",str);
        num.push_back(getId(str));
    }
    in(m);
    for(int i=0;i<m;i++){
        int k;
        in(k);
        for(int j=0;j<k;j++){
            scanf("%s",str);
            v[i].push_back(getId(str));
        }
    }
    int sum = 1<<20;
    int id = -1;
    for(int i=0;i<m;i++){
        int v = calc(i);
        if(v < sum ) {
            sum = v;
            id = i;
        }
    }
    if(id==-1) printf("Brand new problem!\n");
    else {
        cout << id + 1<<endl;
        int p = n*(n-1)/2 - sum + 1;
        printf("[:");
        REP(i,p) printf("|");
        printf(":]\n");
    }
    return 0;
}

Dynamic Programming Problems

Problem 1 : CHEIFEFT
Idea:
From Codechef blog:

Let, dp[i][j] = expected maximal discount that we can obtain if we consider only first ‘i’ items and first ‘j’ discounts.

Consider the following two cases:

1) i-th item is chosen

We apply j-th discount to i-th item and get discount price[i] * discount[j] and turn to situation with (i-1) items and (j-1) discounts. So in this case, expected discount is equal to a[i] * b[j]+dp[i-1][j-1].

The probability of this happening is p = j/i. Since we must choose j items from i, and probability that i’th item will be chosen is equal to j/i.

2) i-th item is not chosen

The answer is dp[i-1][j].

The probability of this happening is 1-p.

I used to use recursive Version (Memoization). So here is my code

See details See https://discuss.codechef.com/questions/4100/chiefett-editorial

Click to See Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n,k;
int a[1005],p[1005];
int CS = 1;
int vis[N][N];
double dp[N][N];

double solve(int i,int j)
{
    if(j==0) return 0;
    if(i==0)return -1e8;
    if(vis[i][j] == CS) return dp[i][j];
    double res = j*1./i * (a[i] * p[j] * .01 + solve(i-1,j-1));
    if(i>=j) res += max((double)0,(1-j*1./i) * solve(i-1,j));
    vis[i][j] = CS;
    return dp[i][j] = res;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d %d",&n,&k);
        for(int i = 1; i <= n; i ++ ) scanf("%d",&a[i]);
        for(int i = 1; i <= k ; i ++ ) scanf("%d",&p[i]);
        sort(a+1,a+n+1);
        sort(p+1,p+k+1);
        printf("%.3lf\n",solve(n,k));
        CS ++;
    }
}

---

Problem 2 : LEMOVIE
Idea : DP + Combinatorics.
Solution : lemovie-editorial

Uva 11400 – Lighting System Design

Category : DP

Solution:
* First we need to sort the categories by voltage rating. Then we can apply dp.

Claim:

A consecutive sequence of category of light bulbs are replaced by a category. So the entire category can be fragmented in some sections and this section are illuminated by the last category on the section.

So, If we have 4 category and we suppose divide them into sections. Then Possible arrangement are
1. [1,1] [2,2] [3,3] [4,4]
2. [1,1] [2,2] [3,4]
3. [1,2] [3,3] [4,4]
4. [1,2] [3,4]
5. [1,3] [4,4]
6. [1,4]
…..

We denote a section by [leftmostIndex – rightMostIndex]

Proof :

Now Lets see a possible solution that does not involve continuous segment.

Now


xi = # of bulbs of i category,
ci= cost of voltage source of i category
pi = cost per bulb of i category


From the picture
The bulbs are divided into two sections.
{1 and 3}, and {2 and 4}
Total Cost = c3 + p3*(x1+x3) + c4 + p4 * (x2+x4) = c3 + c4 + x1 * p3 + x2 * p4 + x3 * p3 + x4 * p4; —– (1)

I need to show that there is an optimal solution using continuous sections. As we always need to use the last category.
So Can we do that ?

We have two case:

1. p3 <= p4 :

So we can replace x2 * p4 to x2 * p3 this gives <= Total Cost , and we get 2 sections [1-3] and [4-4]

2. p3 > p4

We replace all p3 in equation (1) with p4 hence we get a cost = c4 + p4 * (x1+x2+x3+x4) which is smaller than the total Cost
Hence we have proved.

The rest is implementation.
this defines a 2D state space (the current category and when you bought lamps last time).

My code:

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

const int N = 1005;
struct cat{
    int volt,cost,lcost,amo;
    bool operator<(const cat &p) const {
        return volt < p.volt;
    }
}p[N];
int n;
int cs = 1;
long long dp[N][N];
int VIS[N][N];
int csum[N];

long long F(int ind,int prv)
{
    if(ind == n) return 0;
    if(prv >= 0 && VIS[ind][prv] == cs) return dp[ind][prv];
    long long res = (ind== n-1 ? 1e9 : F(ind+1,prv));
    long long res2 = p[ind].cost + p[ind].lcost * (csum[ind] - (prv>=0 ? csum[prv]: 0)) + F(ind+1,ind);
    VIS[ind][prv] = cs;
    return dp[ind][prv] = min(res,res2);
    
}
int main()
{
    
    while(scanf("%d",&n)==1 && n ) {
        for(int i = 0; i < n; i ++ ) {
            scanf("%d %d %d %d",&p[i].volt, &p[i].cost ,& p[i].lcost, &p[i].amo);
        }
        sort(p,p+n);
        csum[0] = p[0].amo;
        for(int i = 1;i <n;i ++) csum[i] = csum[i-1] + p[i].amo;
        
        printf("%lld\n",F(0,-1));
        cs++;
    }
}

Digit DP HDU – 4352

Link : 4352

Solution:

This is a digit dp problem,The only problem is how to store lis information and use it to calculate same result more than twice.
Now LIS is a well known topic. There is a n log(n) solution for LIS. The technique used to find LIS, is needed here . Compactly store info about LIS.

Now Let’s see, we are given a sequence [2,5,3,4], We can see LIS = 3 [2,3,4]
How do we compute this result ?

vector<int>I;
for(int i = 0 ; i < ar.size(); i ++ )
// find a position where I can put ar[i].Let it is Pos , such that I[Pos+1] >= ar[i]
if(Pos>=I.size()) {
I.push_back(a[i]);
}else I[pos] = ar[i];
}
LIS = I.size();

For more detail ,please see the link : LIS

How it will look,
After entering 2, I = {2}
After entering 5, I = {2,5}
After entering 5, I = {2,3} // Note here we have replaced 5 with 3
After entering 4, I = {2,3,4}
So, LIS = 3,

The same think is needed ,but difference is,We need to store them using bit mask.

Let S is Bitmask represent LIS ;
Now lets see how to co-operate S with I giving the same result at the end

After entering 2, I = {2} , S = 000010
After entering 5, I = {2,5}, S = 100010
After entering 5, I = {2,3}, S = 000110, We make the first bit which is 1 to zero greater than the input value
After entering 4, I = {2,3,4},S= 001110,
LIS = Number of set bits is S ( 3)

using this modification we can code digit dp easily

/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

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

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < (n) ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N = 1001;

Long dp[20][1<<10][11];
int ar[20];
int nxt[1<<10][10];

Long F(int ind , int Mask, int k, bool flag)
{
      if(ind < 0 ) {
            if(__builtin_popcount(Mask) == k) return 1;
            return 0;
      }
      if(!flag && dp[ind][Mask][k] !=-1) return dp[ind][Mask][k];
      
      Long res = 0, Lim = flag ? ar[ind] : 9;
      for(int i = 0; i <= Lim ; i ++ ) {
            res += F(ind-1, nxt[Mask][i] , k , flag && i == Lim) ;
      }
      if(flag) return res;
      return dp[ind][Mask][k]  = res;
      
}



Long solve(Long a,int k)
{
      int ind = 0;
      for(ind = 0; a; ind ++ , a/=10) ar[ind] = a%10;
      return F(ind-1, 0,k,true);
}

int foo(int Mask,int digit)
{
      if(Mask == 0 && digit == 0) return 0;
      for(int i= digit ; i < 10 ;i ++ ) {
            if( Mask & (1<<i)){
                  Mask ^= 1<<i;
                  Mask ^= 1<<digit;
                  return Mask;
            }
      }
      return Mask ^= 1<<digit;
}
void work()
{
      for(int i = 0; i < 1<<10; i++ )
      {
            for(int j = 0;j < 10; j ++) {
                  nxt[i][j] = foo(i,j);
            }
      }
}

int main()
{
      ms(dp,-1);
      work();
      Long L,R;
      int k;
      Di(t);
      int cs = 0 ;
      while(t--) {
            
            Sii(L,R);
            Si(k);
            printf("Case #%d: %lld\n", ++cs, solve(R,k)  - solve(L-1,k));
      }
      
      
      return 0;
}

Uva 10934 – Dropping water balloons

Category : DP
Discussion:
This problem is similar to another problems unless its constraints are high (2^63-1).
If the limit of n was small , we could do dynamic programming to find the answer. Let’s see what it looks like.

// Here f(k,L,R) -> the minimum number of moves needed to ensure the required height in range[L,R] having k balloons left.

int f(int k,int L,int R)
{
     
      if(L>=R)return 0;
      if(k==1)return R-L+1;
      if(dp[k][L][R] !=-1) return dp[k][L][R];
      int res = INF;
      for(int i = L; i<R; i++) {
            res = min(res, 1 + max(f(k-1 , L,i-1) , f(k,i+1, R)));
      }

      return dp[k][L][R] =res;
}

Now think other side.

Let’s assume, for a fixed k, we know that, for n = 100, we need 10 moves. now can we claim that for n= 1 to 99, the answer <=10
That is for a fixed k ,the height we can assure is monotonous increasing function of moves number. So if we determine, For a fixed k and what is the maximum height we can assure using m moves. Then iterate through the moves.

dp(i,j) The maximum height possible to assure if I have i ballons left and j moves are left

Base case :
if(j==1) return 1; // If I have 1 move left, the maximum possible height to ensure is 1
if(i==1)return j; // Only 1 balloon left, so starting from 1,2,… to j th height we can experiment, as we have j moves.

Transition:

dp(i,j) = dp(i-1,j-1) + 1 + dp(i,j-1); I will choose The height H = dp(i-1,j-1)+ 1, drop a ballon from this height.

Let’s say, The balloons minimum cap = k;
if( k > H ) I need to do the experiment again. But I have 1 move low, This result correspond to dp(i,j-1)

See code:

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

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/

const int N = 101;

typedef unsigned long long u;

u dp[N][64]; // dp(i,j) The maximum height possible to assure if I have i ballons left and j moves are left
bool vis[N][N];
u f(int i,int j)
{
      if(j==1) return 1;
      if(i==1)return j;
      if(vis[i][j]) return dp[i][j];
      else dp[i][j] = 1 + f(i-1, j-1) + f(i,j-1);
      vis[i][j]= 1;
      return dp[i][j];
}


int main()
{
      
  
      u N;
      int k;
      while(scanf("%d %llu",&k,&N)==2) {
            if(!k)break;
            int ans= -1;
            bool flag = 0;
            for(int i = 1; i<= 63; i ++ ) {
                  if(f(k,i) >= N) {
                        flag = 1;
                        ans = i;
                        break;
                  }
            }
            if(flag) printf("%d\n",ans);
            else printf("More than 63 trials needed.\n");
      }
      return 0;
}

DP with profile

Problem Link : Link
Category: DP + Profile
Here Profile consist of two rows, Denote them Mask1,Mask2, current index,
DP states are F(Mask1, Mask2,int index)
In each stage we select such bit string that, this ensures Mask1 to be set all 1

//
//  main.cpp
//  1092 - Lighted Panels
//
//  Created by Repon Macbook on 12/11/15.
//  Copyright © 2015 MAC. All rights reserved.
/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

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

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N = 10;
char g[N][N];
int ar[N];
int r,c;
int dp[1<<8][1<<8][10];
int bits[1<<8];
vector<int> G[1<<8];
int oo[1<<8];
bool solve;

int F(int Mask1,int Mask2, int ind)
{
      if(ind == r) {
            if(Mask1== (1<<c)-1) {
                  solve = 1;
                  return 0;
            }
            return 1e8;
      }
      if(dp[Mask1][Mask2][ind] !=-1) return dp[Mask1][Mask2][ind];
      int res = 1e8;
      for(int j= 0; j < G[Mask1].Sz; j ++ ){
            int k = G[Mask1][j];// We store all the Mask that can Make Mask1 to set all 1,
            res = min(res , bits[k] + F(Mask2^oo[k] ,ar[ind+1] ^oo[k] , ind+1));
      }
      return dp[Mask1][Mask2][ind] = res;
      
}


int main()
{
      
      Di(t);
      int cs = 0;
      while(t--) {
            Sii(r,c);
            forn(i,r) scanf("%s",g[i]);
            forn(i,r) {
                  ar[i] = 0;
                  forn(j,c) if(g[i][j]=='*') ar[i] |= (1<<j);
            }
            forn(i,1<<c) {
                  forn(j,c) if(i&1<<j) bits[i] ++;
                  int prv = 0;
                  forn(j,c)if(i&1<<j){
                        prv ^=(1<<j);
                        if(j+1 < c )prv ^=(1<<(j+1));
                        if(j-1 >=0 ) prv ^= (1<<(j-1));
                  }
                  int M =( (1<<c)-1)  ^ prv;
                  G[M].pb(i);
                  oo[i] = prv;
                  
            }
            ms(dp,-1);
            int res = 1e8;
            solve=0;
            forn(i,1<<c) {
                  res = min(res , F(i,ar[0],0));
            }
            
            
            if(solve) {
                  printf("Case %d: %d\n",++cs, res );
            }else printf("Case %d: impossible\n",++cs);
            forn(i,1<<c) G[i].clear();
            ms(bits,0);
      }
      return 0;
}

Bitmask : Iterating Over a subset

Intended Problem : DP
Category: Bitmask DP
Discussion:

Now Let’s say, We have n elements in a set. How many subsets of this set?
Exactly 2^n. How can we find all those subset ? One way is to use recursion, another is bit mask
We take a n bit binary number to represent a subset of the set. For each element if the corresponding bit of the number is 1, then it is included , and vice-versa.
Now take n = 4, total = 2^n = 16 subset.
S = {3,5,1,6}
1011 Means -> {3,1,6}

code for following ;

for(int i = 0; i < 1<<n; i++ ) {
	// i contains the mask of set S
	for(int j = 0; j < n; j ++) {
		if(i & 1<<j) {
			// Jth element in this subset
		}
	}
}

Easy ? Right.
Now If I ask, Iterate through the subsets of 1011, {3,1,6} which has 2^3 possible subset
possible subsets are {{},{3},{1},{6},{3,1},{3,6},{3,1,6}}

One way to do this :

// Lets say the mask = x;

for(int i = x; ; i = (i-1)&x)
{
	// i contains the mask of one of the subset of x

	// Main Purpose
	if(i==0) break;
}
//This little code

Here is the solution for intended problem :

/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

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

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N = 14;
int a[N][N];
int F[1<<N];
int dp[1<<N];
int p2[(1<<N)+5];
int ar[15];
int main()
{
      forn(i,14) p2[1<<i] = i;
      Di(t);
      int cs= 0;
      while(t--) {
            Di(n);
            forn(i,n)forn(j,n){
                  Si(a[i][j]);
            }
            
            forn(i,1<<n){
                  int Sum  = 0, cnt =0;
                  for(int j=i ; j ; j -=j&-j) {
                        ar[cnt++]= p2[j&-j];
                  }
                  for(int j=0; j <cnt ; j++ ) for(int k = 0; k < cnt ; k ++ ) Sum += a[ar[j]][ar[k]];
                  F[i] = Sum;
            }
            ms(dp,63);
            dp[0] = 0;
            forn(i,1<<n){
                  for(int j = i ; ; j = (j-1) & i) {
                        dp[i]= min(dp[i], F[j] + dp[i^j] );
                        if(j == 0) break;
                
                  }
            }
            printf("Case %d: %d\n", ++cs, dp[(1<<n) - 1]);
      }
      return 0;
}

LOJ 1110 – An Easy LCS

Category : DP
Link : Problem
Discussion:
Easy DP,
Here we keep dp[i][j]-> the lexicographic smallest LCS of A[1…i] & B[1….j]
The Transition is easily understandable

/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

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

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N = 104;
string A,B;

string dp[N][N];
char a[N], b[N];
int main()
{
      Di(t);
      int cs = 0;
      while(t--) {
            scanf("%s %s",a+1, b+1);
            int n = strlen(a+1) , m = strlen(b+1);
            for(int i = 1; i <= n; i ++ ) {
                  for(int j = 1; j<= m ;j ++) {
                        dp[i][j]= dp[i-1][j];
                        if(dp[i][j-1].length() > dp[i][j].length()) dp[i][j] = dp[i][j-1];
                        else if(dp[i][j-1].length() == dp[i][j].length() && dp[i][j-1] < dp[i][j] ) dp[i][j] = dp[i][j-1];
                        if(a[i] == b[j]) {
                              if(dp[i-1][j-1].length() + 1 > dp[i][j].length() ) dp[i][j] = dp[i-1][j-1] + a[i];
                              else if(dp[i-1][j-1].length() + 1 == dp[i][j].length() && dp[i-1][j-1] + a[i]  < dp[i][j] ) dp[i][j] = dp[i-1][j-1] + a[i];
                        }
                  }
            }
            if(dp[n][m] =="") printf("Case %d: :(\n",++cs);
            else printf("Case %d: %s\n",++cs, dp[n][m].c_str());
            
      }
      
      return 0;
}

LOJ 1073 – DNA Sequence

Category : BitMask DP, String Matching
Problem Info: You are given a list of strings over the alphabet A (for adenine), C (cytosine), G (guanine), and T (thymine), and your task is to find the shortest string (which is typically not listed) that contains all given strings as substrings. If there are several such strings of shortest length, find the smallest in alphabetical/lexicographical order.

Discussion:
This is an instance of a classic problem known as the “Shortest Common
Substring”. It can be solved by relating it to the Traveling Salesman
Problem. First remove the strings that are entirely covered by other string. Then process dp with bit mask. And Matching
To find the lexicographic smallest string, dfs over all the possible string of minimum length

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

/*------- Constants---- */
#define LMT				105
#define ll				long long
#define ull				unsigned long long
#define MOD				1000000007
#define MEMSET_INF		63
#define MEM_VAL			1061109567
#define FOR(i,n)			for( int i=0 ; i < n ; i++ )
#define mp(i,j)			make_pair(i,j)
#define lop(i,a,b)		for( int i = (a) ; i < (b) ; i++)
#define pb(a)			push_back((a))
#define gc				getchar_unlocked
#define PI				acos(-1.0)
#define inf				1<<30
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define debug(x)			cout<<#x<<"--> " << x << endl;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
      register int c = gc();
      x = 0;
      int neg = 0;
      for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}
      for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
      if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
      ll ret = 1;
      for(; e > 0; e >>= 1){
            if(e & 1) ret = (ret * p) % M;
            p = (p * p) % M;
      } return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/
int N;
string str[17];

int PF[17][105];

void comp_pf(int pf[], string P , int Psize)
{
      pf[0] = 0;
      for(int i = 1; i < Psize ; i ++) {
            int j = pf[i-1];
            while( j > 0 && P[i] != P[j]) j = pf[j-1];
            if(P[i] == P[j]) ++j;
            pf[i]  = j;
      }
}

int kmpMatcher(string T , int Tsize, string P, int Psize, int pf[])
{
      int k = 0;
      int added = 0;
      for (int i = 0 ; i <Tsize ; i ++ ) {
            while ( k > 0 && T[i]!= P[k]) k = pf[k-1];
            if( P[k] == T[i] ) ++ k;
      }
      
      return  k;
}

int Store[20][20];
int inter(int a,int b)
{
      if(a<0) return str[b].length();
      if(Store[a][b] !=-1) return Store[a][b];
      return Store[a][b] = str[b].length() - kmpMatcher(str[a],str[a].length(), str[b],str[b].length(), PF[b]);
}



int dp[17][1<<16];
int off= 1;
int cal(int id, int mask)
{
      if(mask == 0) {
            return dp[id+1][mask] = 0;
      }
      
      if(dp[id + off][ mask ] !=-1 ) return dp[ id+off ][mask];
      int res = inf;
      for( int i = 0 ; i < N ; i ++) {
            if( mask & (1 << i )) {
                  res = min(res, cal(i, mask ^(1<<i)) + inter(id,i));
            }
            
      }
      
      return  dp[id + off ][mask] = res;
      
}

string best;
void Trc  ( int id , int mask ,string cur )
{
      if(cur > best) return;
      if(mask==0){
            if(cur < best) best= cur;
            return;
      }
      int now = dp[id+off][mask];
      for(int i = 0;i < N; i ++ ) {
            if(mask & 1<<i){
                  int need = inter(id,i);
                  int index = str[i].length() - need;
                  if(dp[i+off][mask^1<<i] + need == now ) {
                        
                        Trc(i, mask ^1<<i , cur + str[i].substr(index,need));
                  }
            }
      }
      
      
}


int main()
{
      
      
      int tc , cs = 0 ;
      sc(tc);
      
      while (tc --) {
            
            sc(N);
            string s2[20];
            for(int i = 0 ; i< N ; i ++ ) {
                  cin >> s2[i];
            }
            bool vis[20];
            ms(vis,0);
            for(int i = 0;i <N; i++ ) {
                  if(vis[i]) continue;
                  for(int j = 0;j < N; j ++)  {
                        
                        if(i!=j && s2[i].find(s2[j]) != string::npos) {
                              vis[j] = 1;
                        }
                  }
            }
            int cnt = 0;
            for(int i = 0;i  < N; i ++) {
                  if(vis[i]==0){
                        str[cnt ++] = s2[i];
                  }
            }
            N=  cnt;
            for(int i = 0; i < N ; i ++ ) {
                  comp_pf(PF[i],str[i],str[i].length());
            }
            ms(dp, -1);
            ms(Store,-1);
            cal( - 1, (1<<N) - 1 ) ;
            
            printf("Case %d: ",++cs);
            best="Z";
            Trc( -1  , (1 << N) - 1 , "");
            if(N>1)cout << best<<endl;
            else cout << str[0] << endl;
      }
      return 0;
}

HDU – 4389

Category : Digit DP
Code:

//
//  main.cpp
//  HDU - 4389
//
//  Created by Repon Macbook on 12/9/15.
//  Copyright © 2015 Repon Macbook. All rights reserved.
//

/*
 
 *************************
 Id  : Matrix.code
 Task:
 Date:
 
 **************************
 
 */

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

/*------- Constants---- */

#define Long                    long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define forn(i,n)               for( int i=0 ; i < (n) ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define INF                     1<<29
#define EPS                     1e-9
#define Fr                      first
#define Sc                      second
#define Sz                      size()
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(n)                   int n;si(n)
#define Dii(a,b)                int a,b;si(a);si(b)
#define Diii(a,b,c)             int a,b,c;si(a);si(b);si(c)
#define Si(n)                   si(n)
#define Sii(a,b)                si(a);si(b)
#define Siii(a,b,c)             si(a);si(b);si(c)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
      if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}

/*************************** END OF TEMPLATE ****************************/
const int N = 1001;


int dp[11][82][82][82];
int ar[11];

Long F(int ind, int R , int Rem,  bool flag, int Sum)
{
      if(ind < 0 ) {
            if(Sum == R && Rem == 0) return 1;
            return 0;
      }
      if(!flag && dp[ind][R][Rem][Sum] !=-1 ) return dp[ind][R][Rem][Sum];
      
      int res=0, Lim = flag ? ar[ind] : 9;
      for(int i = 0;i <= Lim ; i ++ ) {
            res += F(ind-1,R,(Rem*10+i) % R, flag &(i==Lim) , Sum + i );
      }
      return flag ? res : dp[ind][R][Rem][Sum] = res;
}
Long solve(Long a)
{
      if(a<1) return 0;
      int ind = 0;
      for(ind = 0; a ; ind ++ , a/=10  ) ar[ind]  = a%10;
      Long ans = 0;
      for(int i= 1; i < 82; i ++ ) {
            ans += F(ind-1, i, 0,true, 0);
      }
      return ans;
}
int main()
{
      Di(t);
      ms(dp,-1);
      int cs = 0;
      while(t--) {
            Long a,b;
            cin >> a>>b;
            printf("Case %d: %lld\n" , ++cs, solve(b) - solve(a-1));
      }
      return 0;
}