1252 - Twenty Questions

[flashion]

http://uva.onlinejudge.org/index.php?op ... oblem=3693

Hello,

I'm solving this problem and I don't understand one thing. My program for sample input returns:

0
2
5 <-- correct is 4
11
9

My algorithm: I iterate over every bitmask from 1 to (1<<m) and checked if any two objects are the same. Do I do it right? If not, please point me which 4 questions I should ask in this test.
Thanks

[brianfry713]

You can choose the next question after you get the answer to the previous question.

Code: Select all

11 16 
01000101111 
01011000000 
01011111001 
01101101001 
01110010111 
01110100111 
10000001010 
10010001000 
10010110100 
10100010100 
10101010110 
10110100010 
11001010011 
11011001001 
11111000111 
11111011101 
0 0

ask 2 (group where bit 2 = 0)
01000101111 
01011000000 
01011111001 
10000001010 
10010001000 
10010110100 
11001010011 
11011001001 

ask 2 4 (group where bit 2 = 0 and bit 4 = 0)
01000101111 
10000001010 
10010001000 
10010110100 

ask 2 4 3 (group where bit 2 = 0 and bit 4 = 0 and bit 3 = 0)
01000101111 
10000001010 
Now ask 0

ask 2 4 3 (group where bit 2 = 0 and bit 4 = 0 and bit 3 = 1)
10010001000 
10010110100 
Now ask 5

ask 2 4 (group where bit 2 = 0 and bit 4 = 1)
01011000000 
01011111001 
11001010011 
11011001001 
Now ask 0 then 6

ask 2 (group where bit 2 = 1)
01101101001 
01110010111 
01110100111 
10100010100 
10101010110 
10110100010 
11111000111 
11111011101 

ask 2 4 (group where bit 2 = 1 and bit 4 = 0)
01110010111 
01110100111 
10100010100 
10110100010 
Now ask 0 then 5

ask 2 4 (group where bit 2 = 1 and bit 4 = 1)
01101101001 
10101010110 
11111000111 
11111011101 
Now ask 3 then 6

[brianfry713]

I solved it using recursive backtracking with DP memoization (table size 1 << 12 by 1 << 12). At each state, you try all remaining bits. Take the bit that results in the least number of additional questions in the worst case.

[flashion]

Right, I thought it's enough to get unique object id-s (consists selected bits, the same for every object) to get the answer, but now I see we should adjust to results we get meanwhile. Thanks, I'll try to code it tomorrow.

[flashion]

TLE

Code: Select all

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <climits>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>

#define ALL(v) v.begin(), v.end()
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REPD(i, a, b) for(int i = a; i > b; i--)
#define REPLL(i, a, b) for(LL i = a; i < b; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FORLL(i, a, b) for(LL i = a; i <= b; i++)
#define INF 1000000001

#define VIT vector<int>::iterator
#define SIT set<int>::iterator

#define LL long long
#define LD long double

#define PB push_back
#define MP make_pair
#define PII pair<int, int>
#define PLD pair<LD, LD>
#define st first
#define nd second

#define MAXM 12

using namespace std;

int z, n, m;
LL t;
int mask[200];
char s[100];
int mem[1<<MAXM];
int cnt[1<<MAXM];

int count(int asked) {
    int ret = 0;
    while(asked) {
        ret += (asked&1); asked >>= 1;
    }
    return ret;
}

void f(int& asked, vector<int>& v) {
    int ret = (1<<m) - 1;
    if(mem[asked]) {
        asked = mem[asked];
        return;
    }
    if(v.size() <= 1) return;
    REP(i, 0, m) {
        vector<int> z, o;
        if(((1<<i) & asked) == 0) {
            REP(j, 0, v.size()) {
                if((1<<i) & mask[j]) o.PB(v[j]);
                else z.PB(v[j]);
            }
            int a = asked | (1<<i);
            int b = asked | (1<<i);
            f(a, z); f(b, o);
            int r = a|b;
            if(cnt[r] < cnt[ret]) ret = r;
        }
    }
    mem[asked] = asked = ret;
}


int main()
{
    REP(i, 0, 1<<MAXM) {
        cnt[i] = count(i);
    }

    while(~scanf("%d%d", &m, &n)) {
        if(!m && !n) break;
        REP(i, 0, n) {
            int c = 0;
            scanf("%s", s);
            int l = strlen(s);
            REP(i, 0, l) {
                int t = s[i]-'0';
                c += t;
                c <<= 1;
            }
            c >>= 1;
            mask[i] = c;
        }

        REP(i, 0, 1<<m) mem[i] = false;

        vector<int> v;
        REP(i, 0, n) v.PB(i);

        int asked = 0;
        f(asked, v);
        printf("%d\n", cnt[asked]);
    }

    return 0;
}

[brianfry713]

Here is some of my debug output for the second sample input, taken at the start of my recursive function.
My DP array is 1 << 12 by 1 << 12, indexed on asked and asked_values, and returns the number of additional questions needed.
I skip asking questions that don't lead to any new information.
I set the don't care x's in asked_values to 0.

Code: Select all

asked = 000000000000, asked_values = xxxxxxxxxxxx, number of objects = 4
asked = 010000000000, asked_values = x1xxxxxxxxxx, number of objects = 3
asked = 011000000000, asked_values = x10xxxxxxxxx, number of objects = 2
asked = 010100000000, asked_values = x1x0xxxxxxxx, number of objects = 2
asked = 010010000000, asked_values = x1xx0xxxxxxx, number of objects = 2
asked = 010001000000, asked_values = x1xxx1xxxxxx, number of objects = 2
asked = 010000100000, asked_values = x1xxxx0xxxxx, number of objects = 2
asked = 010000010000, asked_values = x1xxxxx0xxxx, number of objects = 2
asked = 010000000100, asked_values = x1xxxxxxx1xx, number of objects = 2
asked = 001000000000, asked_values = xx0xxxxxxxxx, number of objects = 2
asked = 001000000000, asked_values = xx1xxxxxxxxx, number of objects = 2
asked = 000100000000, asked_values = xxx0xxxxxxxx, number of objects = 2
asked = 000100000000, asked_values = xxx1xxxxxxxx, number of objects = 2
asked = 000010000000, asked_values = xxxx0xxxxxxx, number of objects = 2
asked = 000010000000, asked_values = xxxx1xxxxxxx, number of objects = 2
asked = 000001000000, asked_values = xxxxx0xxxxxx, number of objects = 2
asked = 000001000000, asked_values = xxxxx1xxxxxx, number of objects = 2
asked = 000000100000, asked_values = xxxxxx0xxxxx, number of objects = 3
asked = 010000100000, asked_values = x1xxxx0xxxxx, number of objects = 2, dp hit = 1
asked = 001000100000, asked_values = xx0xxx0xxxxx, number of objects = 2
asked = 000100100000, asked_values = xxx1xx0xxxxx, number of objects = 2
asked = 000010100000, asked_values = xxxx1x0xxxxx, number of objects = 2
asked = 000001100000, asked_values = xxxxx00xxxxx, number of objects = 2
asked = 000000110000, asked_values = xxxxxx01xxxx, number of objects = 2
asked = 000000101000, asked_values = xxxxxx0x0xxx, number of objects = 2
asked = 000000100100, asked_values = xxxxxx0xx1xx, number of objects = 2
asked = 000000100010, asked_values = xxxxxx0xxx1x, number of objects = 2
asked = 000000010000, asked_values = xxxxxxx0xxxx, number of objects = 2
asked = 000000010000, asked_values = xxxxxxx1xxxx, number of objects = 2
asked = 000000001000, asked_values = xxxxxxxx0xxx, number of objects = 3
asked = 001000001000, asked_values = xx0xxxxx0xxx, number of objects = 2
asked = 000100001000, asked_values = xxx0xxxx0xxx, number of objects = 2
asked = 000010001000, asked_values = xxxx0xxx0xxx, number of objects = 2
asked = 000001001000, asked_values = xxxxx1xx0xxx, number of objects = 2
asked = 000000101000, asked_values = xxxxxx0x0xxx, number of objects = 2, dp hit = 1
asked = 000000011000, asked_values = xxxxxxx00xxx, number of objects = 2
asked = 000000001100, asked_values = xxxxxxxx01xx, number of objects = 2
asked = 000000000100, asked_values = xxxxxxxxx0xx, number of objects = 2
asked = 000000000100, asked_values = xxxxxxxxx1xx, number of objects = 2
asked = 000000000010, asked_values = xxxxxxxxxx1x, number of objects = 3
asked = 001000000010, asked_values = xx0xxxxxxx1x, number of objects = 2
asked = 000100000010, asked_values = xxx0xxxxxx1x, number of objects = 2
asked = 000010000010, asked_values = xxxx0xxxxx1x, number of objects = 2
asked = 000001000010, asked_values = xxxxx1xxxx1x, number of objects = 2
asked = 000000100010, asked_values = xxxxxx0xxx1x, number of objects = 2, dp hit = 1
asked = 000000010010, asked_values = xxxxxxx0xx1x, number of objects = 2
asked = 000000000110, asked_values = xxxxxxxxx11x, number of objects = 2
2

Try changing your algorithm to match mine.

[vhua_no_name]

I solved it using recursive backtracking with DP memoization (table size 1 << 12 by 1 << 12). At each state, you try all remaining bits. *<<Take the bit that results in the least number of additional questions in the worst case>>*.

hello brianfry713,
please, can u explain why we are considering worst case?
why we are using max() rather than min() in the following algorithm?

//here kth additonal questiontion is asked

DP[asked][asked_values]= min( DP[asked][asked_values], 1+ max( backtrack(asked|(1<<k), asked_values) , backtrack(asked|(1<<k),asked_values|(1<<k)))

backtrack(asked|(1<<k), asked_values|(1<<k)) --> where kth question's group bit value =1.
backtrack(asked|(1<<k), asked_values) --> where kth question's group bit value = 0. [we are not manually clearing kth bit of asked_values to 0, because we will call backtrack(asked =0 , asked_values =0 ) with initial value 0 ]

thanks in advance.

[jddantes]

Getting WA. What did I miss?

Code: Select all

#include <bits/stdc++.h>

using namespace std;

#define INF 1<<28
#define UNVISITED -1
typedef bitset<11> bset;
typedef unsigned long ul;
int N, M;

vector<string> input;
vector<bset> input_bs;

int arr[1<<11][11][1<<11];


// int f(bset bs, int index){

// 	ul ulong = bs.to_ulong();
// 	int bits_set = bs.count();
// 	cout << bs << " : " << index << endl;
// 	cout << ulong << endl;
// 	printf("Ulong is %u\n", ulong);
// 	if(index == M){
// 		if(bits_set != 1){
// 			return INF;
// 		} else {
// 			return 0;
// 		}
// 	}

// 	if(arr[ulong][index] != UNVISITED){
// 		return arr[ulong][index];
// 	}

// 	int ret = INF;

// 	// Take
// 	bset a_bs, b_bs;
// 	for(int i = 0; i<N; i++){
// 		if(bs[i]){
// 			if(input[i][index] == '1'){
// 				a_bs[i] = 1;
// 			} else {
// 				b_bs[i] = 1;
// 			}
// 		}
// 	}

// 	int a_ret = f(a_bs, index+1);
// 	int b_ret = f(b_bs, index+1);
// 	int take_ret = 1 + max(a_ret, b_ret);
// 	ret = min(ret, take_ret);

// 	// Skip
// 	int skip_ret = f(bs, index+1);
// 	ret = min(ret, skip_ret);

// 	return arr[ulong][index] = ret;

// }

void printBS(bset bs){
	for(int i = 0; i<=10; i++) cout << bs[i];
}
void printbsln(bset bs){
	printBS(bs);
	printf("\n");
	// cout << bs << endl;
}

vector<bset> filter(bset bs, int index, bset q_bs){
	vector<bset> dump = input_bs;
	vector<bset> next_dump;

	for(int q = 0; q<index; q++){
		if(q_bs[q]){
			// printf("q is %d\n", q);
			// printf("Dump currently:\n");
			// for(auto d : dump) {
			// 	printbsln(d);
			// }
			// printf("==\n");
			if(bs[q]){
				for(auto d : dump){
					if(d[q] ){						
						next_dump.push_back(d);
					} 
				}
			} else {
				for(auto d: dump){
					if(!d[q]){
						next_dump.push_back(d);
					} 
				}
			}
		
			dump = next_dump;
			next_dump.clear();
		}
	}
	// printf("Dump currently:\n");
	// 		for(auto d : dump) {
	// 			printbsln(d);
	// 		}
	// 		cout << "yada" << endl;
	return dump;
}

int tabs = -1;
void printTabs() { for(int i = 0; i<tabs; i++) printf("\t");}
int f(bset bs, int index, bset q_bs){
	vector<bset> dump = filter(bs, index, q_bs);

	int dmp_sz = dump.size();

	if(!dmp_sz){
		return 0;
	}

	if(dmp_sz == 1){
		return 0;
	}


	if(index == M){
		// printf("Terminal\n");
		// printbsln(bs);
		// printbsln(q_bs);
		// printf("Dump:\n");
		// for(auto d: dump) printbsln(d);

		if(dmp_sz>1){
			return INF;
		} else {
			return 0;
		}
	}

	

	ul bs_ul = bs.to_ulong();
	ul q_ul = q_bs.to_ulong();

	if(arr[bs_ul][index][q_ul] != UNVISITED){
		return arr[bs_ul][index][q_ul];
	}

	int ret = INF;	

	// If take
	bset q_bs_next = q_bs;
	q_bs_next[index] = 1;
	bset bs_a = bs;
	bs_a[index] = 1;
	bset bs_b = bs;
	bs_b[index] = 0;
	int a_ret = f(bs_a, index+1, q_bs_next);
	int b_ret = f(bs_b, index+1, q_bs_next);
	int take_ret = 1 + max(a_ret, b_ret);
	ret = min(ret, take_ret);

	
	// If skip
	int skip_ret = f(bs, index+1, q_bs);
	ret = min(ret, skip_ret);

	return arr[bs_ul][index][q_ul] = ret;
}

int main(){
	while(scanf("%d %d", &M, &N)!=EOF){
		if(!N && !M) return 0;
		input.clear();
		input_bs.clear();
		for(int i = 0; i<N; i++){
			string str;
			cin >> str;
			bset bs;
			input.push_back(str);
			for(int j = 0; j<M; j++){
				if(str[j] == '1'){
					bs[j] = 1;
				}
			}
			input_bs.push_back(bs);
		}

		for(int i = 0; i< 1<<M; i++){
			for(int j = 0; j<M; j++){
				for(int k = 0; k< 1<<M; k++){
					arr[i][j][k] = UNVISITED;
				}
			}
		}





		bset bs, q_bs;
		// bs[0] = 1;
		// q_bs[0] = 1;
		// vector<bset> dump = filter(bs, 1, q_bs);
		// for(auto d : dump) printbsln(d);
		// return 0;

		int ret = f(bs, 0, q_bs);
		printf("%d\n", ret);
	}


	return 0;
}