## 11357 - Ensuring Truth

Moderator: Board moderators

RoBa
New poster
Posts: 8
Joined: Thu Aug 11, 2005 7:57 pm

### 11357 - Ensuring Truth

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

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am
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:
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 @@@

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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:
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
Contact:
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.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
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
Contact:
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
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
Contact:

### Re: 11357 - Ensuring Truth

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


Is there any tricky way to solve this ?

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

### Re: 11357 - Ensuring Truth

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

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