Page 1 of 2

### 11199 - Equations in Disguise

Posted: 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
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
``````

Posted: 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...

Posted: Thu Apr 05, 2007 2:21 pm
Your output matches the output from standard solution

Code: Select all

``````2
abcdefghijk
kcachlflfgd
0
``````

Posted: 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+
``````

Posted: Thu Apr 05, 2007 6:14 pm
Your output is incorrect. Once you've figured out the correct output, u'll probably get AC.

Posted: 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.

Posted: 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

Posted: Fri Apr 06, 2007 2:32 am
!!! I finaly understood what was wrong. Thanks rujialiu
I'll try to fix it.

Posted: 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*
``````

Posted: 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.

Posted: 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.

Posted: Sun Apr 08, 2007 7:05 pm
Got AC Thanks for help.

Posted: 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.

### Re: 11199 Equations in Disguise

Posted: 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?

Posted: 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