271 - Simply Syntax

[Felipe Santos Pinheiro]

Hi,

In the problem 271 (Simply Syntax), the output say "... the list of answers is followed by an end-of-file character." How I can print the EOF character?

[Stefan Pochmann]

Don't. Just ignore that silly statement.

[Fresh]

I normally use this style,

[cpp]
int len;
char s[1024];

while (cin.getline(s,1024))
{ if (!(len = strlen(s))) break;
process(s,len);
}
[/cpp]

-novice

[htl]

The last data makes me confused.

In:
Cqpq

Out:
NO

And I think it's YES because the substring after C can be divide into 2 right sentences 'q','pq' or 'qp','q'

Could someone tell me why?

[xenon]

Every character from p..z is a correct sentence. This applies only to characters, not to strings made up of characters. So 'pq' and 'qp' are not correct sentences. So 'Cqpq' is one character too long.

[htl]

My code got TLE. I can't find out where I can improve the code. Could someone help me?
[c]
#include<stdio.h>
#include<string.h>
int check(char [],int,int);
void main(void)
{
char s[300];
while(scanf("%s",s)!=EOF)
if(check(s,0,strlen(s)-1))
printf("YES\n");
else
printf("NO\n");
}
int check(char s[],int start,int end)
{
int x;
if(start==end)
{
if(s[start]>='p' && s[start]<='z')
return 1;
else
return 0;
}
if(s[start]=='N' && check(s,start+1,end))
return 1;
if(s[start]=='C' || s[start]=='D' || s[start]=='E' || s[start]=='I')
{
if(end-(start+1)+1<2)
return 0;
for(x=start+1;x<end;x++)
if(check(s,start+1,x) && check(s,x+1,end))
return 1;
}
return 0;
}
[/c]

[obayashi]

I actually use DP to solve this problem but the speed is not so satisfactory
It ran 26 secs...

i hope that somebody could help me with the poor speed
here is the code

[cpp]

#include <iostream>
#include <string.h>
using namespace std;
int valid[128],ok[300][300];
char str[300];
void init () {
for (int i=0;i<128;i++) valid = 0;
for (char ch='p';ch<='z';ch++) valid[ch] = 1;
valid['N'] = valid['C'] = valid['D'] = valid['E'] = valid['I'] = 1;
}
int check (int s,int t) {
int i,len,flag;
len = t-s+1;
if (ok[s][t]>=0) return ok[s][t];
if (len<0) return 0;
if (str[s]=='N') {
ok[s+1][t] = check(s+1,t);
return ok[s+1][t];
} else if (str[s]=='C' || str[s]=='D' || str[s]=='E' || str[s]=='I') {
for (i=1;i<len;i++) {
ok[s+1][s+i] = check(s+1,s+i);
ok[s+i+1][t] = check(s+i+1,t);
flag = (ok[s+1][s+i] && ok[s+i+1][t]);
if (flag) {
ok[s][t] = 1;
return 1;
}
}
ok[s][t] = 0;
return 0;
}
ok[s][t] = 0;
return 0;
}
int main () {
int i,j,len,flag;
init();
while (cin>>str) {
flag = 1;
len = strlen(str);
for (i=0;i<=len;i++)
for (j=0;j<=len;j++)
ok[j] = -1;
for (i=0;i<len;i++) {
if (!valid[str]) flag = 0;
ok = (str>='p' && str<='z');
}
if (!flag) {
cout<<"NO"<<endl;
} else if (check(0,len-1)) {
cout<<"YES"<<endl;
} else {
cout<<"NO"<<endl;
}
}
return 0;
}

[/cpp]

[bjacoke001]

My program also took over 20 seconds for the problem, and I used the same DP that you did. Does anyone have an idea why it would take so long?

[obayashi]

with a glance at this problem, i thought it just another easy one which would be solved by
simple recursion. but i was wrong. i got TLE first, then i modified my code a little and got AC.

what about the string

NNNNNNN...NNNNNNNNCst
253 N 1 C 1 s 1 t totally 256 chars

how long does your program run with this string?

i think with DP it should gimme a nlog(n), but it didn't.

actually it gimme a n^2, not nlog(n), cos i divide the string from its head...

i think if with divide this string from the middle, then re-middle ..., it will be ok.

just like the difference between bubble sort and quicksort.

Do u think so?

I will fix it when free.

[Dominik Michniewski]

I got accepted with this problem and I use only simple recursion ...
I think, that you must make one of following mistakes in your resursive solution:
1. didn't right handle of end of string
2. had an error in recursion .....
my recursive function is very simple

Best regards
Dominik

PS. My program took 0.01 sec and 64 kB RAM

[obayashi]

thanx, i will go find it and get it fixed~

[shuan_ck]

I got WA.
Anyone tell me why, please?

Code: Select all

#include<iostream>
#include<stack>
#include<string>
using namespace std;

int main()
{
    string t;
    while(cin>>t){
        stack<char> s;
        int q=0;
        for(int i=0;i<t.size();i++){
            if(t[i]<'a')
                s.push(t[i]);
            else{
                q++;
            }
            while(q>1){
                if(s.empty()){
                    i=t.size();
                    break;
                }
                if(s.top()!='N')
                    q--;
                s.pop();
                while(!s.empty()&&s.top()=='N')
                    s.pop();
            }
        }
        if(q>1||!s.empty())
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
}

[sohel]

Hi,

Rule 2 states that 'If s is a correct sentence, then so is Ns.'
I may be wrong but I think your program gives wrong output for cases such as Np, Nx etc.

[shuan_ck]

Thanks a lot. That should be one of my mistakes.

[stcheung]

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.