11357 - Ensuring Truth

All about problems in Volume 113. 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
RoBa
New poster
Posts: 8
Joined: Thu Aug 11, 2005 7:57 pm

11357 - Ensuring Truth

Post by RoBa » Sun Nov 25, 2007 5:27 pm

SAT is NPC, so... how to solve it? Is there something about randomization algorithm? :o
Let it be

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

Post by jah » Sun Nov 25, 2007 5:40 pm

SAT is formulated as: (a|b|c)&(c|d|~d) .... etc

This problem is formulated as (a&b&c)|(c&d&~d) .... etc

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Fri Nov 30, 2007 10:10 pm

I am getting WR.
Whats wrong in my code?

Code: Select all


// Remove after Acc

Thanks
Keep posting
Sapnil
Last edited by sapnil on Sat Dec 01, 2007 5:32 pm, edited 1 time in total.
"Dream Is The Key To Success"

@@@ Jony @@@

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Nov 30, 2007 10:23 pm

Try this.
Input:

Code: Select all

1
(x&~x)|(x)
Output:

Code: Select all

YES
-----
Rio

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Sat Dec 01, 2007 5:34 pm

Thanks rio

I really miss intilize.

Thanks
keep posting
sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

abdullah<cse du>
New poster
Posts: 39
Joined: Mon Dec 04, 2006 2:18 pm
Location: Bangladesh(CSE DU)
Contact:

Post by abdullah<cse du> » Mon Dec 10, 2007 4:33 pm

Hi all,

The problem gives me simply WA. I can't find out any problem in my code. Please help me to locate my errors.

Code: Select all

//Problem: Ensuring Truth-11357
//Status : 
//Algorithm : Boolean Exp. slution.

#include<stdio.h>
#include<string.h>
#define max 300

char stack [max];

void result(void)
{
	int res[max];
	int i,top=0;

	for(i=0; stack[i]; i++)
	{
		if(stack[i] >='a' && stack[i] <='z')
			res[top++] = 1;

		else if(stack[i] == '&')
		{
			res[top-2] = res[top-2] & res[top-1];
			top--;
		}

		else if(stack[i] == '|')
		{
			res[top-2] = res[top-2] | res[top-1];
			top--;
		}

		else if(stack[i]=='~' && res[top-1])
			res[top-1]=0;

		else if(stack[i]=='~' && (!res[top-1]))
			res[top-1]=1;
			
	}

	if(res[top-1])
		printf("YES\n");
	else
		printf("NO\n");
}

void process(char *input)
{
	char save[max];
	int i,j=0,k=0,l;
	
	l = strlen(input);
	input[l]=')'; input[l+1]='\0';

	save[k] = '(';  k = 1;

	for(i=0; input[i]; i++)
	{
		if(input[i] == '(')
			save[k++] = input[i];

		else if(input[i] >='a' && input[i] <='z')
			stack[j++] = input[i];

		else if(input[i] == '~')
			save[k++] = input[i];

		else if(input[i] == ')')
		{
			while(k>0 && save[k-1]!='(')
				stack[j++] = save[--k];
			k--;
		}

		else if(input[i] == '&' || input[i] == '|')
		{
			while(k >0 && save[k-1]!= '(')
				stack[j++] = save[--k];

			save[k++] = input[i];
		}
	}
	save[k]='\0';
	stack[j]='\0';
}

void take_input(void)
{
	char input[max];
	int i,j=0;

	gets(input);
	for(i=0;input[i];i++)
	{
		if(input[i]==' ' || input[i]=='\t')
			continue;
		else
			input[j++]=input[i];
	}
	input[j]='\0';

	process(input);
	result();
}

int main(void)
{
	int test;
	//freopen("f:\\acm\\in.txt","rt",stdin);
	
	scanf("%d\n",&test);

	while(test--)
	{
		take_input();
	}
return 0;
}
Thanks
ABDULLAH
We were in past, we are in past and we will go in past.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Dec 11, 2007 12:11 am

I think you had little misunderstood the problem.
You code assigns only true to every variable.
But the problem statement says:
A formula is called satisfiable if it is possible to assign values to its variables in such a way as to make the formula evaluate to true.
So for test case:

Code: Select all

1
(~x)
You must output "YES".
-----
Rio

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Post by RC's » Fri Jan 18, 2008 9:05 am

I got TLE for this problem.
Is there any fast method to solve this problem ?
I use backtracking to determine if it is possible to evaluate the function and if one solution can generate 'TRUE' then i stop the backtrack..

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Jan 18, 2008 9:25 am

RC's wrote:I got TLE for this problem.
Is there any fast method to solve this problem ?
I use backtracking to determine if it is possible to evaluate the function and if one solution can generate 'TRUE' then i stop the backtrack..
Hint: there is a non-backtracking way to solve this problem

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Post by RC's » Fri Jan 18, 2008 3:28 pm

okay, now I get WA..
Any more tricky test cases ?
I have tried all input in the posts above

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Location: Dhaka , Bangladesh
Contact:

Re: 11357 - Ensuring Truth

Post by mukit » Wed Jul 30, 2008 10:47 pm

I am getting W.A. in this problem

Code: Select all

#include<stdio.h>
#include<string.h>
int main()
{
	int op,len,j,i,l,k,t,stack[1001],exp[1001],car;
	char in[300],_in[300];
	bool is;
	scanf("%d",&t);
	gets(_in);
	for(j=0;j<t;j++)
	{
		k=0;
		l=0;
		op=0;
		car=0;
		gets(_in);
		len=strlen(_in);
		in[0]='(';
		int ct=1;
		for(i=0;i<len;i++)
		{
			if((_in[i]>='a' && _in[i]<='z') || _in[i]=='&' || _in[i]=='|' || _in[i]=='~' || _in[i]=='(' || _in[i]==')')
			{
				in[ct]=_in[i];
				ct++;
			}
		}
		in[ct]=')';
		in[ct+1]='\0';
		len=strlen(in);
		for(i=0;i<len;i++)
		{
			if((in[i]=='(') || (in[i]=='&') || (in[i]=='|') || (in[i]=='~'))
			{
				stack[k]=in[i];
				k++;
				if(in[i]=='&'||in[i]=='|'||in[i]=='~')
				{
					op++;
				}
			}
			else if(in[i]>='a'&&in[i]<='z')
			{
				exp[l]=in[i];
				l++;
				car++;
			}
			else if(in[i]==')')
			{
				while(k>0)
				{
					k--;
					if(stack[k]!='(')
					{
						exp[l]=stack[k];
						l++;
					}
				}
			}
			else
			{
				
			}
		}
		stack[k]='\0';
		exp[l]='\0';
		char st2[300];
		int top=0,_p=0;
		for(int i=0;i<l;i++)
		{
			if(exp[i]=='&'||exp[i]=='|'||exp[i]=='~')
			{
				if(exp[i]=='&')
				{
					st2[top-2]=st2[top-2]&st2[top-1];
					top--;
				}
				else if(exp[i]=='|')
				{
					st2[top-2]=st2[top-2] | st2[top-1];
					top--;
				}
				else
				{
					for(int p=0;p<len;p++)
					{
						if(in[p]==st2[top-1])
						{
							_p++;
						}
					}
					if(_p>1)
					{
						st2[top-1]=!st2[top-1];
					}
				}
			}
			else
			{
				st2[top]=exp[i];
				top++;
			}
		}
		if((st2[top-1]!=false) || op<=1 || car<=1)
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}

Please post some critical input-output.
Is there any tricky way to solve this ?

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11357 - Ensuring Truth

Post by emotional blind » Fri Aug 01, 2008 2:19 pm

try this input

Code: Select all

(x&~y)|(y&~y)

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Re: 11357 - Ensuring Truth

Post by RC's » Mon Aug 04, 2008 10:17 pm

My program outputs "YES" for your input, but I still get WA.. Any more test cases ?

Post Reply

Return to “Volume 113 (11300-11399)”