Link to pdf version on UVa OJ
As you read in the problem statement, this definition of WFF (Well-formed formula) is recursive. We have single sentences p, q, r, s, t. Each WFF starts with one of these, because by definition these are WFF. Any larger WFF must be formed using these.
The problem asks us for the longest WFF possible from input.
What happened on my mind : all we have is the input, the longest WFF we can create is as long as input, so it's better to use as much character of it as possible.
After reading the problem statement I put characters into 3 groups, variables (pqrst), binary operators (KACE) and unary operator (N).
Soon I realized if we don't have any variables we can't form any WFF according to the definition of WFFs.
Then I realized if we can make any WFFs at all we can put all the Ns at the beginning of it and it is still valid and it is still WFF. (Remember our goal is to use as much characters from input as possible)
Now I have to think about binary operators. I tried to play with different examples on paper to come up with some pattern or something.
I checked KKpp --- best ---> Kpp
I checked KKpppp --- best ---> KKppp
I checked KKKpppp, then I came up with KKppKpp, and KKKpppp, both are WFFs. Then I realized, other than the starting variable, every binary operator can add a single variable (this pattern KKKpppp).
If I want to explain this step by step :
first WFF = p
now I take one p and one K and WFF = Kpp
now I have the option to create another Kpp and finally merge them together like K(Kpp)(Kpp)
or add one K and one p like K(Kpp)(p) and then add another K and p like K(K(Kpp)(p))(p)
For more details please refer to my code on github
As you read in the problem statement, this definition of WFF (Well-formed formula) is recursive. We have single sentences p, q, r, s, t. Each WFF starts with one of these, because by definition these are WFF. Any larger WFF must be formed using these.
The problem asks us for the longest WFF possible from input.
What happened on my mind : all we have is the input, the longest WFF we can create is as long as input, so it's better to use as much character of it as possible.
After reading the problem statement I put characters into 3 groups, variables (pqrst), binary operators (KACE) and unary operator (N).
Soon I realized if we don't have any variables we can't form any WFF according to the definition of WFFs.
Then I realized if we can make any WFFs at all we can put all the Ns at the beginning of it and it is still valid and it is still WFF. (Remember our goal is to use as much characters from input as possible)
Now I have to think about binary operators. I tried to play with different examples on paper to come up with some pattern or something.
I checked KKpp --- best ---> Kpp
I checked KKpppp --- best ---> KKppp
I checked KKKpppp, then I came up with KKppKpp, and KKKpppp, both are WFFs. Then I realized, other than the starting variable, every binary operator can add a single variable (this pattern KKKpppp).
If I want to explain this step by step :
first WFF = p
now I take one p and one K and WFF = Kpp
now I have the option to create another Kpp and finally merge them together like K(Kpp)(Kpp)
or add one K and one p like K(Kpp)(p) and then add another K and p like K(K(Kpp)(p))(p)
For more details please refer to my code on github
No comments:
Post a Comment