11203 - Can you decide it for ME?

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

11203 - Can you decide it for ME?

Post by andmej » Mon May 21, 2007 8:46 am

Hello all, nice people:

I don't know why I am getting wrong answer at this problem.

Here's the input i'm trying:

Code: Select all

49
??M?E???
xM?Ex?
??M??E????
M?E?
??m?e???
?M?E??
12M12E????
ME
M?E
?M?E?
?ME?
ME?
???ME???
???M?E????
??????????M?E???????????
??????????M?E??????????
????????????????????M?E?????????????????????
????????????????????M?E??????????????????????
?????????????????????M?E???????????????????????
??????????????????????M?E????????????????????????
?M?E??M?E??
?M?E?M
??M??E???
??M??E????
??M???E???
??M???E????
?M????E?????
M????E?????
?M??E???
?M???E????
?M????E?????
?M?????E??????
?M??????E???????
?M???????E????????
?M????????E?????????
?M?????????E??????????
?M??????????E???????????
?M???????????E????????????
?M????????????E?????????????
?M?????????????E??????????????
?M??????????????E???????????????
?M???????????????E????????????????
?M????????????????E?????????????????
?M?????????????????E??????????????????
?M??????????????????E???????????????????
?M???????????????????E????????????????????
?M????????????????????E?????????????????????
?M?????????????????????E??????????????????????
?M??????????????????????E???????????????????????
And the output from my program:

Code: Select all

theorem
no-theorem
theorem
no-theorem
no-theorem
theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
theorem
theorem
no-theorem
theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
theorem
no-theorem
no-theorem
theorem
no-theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
theorem
Can somebody with an AC code please check this answers?
Does somebody have some extra critical input?

If you wan't I can post my code, but basically what I am doing is as follows:

1. Read the line

2. If the line contains a character different to M, E, or ? then output no-theorem and read next line

3. Extract x, y and z (as denoted in the problem: xMyEz) from the read string

4. If any one of these equals "" or contain a character different from ? then output no-theorem and read next line

5. If the delimiter between x and y is different from M or the delimiter between y and z is different from E, output no-theorem and read next line

6. If the length of y is greater than 1, then delete from y its last character and delete from z its last character until the length of y equals 1 ("un-theoremize").

7. If the length of x + 1 equals z, then it is an axiom, output theorem and read next line; else it is not valid, output no-theorem and read next line.

I alredy checked if the input method was correct and it seems like it is.

Any suggestion?

Thanks a lot for your help.

By the way, i'm sorry to post this problem at the CXI Volume's forum, but CXII Volume's forum is still not available.

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

Post by rio » Mon May 21, 2007 9:05 am

Your output is same as my AC code's.
Your alogrithm seems to be right (Actually, step 6, 7 could be done more simply).

Silly bug may be in your code.

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Mon May 21, 2007 10:25 am

There can be M & E more than 1.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Mon May 21, 2007 6:31 pm

Thanks for your answers.
rio wrote:Your alogrithm seems to be right (Actually, step 6, 7 could be done more simply).
How?
DP wrote:There can be M & E more than 1.
What do you mean with this?

Do you mean that M and E can appear in the string more than once? If that's what you mean, then they wouldn't be correct theorems, for instance, the input:

Code: Select all

10
?MM?EE??
?M?E???M?E??
ME?ME?ME?
??M??E????
??M??E?????
??M??E????M
??M??E???E??M?E??
?M?E?M
?M?E?E
?M?E??
produces this output:

Code: Select all

no-theorem
no-theorem
no-theorem
theorem
no-theorem
no-theorem
no-theorem
no-theorem
no-theorem
theorem
Last edited by andmej on Mon May 21, 2007 7:20 pm, edited 1 time in total.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon May 21, 2007 6:55 pm

STEP 6 & 7 ::

if( x + y == z ) yes;
else no;

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Mon May 21, 2007 7:20 pm

sohel wrote:STEP 6 & 7 ::

if( x + y == z ) yes;
else no;
Thanks.

I'm using this approach now but still can't get accepted. I'm beginning to beleive there is some sort of special case that i'm not considering. :( I'm going a little desperate now so I will post my Pascal code; Just in case some of you people would like to check it:

Code: Select all

program problem11203 (input, output);

begin
writeLn('Finally got accepted. Nice problem.');
end.
Sorry for being so newbish :oops:

Edit:

Anyone?

Some extra critical input?

Any idea?

Can you help me?

Thanks!
Last edited by andmej on Wed May 23, 2007 3:58 pm, edited 1 time in total.

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> » Wed May 23, 2007 7:13 am

Hi,

I have just got accepted the program. My procedure is:

1. Cheack for any invalid letters in the string (except '?' ,'M', 'E').
2. If number of 'M' or number of 'E' is more than one than invalid.
3. count '?' before 'M' (x), before 'E' (y)and than to the end of the string(z).
4. If any count is zero than invalid.
5. If x+y=z than valid.

I think this will help you.

ABDULLAH.
We were in past, we are in past and we will go in past.

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Post by Mushfiqur Rahman » Wed May 23, 2007 2:37 pm

Dear, andmej
I saw your approach but didn't found anyting wrong. Sometimes we face this problem, theres no error in the code and algorithm but judge giving WA.
In this circumstances we should re code the problem without opening the existing code.
If it fail then should leave it for few days. After some days should take the problem as a new problem and try to solve it without the help of previous code and approach.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby » Wed May 23, 2007 3:31 pm

andmej wrote:Any idea?

Can you help me?

Thanks!
Hello. I think your code has some really really small mistakes. Look at this line:

Code: Select all

if (s[1] <> 'M') then //if next char is not an M 
What if s is an empty string? What do you think will happen?

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Wed May 23, 2007 3:55 pm

tobby wrote:
andmej wrote:Any idea?

Can you help me?

Thanks!
Hello. I think your code has some really really small mistakes. Look at this line:

Code: Select all

if (s[1] <> 'M') then //if next char is not an M 
What if s is an empty string? What do you think will happen?
I think in that case a runtime error would produce, although that code got WA and no RE :-?

Or maybe it just exists from the function "isTheorem" and returns true, wich could be the correct explanation to WA :D

Begin of Edit:

I think that was exactly the problem, because of this:
I had several very unpleasant experiences with Runtime Errors (RE) being reported as Wrong Answer (WA).

Reason for those is mentioned in post about 'submitting Pascal'. It turns out that FPC does not emit error signal (at least not under Linux), so if RE occurs your program either just abort, leaving your result output unfinished (and thus producing WA), or it write few error strings and then abort, which again result in WA since those error strings were not expected in output.
(More here: http://online-judge.uva.es/board/viewtopic.php?t=12303)

Runtime errors are reported as WA in Pascal :x

End of Edit.

Anyway, I will remove this code because alredy got accepted.
Mushfiqur Rahman wrote:Dear, andmej
I saw your approach but didn't found anyting wrong. Sometimes we face this problem, theres no error in the code and algorithm but judge giving WA.
In this circumstances we should re code the problem without opening the existing code.
If it fail then should leave it for few days. After some days should take the problem as a new problem and try to solve it without the help of previous code and approach.
I did what you said and finally got accepted!

I was able to write shorter and clearer code on the second try. My new program was about 30 lines shorter than the old one. Thanks for the advice Musfiqur.

Thanks also to Abdullah for posting his algorithm.

SARKAR
New poster
Posts: 21
Joined: Tue May 22, 2007 4:18 pm

>>>andmej

Post by SARKAR » Sun May 27, 2007 9:27 am

can u plzzzzzzzzzzz telll me y
?M?E?
is not a theorem




10 case of ur 49 cases long input






sorry i misunderstood the problem
i got it now
[/b]

Freyr
New poster
Posts: 5
Joined: Sun Apr 22, 2007 8:47 pm
Contact:

Post by Freyr » Fri Jun 01, 2007 10:59 pm

Hmm, I've run all the test cases I can think off, and I'm not exactly sure why this keeps getting WA.

Anyone have any test data that can trip this program up?

Code: Select all

AC, thanks!
Thanks muchly!
Last edited by Freyr on Sat Jun 02, 2007 3:51 pm, edited 1 time in total.

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

Post by rio » Sat Jun 02, 2007 3:46 am

Try this.

Code: Select all

1
?E?E??
----
Rio

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Sat Jun 02, 2007 4:37 am

Changing line 18 for

Code: Select all

            if((line[i] == 'E' && ef) || (line[i] == 'M' && !ef)){ 
should do the job.

Please remove your code after this :D to not spoil the problem to others.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Freyr
New poster
Posts: 5
Joined: Sun Apr 22, 2007 8:47 pm
Contact:

Post by Freyr » Sat Jun 02, 2007 3:51 pm

Ah, of course! Well, I feel like an idiot now, haha. Thanks guys :)

Post Reply

Return to “Volume 112 (11200-11299)”