1252 - Twenty Questions

All about problems in Volume 12. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
flashion
New poster
Posts: 17
Joined: Thu Jul 24, 2014 10:29 pm

1252 - Twenty Questions

Post by flashion » Tue Aug 05, 2014 11:47 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1252 - Twenty Questions

Post by brianfry713 » Tue Aug 05, 2014 10:24 pm

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
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1252 - Twenty Questions

Post by brianfry713 » Tue Aug 05, 2014 10:47 pm

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.
Check input and AC output for thousands of problems on uDebug!

flashion
New poster
Posts: 17
Joined: Thu Jul 24, 2014 10:29 pm

Re: 1252 - Twenty Questions

Post by flashion » Tue Aug 05, 2014 11:07 pm

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
New poster
Posts: 17
Joined: Thu Jul 24, 2014 10:29 pm

Re: 1252 - Twenty Questions

Post by flashion » Wed Aug 06, 2014 2:10 pm

TLE :o

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1252 - Twenty Questions

Post by brianfry713 » Wed Aug 06, 2014 10:57 pm

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.
Check input and AC output for thousands of problems on uDebug!

vhua_no_name
New poster
Posts: 8
Joined: Sat Dec 21, 2013 8:48 pm

Re: 1252 - Twenty Questions

Post by vhua_no_name » Thu Mar 26, 2015 5:32 pm

brianfry713 wrote: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
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 1252 - Twenty Questions

Post by jddantes » Mon Feb 22, 2016 6:07 pm

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;
}

Post Reply

Return to “Volume 12 (1200-1299)”