11920 - 0 s, 1 s and ? Marks

[Shadek_BUET_07]

Brianfry, can you check it again. It is still getting TLE.

Code: Select all

#pragma comment(linker,"/STACK:16777216")
#pragma  warning ( disable: 4786)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<queue>
#include<sstream>
#include<stack>
#include<list>
#include <bitset>
#include<iomanip>
#include <fstream>
#include<ctime>

using namespace std;

#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

#define MX 1000000

#define forl(i,a,b) for ( i = a; i < b; i++)
#define fore(i,a,b) for ( i = a; i <= b; i++)
#define forrev(i,a,b) for ( i = a; i >= b; i--)
#define pb push_back
typedef long long  LL;
#define in(a,b,c) ((a) <= (b) && (b) <= (c))
#define ms(a,b) memset((a),(b),sizeof(a))

#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ull unsigned long long int
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

string to_string(long long x) { stringstream ss; ss << x; return ss.str(); }
long long to_int(const string &s) { stringstream ss; ss << s; long long x; ss >> x; return x; }


int max_group;
int ans;
char in[1002];
int n;
void max_optimum_group()
{
	int cnt=0;
	int i;
	max_group = 1;
	bool ques = true;
	forl(i,0,n)
	{
		
		if(in[i] == '?')
		{
			ques = true;
			if(cnt > 0)
			{
				max_group = max(max_group,cnt);
			}
		}
		else
		{
			if(i>0 && in[i] == in[i-1])
			{
				cnt++;
			}
			else
			{
				max_group = max(max_group,cnt);
				cnt=1;
			}
		}
	}
	max_group = max(max_group,cnt);
	
}
void doit(int pos, int max_group_size, int curr_size, char prev)
{
	int i,j,k,sz;
	if(pos == n)
	{
		max_group_size = max(max_group_size, curr_size);
		ans = min(ans,max_group_size);
		return;
	}
	if(max_group_size > ans)
		return;
	if(curr_size >= max_group)
		return;
	if(in[pos] != '?')
	{
		if(in[pos] == prev)
		{
			i = pos;
			sz = curr_size;
			while(i<n && in[i] == prev)
			{
				i++;
				sz++;
			}
			doit(i,max_group_size,sz,prev);
		}
		else
		{
			max_group_size = max(max_group_size,curr_size);
			i = pos;
			sz = 0;
			while(i<n && (in[i] != '?') && in[i] != in[pos])
			{
				sz++;
				i++;
			}
			doit(i,max_group_size,sz,in[pos]);			
		}
		
	}
	else
	{
		char arr[2];
		int ind=0;
		if(pos != 0)
		{
			
			int used = (prev-'0')^1;
			char c1 = char('0'+used);
			//max_group_size = max(max_group_size,curr_size);
			arr[ind] = c1;
			ind++;
		}
		if(pos + 1 < n && in[pos+1] != '?' && in[pos+1] != prev)
		{
			int c1 = in[pos+1] - '0';
			c1 = c1^1;
			arr[ind] = char('0' + c1);
			ind++;
		}
		if(pos + 1 < n && in[pos+1] != '?' && in[pos+1] == prev)
		{
			doit(pos+1,max_group_size,1,(prev-'0')^1);
			return;
		}
		if(ind == 0)
		{
			arr[0] = '0';
			arr[1] = '1';
		}
		if(ind == 1)
		{
			arr[1] = char('0' + ((arr[0]-'0')^(1)));
		}
		if(arr[0] == prev)
		{
			if(max_group_size < ans)
			doit(pos+1,max_group_size,curr_size+1,arr[0]);
		}
		else
		{
			max_group_size = max(max_group_size,curr_size);
			if(max_group_size < ans)
			doit(pos+1,max_group_size,1,arr[0]);
		}
		
		if(arr[1] == prev)
		{
			if(max_group_size < ans)
			doit(pos+1,max_group_size,curr_size+1,arr[1]);
		}
		else
		{
			max_group_size = max(max_group_size,curr_size);
			if(max_group_size < ans)
			doit(pos+1,max_group_size,1,arr[1]);
		}
	}
}
int main()
{
    int t;
    scanf("%d",&t);
    getchar();
    int ca = 1;
    while(t--)
	{
		gets(in);
		n = strlen(in);
		max_optimum_group();
		ans = max_group;
		//cout << max_group << endl;
		doit(0, 0, 0, '-');

		printf("Case %d: %d\n",ca++,ans);
	}
    return 0;
}

[brianfry713]

Your algorithm is wrong. Try input:

Code: Select all

1
0?1

AC output 2

[brianfry713]

Shadek, your doit function is wrong also. Your code does not make sense.

I first calculate the optimum max group based on the existing 0's and 1's. That is a pruning optimization. It tells me that I'm not going to get a smaller result so I should stop searching. My backtracking function would still get the same result without that code, but would TLE. I have a global variable best that starts at the length of the string and then is updated when the backtracking function has reached the end of the string and I get a smaller result. If best is equal to the optimum max group size then I stop searching.