Skip to main content

Posts

Forming Quiz Teams

                        Forming Quiz Teams                                                       dp + bitmasking Problem Link   #include <iostream> #include <cstdio> #include <math.h> #include <cstring> #define sf(a) scanf("%d", &a) #define REP(i, n) for(int i = 0; i < n; i++) using namespace std; int n, posx, posy; char name[21]; double dist[17][17]; double dp[1 << 16]; int xy[17][2]; double solve(int bits) {     if(dp[bits] != -1)         return dp[bits];     if(bits == (1 << n) - 1)         return 0;     double ans = 1 << 30; // random big number     for(int i = 0; i < n; i++)   ...

Jogging Trails

                                      Jogging Trails                                                        bitwise DP  Problem Link #include <iostream> #include <cstring> #include <climits> #include <cstdio> #define INF INT_MAX #define sf(a) scanf("%d", &a) #define set(b, pos) ( b | (1 << pos) ) #define off(b, pos) ( b & ~( 1 << pos) ) #define test(b, pos) (b & (1 << pos) ) using namespace std; int v, e, st, en, wt, weight, bits; int graph[15][15]; int deg[15]; //stores degree of a node int memo[1 << 15]; int solve(int bits) {     if(memo[bits] >= 0)         return memo[bits];     int ans ...

Twenty Questions

                                 Twenty Questions                                                  DP + bitmasking Problem Link #include <iostream> #include <cstring> #include <string> #include <algorithm> using namespace std; int F[128]; //feature set int dp[1 << 11][1 << 11]; //set of question and answer //denotes bitmask of question and answer int n, m; int solve(int Q, int A) {     if(dp[Q][A] != -1)         return dp[Q][A];     int nObjects = 0; //number of objects remaining after asking Q     for(int i = 0; i < n; i++)     {         if((F[i] & Q) == A)            ...

Pebble Solitaire

                                  Pebble Solitaire                                                 DP + bitmasking Problem Link #include <stdio.h> #include <string.h> #define min(a,b) a > b ? b: a void on( int &mask ,int pos){      mask |= ( 1 << pos) ; } void  off(int &mask,int pos){     mask = mask & ~( 1 << pos) ; } bool check( int mask , int pos ){      return bool( mask & ( 1 << pos) ) ; } int dp[ 1<<12 + 5 ] ; int solve( int mask) {     int &ret = dp[mask];     if( ret != -1 ) return ret;     ret = __builtin_popcount(mask);     for( int pos = 0 ; pos < 12 ; pos ++ )   ...

BORW - Black or White

Problem Link #include <iostream> #include <cstring> using namespace std; typedef long int li; const int size = 201; int n; li arr[size]; int dp[size][size][size]; int main() {     while(true)     {         cin >> n;         if(n == -1)             break;         for(int i = 1; i <= n; i++)             cin >> arr[i];         memset(dp, 0, sizeof(dp));         for(int i = 1; i <= n; i++)         {             for(int lb = i + 1; lb <= n + 1; lb++)             {                 for(int lw = i + 1; lw <= n + 1; lw++)                 {    ...

BADXOR

BADXOR - Bad XOR #include <iostream> #include <cstring> #define REP(i, n) for(int i = 0; i < n; i++) #define REP1(i, n) for(int i = 1; i <= n; i++) using namespace std; typedef long long int ll; const int maxLimit = 100000007; ll dp[1005][1024]; //dp[i][j] = number of ways of making value j with first i elements int main() {     int t, a, b;     int arr1[1001];     bool arr2[1025];     cin >> t;     REP1(k, t)     {         memset(dp, 0, sizeof(dp));         memset(arr2, false, sizeof(arr2));         cin >> a >> b;         REP(i, a)         {             cin >> arr1[i];         }         REP(i, b)         {     ...

ANARC05H

ANARC05H - Chop Ahoy! Revisited! #include <iostream> #include <stdio.h> #include <cstring> using namespace std; char str[26]; int len, sum; int solve(int pos, int prevSum) {     if(pos == len)         return 1;     int c = 0;     for(int i = pos, sum = 0; i < len; i++)     {         sum += str[i] - '0';         if(sum >= prevSum)         {             c += solve(i + 1, sum);         }     }     return c; } int main() {     int k = 1;     while(true)     {         scanf("%s", str);         if(!strcmp(str, "bye"))             break;         len = strlen(str);   ...