UVA 1734 : Numbered Card (Bitmask +Digit dp)


UVA 1734: Numbered Card

 ( ACM-ICPC Dhaka Regional 2015 )


Idea:

The problem is asking for total numbers of subsets that can be constructed by using only numbers within 1 to N such that no two numbers contains same digit on their representation . Where, N can be as much as 1e9. 
So, main generalization to this problem is considering the pattern of numbers that can be included in a subset.Let us assume that 1,11,111,111,1111 are same type of numbers. Similarly, 2,22,222,2222...also 12,21,211,122,121 are of same type of numbers. So, it is easy to see that there are total 2^10 type of numbers.So, total size of subset will never be great than 2^10.
So, if we calculate  for each type of numbers how many are there within 1 to N. (This can be done with digit dp) Then, we may proceeds for core idea of problem. 
The idea is that,  we can find total different subsets by DP keeping track of current position out of total 2^10 position and the mask of different digit included so far. So, we may have choices for each type of numbers that we may either do not include it  or we include only one of it on our subset considering that non of digit of that type are already included in mask. 
(Feel Free to mail me if you face any problem)
Source Code:
///============================================================================///
///                                                                            ///
///                            IT'S ME                                         ///
///                         BISHAL GAUTAM                                      ///
///                  CSE,JAHANGIRNAGAR UNIVERSITY,DHAKA                        ///
///               "Follow Excellence..Success will chase U"                    ///
///                                                                            ///
///============================================================================///
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>

///==Scanning====///
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define S3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
#define SL3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)

///==Arr,Vec Functions==///
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define MAX(a) (*max_element(all(a)))
#define MIN(a) (*min_element(all(a)))
#define fv(i,v)  for(int i=0;i<(int)v.size();i++)
#define fr(i,a,n) for(int i=a;i<=n;i++)
#define rf(i,n,a) for(int i=n;i>=a;i--)

///===Some Useful====///
#define OnBit(a) __builtin_popcountll((ll)a)
#define LB(v,k) lower_bound(v.begin(),v.end(),k)
#define _cin ios_base::sync_with_stdio(0),cin.tie(0)
#define dbg(x) cerr<<__LINE__<< ":: "<<#x<<"= "<<x<<endl
#define UNIK(v) sort(all(v)),v.resize( unique(all(v)) -v.begin() );
#define fi(n) for(__typeof(n.begin()) it=n.begin();it!=n.end();it++)
#define IO freopen("A.in","r",stdin),freopen("Out.out","w",stdout)
using namespace std;

///===TypeDefs=====///
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<pii> vii;

///===Number Theory===///
//template< class T > inline T SQR(T a) { return ((a)*(a)); }
//template< class T > inline T gcd(T a,T b) {a=abs(a);b=abs(b); if(!b) return a; return gcd(b,a%b);}
//template< class T > inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/_gcd(a,b))*b;}
//template<typename T> T POW(T b,T p) {T r=1; while(p){if(p&1)r=(r*b);b=(b*b);p>>=1;}return r;}
//template<typename T> T BigMod(T b,T p,T m) {T r=1; while(p){if(p&1)r=(r*b)%m;b=(b*b)%m;p>>=1;}return r;}
//template<typename T> T ModInverse(T n,T m) { return BigMod(n,m-2,m); }
//
/////==GeoMetry=========///
//double DEG(double x) { return (180.0*x)/(PI);}
//double RAD(double x) { return (x*(double)PI)/(180.0);}
//template<typename T> double DIS(T a,T b){ return sqrt((double)( SQR(a.X-b.X)+ SQR(a.Y-b.Y))); }
//template<typename T> T ANGLE(T a,T b){ return atan( double(a.Y-b.Y) / double(a.X-b.X));}
//template<typename T> int isLeft(T a,T b,T c) { return (c.X-a.X)*(b.Y-a.Y)-(b.X-a.X)*(c.Y-a.Y); }
//
/////===IO-Related===///
//template< class T > void prnt(T v) { fv(i,v) {if(!i)cout<<v[i];else cout<<" "<<v[i];} cout<<endl; }
//template< class T > void BIN(T n) { if(!n){nl;return;}BIN(n/2);cout<<(n%2); }
//template<typename T> T in(){ char ch; T n = 0; bool ng = false; while (1) { ch = getchar(); if (ch == '-') { ng = true; ch = getchar(); break;} if (ch>='0' && ch<='9') break; }    while (1) { n = n*10 + (ch - '0'); ch = getchar(); if (ch<'0' || ch>'9')   break;    }  return (ng?-n:n);  }

///====Some-Stuff===///
// atoi( str.c_str() ); // char string to int
/// sprintf(str,"%d",num);// num to char string
///int month[]={-1,31,28,31,30,31,30,31,31,30,31,30,31}; //Not Leap Year
///int dx[]= {1,0,-1,0};int dy[]= {0,1,0,-1}; //4 Direction
///int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 Direction
///int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction

/**************************************************************************************
 * ///////////////////////////////////////////////////////////////////////////////////*
 *************************************************************************************/

///==========CONSTANTS==============///
///  Digit     0123456789*#@%&^$"-  ///
#define MX     500000
#define inf    2000000000
#define md     1000000007LL
#define eps    1e-9
///================================///

int n,ar[1030+5];

int Brute(int msk){
    set<int>St;
    for(int i=0;i<=9;i++){
        if( msk&(1<<i) )St.insert( i );
    }
    int cnt=0;
    for(int i=0;i<=n;i++){
        int ok=1;
        set<int>tp;
        if( i==0 )tp.insert(0);
        int nm=i;
        while(nm){
            tp.insert( nm%10 );
            nm/=10;
        }
        if( tp==St )cnt++;
    }
    return cnt;
}

int ms,ln;
char s[12];
ll dpp[11][2][2][1030];

ll DP(int p,int ch,int z,int msk){
    if( p==ln ) return (msk==ms);
    ll &ret=dpp[p][ch][z][msk];
    if(ret!=-1) return ret;
    ret=0;
    int mx=s[p]-'0';
    if(ch)mx=9;
    for(int i=0;i<=mx;i++){
        int nz=(z||i>0);
        int nmsk=msk;
        if( nz ){
            if( !(ms&(1<<i)) ) continue;
            else nmsk|=(1<<i);
        }
        ret+=DP(p+1,ch||i<mx,nz,nmsk);
    }
    return ret;
}

ll lim,dp[1030][1030];
ll go(int p,int msk){
    if(p==lim+1) return 1LL;
    ll &ret=dp[p][msk];
    if(ret!=-1) return ret;
    ret=go(p+1,msk)%md;
    if( (msk&p)==0 )ret=(ret+ ((ll)ar[p]*go(p+1,msk|p))%md )%md;
    return ret;
}

int main(){
    int tc,cs=1,i,j,k;
    S(tc);
    while(tc--){
        S(n);
        sprintf(s,"%d",n);
        ln=strlen(s);
        lim=(1<<10)-1;
        for(i=2;i<=lim;i++){
            ms=i;
            SET(dpp);
            ar[i]=DP(0,0,0,0);
           //ar[i]=Brute(i);
        }
        SET(dp);
        ll ans=go(2,0);
        printf("Case %d: %lld\n",cs++,(ans-1+md)%md);
    }
    return 0;
}

Comments

  1. Amr MohamedSeptember 9, 2016 at 4:57 PM

    What are the state variables for the dp array?
    Obviously we need a bitmask to prevent taking a digit that is already part of a number in the current set.
    But how can we prevent counting {1,2} & {2,1} as two different sets?

    Thanks

    ReplyDelete
    Replies
    1. Bishal GautamSeptember 10, 2016 at 2:44 AM

      As we already counted total bumbers from 1 to N for each bitmasks
      representing digits on array-ar.
      so, after that, dp array represents position bitmasks array-ar (p) and
      total masks formed by including/non including different mask array-ar (msk).
      So, obviously it prevents counting {1,2} and {2,1} twice,coz, we are including mask
      for 1 at first and then for 2.

      Delete

Post a Comment

Popular posts from this blog

HackerEarth: City and Campers 2 (DSU-UnionFind)

HackerEarth: City and Campers 2 (DSU-UnionFind) ///==================================================/// /// HELLO WORLD !! /// /// IT'S ME /// /// BISHAL GAUTAM /// /// [ bsal.gautam16@gmail.com ] /// ///==================================================/// #include<bits/stdc++.h> # define X first # define Y second # define mpp make_pair # define nl printf("\n") # define SZ ( x ) (int)(x.size()) # define pb ( x ) push_back(x) # define pii pair<int,int> # define pll pair<ll,ll> ///--------------------- # define S ( a ) scanf("%d",&a) # define P ( a ) printf("%d",a) # define SL ( a ) scanf("%lld",&a) # define S2 ( a,b ) scanf("%d%d",&a,&b) # define SL2 ( a,b ) scanf("%lld%lld",&a,&b) ///------------------------------------ # define
Read more

Two Pointers Technique & Binary Search For Beginners

Sample Problem: Electronics Shop ( HackerRank ) (Find me on HackerRank @ Handle:  BishalG  ) Problem Summary: In this problem, you are given two arrays of positive integer numbers of lengths n and m respectively and another positive integer b . Your task is to find out the maximum integer formed by the summation of two integer values taken from different arrays and is less than or equal to b. If there does not exist such summation print -1 . Solution Idea: Since the constraints for n and m are small ( i.e. 1 <= n, m <= 1000 ) , so this problem is very much suitable to test different variants of our solution approaches. Here, we will discuss about 3 different approaches to solve this problem progressively starting from least efficient solution to most efficient one. Approach - 1: Brute-force If we think in brute-force manner, the naive approach to solve this problem will be to try every possible pairing among these two arrays. For this, we can just iterate ove
Read more

Problem : Codeforces Round #406 (Div. 1) B [ Legacy ]( Dijakstra, Segment tree)

You are given graph N (10^5) nodes and starting node (S), You have to find min distance needed to go to all other nodes. Connections among nodes are a little bit different in the form of range type queries, which are: (1) you can open a portal from planet u to planet v with cost z. (2) you can open a portal from planet u to any planet with index in range [l, r] with cost z. (3) you can open a portal from any planet with index in range [l, r] to planet u with cost z. Idea: If we tried to make a adjacency matrix normally by traversing from l to r in (2) and (3) type of connection queries, it will surely time out. So, what we have to do is to think little bit about segmenttree representation of array. This representation allow us to make connection matrix only with LOGN adjacency nodes. So that we may proceed further. Lets build two types of segment-tree nodes , say UP segment tree , which will be used for (2) type of query and DOWN segmenttree which will be used for (3) type of
Read more