285 - Crosswords

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

Moderator: Board moderators

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

285 - Crosswords

Post by junbin » Mon Jan 05, 2004 10:59 am

Anyone can tell me what sort of weird test data they will provide?

Would these be possible:

1) The crossword requires a rotation before it fits.
2) Extra spaces are inserted before a row in the solution
3) Spaces are removed from the start/end/middle of a row in the solution
4) The crossword has to be shifted by an offset before it fits.

In essense, I would like to know the answer to the following test data:

(1)
abc 1 1 r
abc 1 1 d
#
3
3
cba b c$

(2)
abc 1 1 r
abc 1 1 d
#
3
3
abcb c $
abc 1 1 r
abc 1 1 d
#
3
3
abc b c $

(3)
abc 1 1 r
abc 1 1 d
#
3
3
abcbc $
abc 1 1 r
abc 1 1 d
#
3
3
abcb c$
abc 2 1 d
abc 1 2 r
#
3
3
a abcc $
abc 2 1 d
abc 1 2 r
#
3
3
a abc c $
abc 1 1 r
abc 1 1 d
abc 3 3 u
abc 3 3 l
#
3
3
abcbbcba$


(4)
abc 2 2 r
abc 2 2 d
#
3
3
abcb c $
abc 1 1 r
abc 1 1 d
#
4
4
abc b c $



Will any of the above sample test data result in correct solution?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Jan 05, 2004 11:20 am

My AC program assumes 1) No, 2) Yes, 3) Yes and 4) No.

So the first and last two of your inputs are incorrect solutions, and the other correct.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Mon Jan 05, 2004 2:26 pm

Thank you so much for your tips.. after some more trial and errors, I've managed to get AC. :)

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Sat Apr 10, 2004 3:19 am

This is what I'm doing, and it's wrong but I don't know why:

a) Build the actual crossword solution as a two dimentional matrix of characters, rembering the size of the matrix
b) create a string from that matrix by treating each row as a string and concatenating rows
c) removing all spaces from this constructed string
d) remove all spaces from the proposed solution
e) Return correct iff both strings agree and if the size of the actual solution's size agrees with the proposed solution's size

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Mon Jun 14, 2004 4:57 am

I've got the same problem

it's working for all the inputs I can think of, any tricky inputs or interpretation of the problem that we should know about?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Sat Jul 31, 2004 11:04 pm

Only I think you must assume: what is meaning of width and height of solution ;-) I made such mistake, so my first 3 submissions was rejected by judge

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Sun Aug 01, 2004 9:16 am

I'm pretty sure I did that properly - i verified whether the given width/height were indeed the minimums required (as stated in the problem), and if not, reported an incorrect solution. Is that the correct interpretation?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Aug 02, 2004 8:30 am

Problem is, that minimum width / height of crossword in this problem isn't real minimal width / height. I discovered it after a few of submissions. So if you have input like

Code: Select all

alas 2 1 r
#
4
1
alas$
you must report 'incorrect solution'. Why - try to think about ;-)

Best regards
DM

PS. Meaning of width/height in this problem isn't correct for me - and is far from reality :(
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Mon Aug 02, 2004 10:02 am

actually, my WA program *does* say "incorrect solution" for that one!

Thanks for trying to help though, I appreciate it.

EDIT: BTW, my program says "correct solution" when the input is:

Code: Select all

alas 2 1 r
#
5
1
alas$ 

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Wed May 03, 2006 6:40 pm

Anyone have any suggestions for this one?

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Thu May 04, 2006 1:42 am

I don't remember the details any longer since it's so long ago since I solved it, but here's the I/O I used when I solved it (your input is also in here somewhere):

Input:

Code: Select all

second 1 1 r
vis 1 3 r
file 2 4 u
castle 3 1 d
end 6 3 u
#
6
6
second la  nvis  e ft  l  e   $
sample 1 4 r
output 1 7 r
for 3 3 u
crossword 1 1 d
is 2 5 l
correct 1 1 r
#
7
9
correctr o    o f    sample  si     w      output r      d      $
ruben 1 1 r
einar 1 2 r
d 1 3 r
e 4 3 r
#
5
3
rubeneinard e $
alas 2 1 r
#
4
1
alas$
alas 2 1 r
#
5
1
alas$
alas 1 1 r
#
6
1
alas$
abc 1 1 r
abc 1 1 d
#
3
3
cba b c$
abc 1 1 r
abc 1 1 d
#
3
3
abcb c $
abc 1 1 r
abc 1 1 d
#
3
3
abc b c $
abc 1 1 r
abc 1 1 d
#
3
3
abcbc $
abc 1 1 r
abc 1 1 d
#
3
3
abcb c$
abc 2 1 d
abc 1 2 r
#
3
3
a abcc $
abc 2 1 d
abc 1 2 r
#
3
3
a abc c $
abc 1 1 r
abc 1 1 d
abc 3 3 u
abc 3 3 l
#
3
3
abcbbcba$
abc 2 2 r
abc 2 2 d
#
3
3
abcb c $
abc 1 1 r
abc 1 1 d
#
4
4
abc b c $
Output:

Code: Select all

The solution is correct.
The solution is correct.
The solution is correct.
The solution is incorrect.
The solution is correct.
The solution is incorrect.
The solution is incorrect.
The solution is correct.
The solution is correct.
The solution is correct.
The solution is correct.
The solution is correct.
The solution is correct.
The solution is correct.
The solution is incorrect.
The solution is incorrect.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Thu May 04, 2006 3:24 am

Thanks for the info, but unfortunately mine matches up with that so far.

I'll keep trying :)

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Thu May 04, 2006 3:48 am

If you still have your program around, can you check if adding spaces to the start of the solution line changes "correct" to "incorrect" or not?

Thank you,

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Thu May 04, 2006 4:14 am

Never mind, I got AC.

I wrote it again from scratch, and I guess I have better habits now -- it looks like some of the words don't use 'u', 'r', 'd', or 'l' to specify the direction, and I get AC when such entries are ignored completely (my WA prog would write the first letter into the grid at least).

This is definitely an issue with the problem statement which says: "Given crossword will always be correct."

Hope this will help some others!

User avatar
warenix
New poster
Posts: 5
Joined: Sun Aug 12, 2007 1:17 pm

Post by warenix » Sun Aug 12, 2007 1:19 pm

Hi all,

Why is this input incorrect?

Code: Select all

alas 1 1 r
#
6
1
alas$
Oh, after trials and errors, I know the reason now. (AC!)

The key is on the true meaning of "minimal" :lol:

Post Reply

Return to “Volume 2 (200-299)”