11199 - Equations in Disguise

rio · 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

little joey · 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 · 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

rio · 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 · 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.

rio · 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 · 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

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

!!!

I finaly understood what was wrong. Thanks rujialiu

I'll try to fix it.

rio · 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 · 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.

rio · 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.

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

Got AC

Thanks for help.

sclo · 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.

hank · 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.

rio · 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

UVa OJ Board

11199 - Equations in Disguise

11199 - Equations in Disguise

Re: 11199 Equations in Disguise