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;
}
Code for Fun 