11199 - Equations in Disguise

All about problems in Volume 111. 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
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

11199 - Equations in Disguise

Post by rio » Thu Apr 05, 2007 11:26 am

This is a realy hard problem. Hard to avoid TLE.
I manage to run in time (over 40 sec), but now I'm getting WA.

If you have tried this problem, and made some io test cases,
please share it here. (Even If you are not sure that it is valid).

Heres some test cases I made (I'm not sure its valid).
INPUT

Code: Select all

1
abcdefghijk
2
abcabbeabbb
abcbeb
4
abcdedb
bcaeb
bfaea
dfafaeab
3
abcdefgh
gdibafjdc
cdkfc
2
abcdefgh
gdibafjdc
1
afghaj
2
abcdefghijk
adegjkh
3
abaec
cbced
dbdef
2
abaec
cbced
3
aikabegda
eghmbikj
dikabega
10
aaeaa
bbebb
ccecc
ddedd
ffeff
ggegg
hhehh
iieii
jjejj
kkekk
0
OUTPUT

Code: Select all

Case 1: Oops
Case 2: a1 b0 c* e=
Case 3: a1 b0 c* d8 e= f+
Case 4: f=
Case 5: f=
Case 6: a1 f+ g9 h= j0
Case 7: No
Case 8: a1 b+ c2 d4 e= f8
Case 9: Oops
Case 10: No
Case 11: No

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Apr 05, 2007 1:48 pm

Haven't solved it yet, and indeed I think it's a hard problem.
Looking over your cases (and contemplating ideas :)), I stumbled on case 9.
Why is it not "e="? I don't think 'b' can be the equal sign, or am I being very stupid?

EDIT: duh, I'm being very stupid :) 'b' can also be an equal sign...

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

Post by rujialiu » Thu Apr 05, 2007 2:21 pm

Your output matches the output from standard solution :)

Please try this case and tell me your answer.

Code: Select all

2
abcdefghijk
kcachlflfgd
0
:-)

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

Post by rio » Thu Apr 05, 2007 3:35 pm

Thanks for replies.

For rujialiu's input, my code outputs:

Code: Select all

Case 1: a1 b5 c* d4 e9 f2 g= h7 i3 j8 k0 l+

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

Post by rujialiu » Thu Apr 05, 2007 6:14 pm

Your output is incorrect. Once you've figured out the correct output, u'll probably get AC.
:-)

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

Post by rio » Thu Apr 05, 2007 7:04 pm

I got one solution for the input.

Code: Select all

equation1 : 15*492=7380
equation2 : 0*1*7+2+2=4
I think this solution is valid (Or am I misinterpriting something ??).

I runned the code with out pruning (which may have bug), but couldn't find other solution.
I also tried to find other solution by pen-and-paper, but soon my brain overflowed.
I re-read the output format, but I think I'm outputing right.

What shoud be the correct output ? Only a hint would help me.
Thanks in advance.

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

Post by rujialiu » Fri Apr 06, 2007 2:03 am

Please make sure that you did not miss any information from the first sentence of the problem description. Then you will know why your output is incorrect with eyes :)
:-)

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

Post by rio » Fri Apr 06, 2007 2:32 am

!!! :o I finaly understood what was wrong. Thanks rujialiu :D
I'll try to fix it.

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

Post by rio » Fri Apr 06, 2007 8:03 am

I think I fixed it properly, but still getting WA..
Anyway, I'll add some test cases here.
INPUT:

Code: Select all

2
abcdefedcba
hijfabcde
2
abcdefghijk
kcachlflfgd
12
aaeaa
bbebb
ccecc
ddedd
ffeff
ggegg
hhehh
iieii
jjejj
ikiei
jkmem
akaeb
3
abcdefghijk
jbaefcgbga
jbcfl
0
OUTPUT:

Code: Select all

Case 1: c+ f= h1
Case 2: a1 b5 c* d4 e9 f2 g= h7 i3 j8 k0 l+ m6
Case 3: e= i1 k* l+ m0
Case 4: b+ f= i*

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

Post by rujialiu » Fri Apr 06, 2007 9:03 am

Yes they're correct - and your 3rd case is nice ;)
You may want to send me your code so that I can check it for you.
:-)

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

Post by rio » Fri Apr 06, 2007 10:51 am

I will re-write my code (Its quite large and ugly. I don't whant to show this code for shame).
After re-writing the code, and still gets WA, I will send the code to you.

Thanks for your help. :)

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

Post by rio » Sun Apr 08, 2007 7:05 pm

Got AC :D Thanks for help.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Jun 20, 2007 12:10 pm

It is very easy to get TLE for this problem. Now, I passed all testcases above, but still get WA. I think I have problem checking for unique solutions.

I finally got AC, I wasn't generating enough solutions before.

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Re: 11199 Equations in Disguise

Post by hank » Sun Jul 15, 2007 8:15 am

rio wrote:This is a realy hard problem. Hard to avoid TLE.
I manage to run in time (over 40 sec), but now I'm getting WA.

If you have tried this problem, and made some io test cases,
please share it here. (Even If you are not sure that it is valid).
...
Hello rio,

I try to solve this problem, but always get TLE. :(
I use backtracking to find all the one-to-one mappings of all letters, and
calculate the expressions to check if it is valid.
My program's output is the same as you provide above.
For the input you provide above, my program takes about 6 minutes to finish.
I think it is tooo slow.
I am curious about how to solve this problem more efficiently.
Could you give me some hints?

Thanks in advance.

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

Post by rio » Sun Jul 15, 2007 9:44 am

You must to prune somehow. Also mapping order is important.

The mapping order I took is :

Code: Select all

1. map '=' to alphabet which appear once
2. map '*' and '+' to appear alphabets (or don't map)
3. map the rest appear alphabets to digits
Actually, step 3. takes almost of the time, so you must to prune during step 3.

One idea is to use the minimum and maximum value of left side and right side of '=' under the current mapping.
(I took this way, so I'm sure that this works.)

Another idea is mapping from the lower digits. (I haven't tried this one, so I'm not sure that this works)
example:
After mapping '=', '*' and '+', if you get:

Code: Select all

xxx+xx=xx*xx+xx     (x : some alphabet)
you can't map like below:

Code: Select all

xx1+x2=x3*x8+x1    (left sides lowest digit will be 3, right sides lowest digit will be 5)
----
Rio

Post Reply

Return to “Volume 111 (11100-11199)”