271 - Simply Syntax

[junbin]

I got TLE at first too (it's unfortunate that time limit is now 10 second instead of the previous 30 second). I just got AC using 0.5 second by the stack approach. Basically just start at the end of the string, and whenever you see one of the C, D, E, or I, check if stack has at least 2 correct sentences. Let's say the current char is C, and the stack has 2 correct sentences on the top, then they can all be combined into one correct sentence and pushed onto the stack. If the stack doesn't have 2 correct sentences on the top, then you can immediately judge the string as incorrect.

Another optimization is to take out the N.

Starting from the front, using recursion, I got 0.12s..

This is a very simple parsing question. There is no need for branching, so no need for DP.

Realise that

If X is a sentence and Y is a sentence, XY is NOT a sentence.

This effectively tells you how the recursion should go.

[lovemagic]

Can anybody give me some sample input & output for p271?

[tuyide]

Is there anybody so kind to give me some advice?


[cpp]
#include <iostream>
#include <cstring>
using namespace std;
int key[255];
int is(char *p)
{
int stack[300],stack1[300],now,f;
int i,at=0;
int len=strlen(p);
for(i=0;i<len;i++)
{
if(p=='N')continue;
stack[at++]=key[p];
}
while(1)
{
now=0;
f=0;
for(i=0;i<at;i++)
if(i<at-2&&stack==2&&stack[i+1]==1&&stack[i+2]==1)
{f=1;stack1[now++]=1;i+=2;}
else stack1[now++]=stack;
for(i=0;i<now;i++)
stack=stack1;
at=now;
if(!f)break;
}
if(at==1&&stack[0]==1)
return 1;
return 0;
}
int main()
{
int i;
for(i=0;i<255;i++)
key=0;
for(i='p';i<='z';i++)
key=1;
key['E']=2;
key['I']=2;
key['C']=2;
key['D']=2;
char s[1000];
while(cin.getline(s,1000))
{
if(is(s))
cout<<"YES\n";
else
cout<<"NO\n";
}
return 0;
}
[/cpp]
Thank a lot!

[hiloshi]

try this.

Code: Select all

EppIqq

You should output "Yes".

[d91-lek]

EppIqq

You should output "Yes".

Oh, but that is not a valid sentence. Two, yes, but we should
only output YES for exactly one valid sentence per line. Please
refer to the final example: Cqpq.

[biterman]

Hi,

I apologize for starting a new topic, but the other posts on this problem seemed abandoned and I didn't know how bumping is looked upon here.

I've submitted a few solutions to this problem, after an initial WA, thinking that I might have interpreted the problem erroneously. And after some long testing and a lot of thought I've come up with this code that as far as I can tell /should/ solve the problem. I've also seen code from other people with the same interpretation of the problem, perfectly good C code mind you, and it also gets WA.

Thus I can only conclude that I must be misinterpreting the problem. I'll stop ranting and let the code speak for itself.

Code: Select all

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAX_STR 100

char validUpper[] = { 'N', 'C', 'D', 'E', 'I' };
#define VU_MAX (sizeof validUpper / sizeof(char))

int isValidLower(char c);
int isValidUpper(char c);
int isValidSent(char *str);

int main(int argc, char **argv)
{
    char buff[MAX_STR][BUFSIZ];
    size_t c, i;
    for(c = 0; c < MAX_STR; c++)
    {
        fgets(buff[c], BUFSIZ, stdin);
        if(*buff[c] == EOF || *buff[c] == '\0')
        {
            break;
        }
        else if(isValidSent(buff[c]))
        {
            memset(buff[c], 0, BUFSIZ);
            strcpy(buff[c], "YES");
        }
        else
        {
            memset(buff[c], 0, BUFSIZ);
            strcpy(buff[c], "NO");
        }
    }
    puts("");
    for(i = 0; i < c; i++)
        printf("%s\n", buff[i]);
    return 0;
}

int isValidLower(char c)
{
    return ((c - 'p') >= 0 && ('z' - c) >= 0);
}

int isValidUpper(char c)
{
    size_t i;
    for(i = 0; i < VU_MAX; i++)
        if(c == validUpper[i])
            return 1;
    return 0;
}

int isValidSent(char *str)
{
    if(str != NULL && *str != '\0')
    {
        size_t l = strlen(str) - 1;
        if(l == 1 || l == 0)
            return isValidLower(*str);
        else if(l == 2)
        {
            if(isValidUpper(*str))
            {
                if(*str != 'N')
                    return 0;
                else
                    return isValidSent((str + 1));
            }
            else if(isValidLower(*str))
            {
                if(isValidUpper(*(str - 1)))
                    return isValidSent((str + 1));
            }
            else
                return 0;
        }
        else
            if(isValidUpper(*str) || isValidLower(*str))
                return isValidSent((str + 1));
    }
    return 0;
}

Thanks in advance

adios,
biterman.

PS: I realize this is certainly not the /best/ way to go about things, I/O and the crux of the problem.

[mf]

Try these test cases:

Code: Select all

CDEIpqrst
CCppp

For each of the above cases, the answer must be "YES".

Also, your program prints unnecessary empty line at the start of output - you'll get P.E. for that.

[edit]
I/O code seems to be incorrect: I got different answers from your program, when I deleted newline characters at the end of input.

[biterman]

From those cases one infers that a succession of characters from p through z form a valid sentence, i.e.: pqrst. Given the fact that 'Ipqrst' needs to be two sentences thus we could have 'Ipq' and 'rst', or any other combination which satisfies Ist.

I believe that to achieve this with the code I've written one needs only comment out the line:

Code: Select all

if(isValidUpper(*(str - 1))) 

Which is inside isValidSent(). Having done this the test cases you suggest do return YES for output.

About the code behaving strangely when you delete the newline character at the end of input, I wrote the code counting on that newline because it is stated in the Input portion of the problem description that: "Each sentence is ended by a new-line character."

I've removed the unnecessary new-line character at the start of output, thank you.

I added

Code: Select all

buff[c][strlen(buff[c]) - 1] = '\0';

Right after receiving input, as I see it effectively deleting the newline character and still got a YES reply for the test cases you suggested, and many others besides.

Thank you again for your help

adios,
biterman.

[mf]

A succession of p..z does not necessarily form a valid sentence. It depends on the context. 'pqrst' alone is not a valid sentence, but 5 independent concatenated sentences.

But 'CDEIpqrst' is a valid single sentence. Here I intentionally put brackets to delimit smaller sub-sentences (except those of form p..z) inside it:

Code: Select all

C(D(E(Ipq)r)s)t

Going from bottom to top:

By rule 1, 'p' and 'q' are two valid sentences.
By rule 3, 'Ipq' is a valid sentence, because it is a capital 'I', followed by exactly two valid sentences - 'p' and 'q'.
Then again by rule 1, 'r' is a valid sentence.
And by rule 3, 'EIpqr' is also valid: capital 'E', followed by two valid sentences 'Ipq' and 'r', concatencated together.
And so on.

[biterman]

...I must completely reevaluate my interpretation of the problem and my solution. Your suggestions have been most enlightening.

Thank you very much.

adios,
biterman.

[serendipity]

can someone tell me why my code shows the CE?

#include<stdio.h>
#include<conio.h>

int find_min(int p,int q)
{
if(p>q)
return q;
else
return p;


}

int main(void)
{
long cs;
int m, n;
char chpcs;

scanf("%ld", &cs);

while(cs)
{
chpcs=getch();
scanf("%d %d",&m,&n);

if(chpcs=='r'||chpcs=='Q')
printf("%d\n", find_min(m,n));


else if(chpcs=='k')
printf("%d\n",m*n/2);

else
printf("%d\n",( ((m+1)/2) * ((n+1)/2) ) );


cs--;


}
return 0;
}

[ayon]

no <conio.h> is allowed, no getch() is allowed

[Joseph Kurniawan]

If you're trying to use a certain C function, you should first check it's portability in UNIX.
How do we do that?
Quite simple.
For example :
You're trying to use getch();
Move your cursor to the getch(); and then press Ctrl+F1. The help Screen which provides all information about getch(); will appear. Keep scrolling down until you find the portability table.
If in the UNIX column is written "Yes", then the function is recognized in the Judge's GCC compiler.
As far as I know, every single function provided in conio.h is not portable for UNIX, therefore if you use them, it will produce CE.
you can use this method for every function.
Good luck!

[cytmike]

To all people who are getting TLE, there is an algorithm posted on Methods to Solve website. It takes 0.5s to run.

http://www.comp.nus.edu.sg/~stevenha/pr ... y%20Syntax

[Kire Sopov]

What's wrong with this code. I tried so many input cases and it seems to work ok. Are there any special cases I'm missing?

[code]
#include <iostream>
#include <string>

#define IsPZ(ch) (((ch) >= 'p') && ((ch) <= 'z'))

bool CheckValid(const std::string &ss, std::string::const_iterator it, int nValids)
{
if (nValids < 0) return false;
else if (it == ss.end()) return (nValids == 0);

if (IsPZ(*it)) return CheckValid(ss, ++it, nValids-1);

switch (*it)
{
case 'N':
while ((it != ss.end()) && (*it == 'N')) ++it;
return (it == ss.end()) ? false : CheckValid(ss, it, nValids);

case 'C':
case 'D':
case 'E':
case 'I':
return CheckValid(ss, ++it, nValids+1);

default:
return false;
}
}

int main()
{
std::string str;

while (std::getline(std::cin, str) != NULL)
{
std::cout << (CheckValid(str, str.begin(), 1) ? "YES" : "NO") << std::endl;
}
}
[/code]