## 11199 - Equations in Disguise

Moderator: Board moderators

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

### 11199 - Equations in Disguise

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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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
Your output matches the output from standard solution

Code: Select all

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

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
Your output is incorrect. Once you've figured out the correct output, u'll probably get AC.

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

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
!!! I finaly understood what was wrong. Thanks rujialiu
I'll try to fix it.

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

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Got AC Thanks for help.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

### Re: 11199 Equations in Disguise

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?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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