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

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

1252 - Twenty Questions

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

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

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

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

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

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

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;
char s;
int mem[1<<MAXM];
int cnt[1<<MAXM];

int count(int asked) {
int ret = 0;
}
return ret;
}

void f(int& asked, vector<int>& v) {
int ret = (1<<m) - 1;
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;
}
}
}

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

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

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

int asked = 0;
}

return 0;
}

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

Re: 1252 - Twenty Questions

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

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?

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 ]

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 1252 - Twenty Questions

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][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 = 1;
// q_bs = 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;
}