## 10825 - Anagram and Multiplication

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### 10825 - Anagram and Multiplication

I've found a simple formula for this problem (and perhaps many other people too).
It works correctly for judge's input.

But... is it correct in general for arbitrary n and if so, how to prove that?

Here is how I compute for case m = 4 (there are also two similar cases for m=6, and all others are "Not found."):

Code: Select all

``````if (m == 4 && (n % 5) == 2) {
a = (n - 2) / 5;
printf("%d %d %d %d\n",
a,
2 * a,
4 * a + 1,
3 * a + 1
);

} else if (m == 4 && (n % 5) == 3) {
a = (n - 3) / 5;
printf("%d %d %d %d\n",
a,
3 * a + 1,
4 * a + 2,
2 * a + 1
);
...
``````

Programmer
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am
Hello.
Can you give me output for these tests please.
Input

Code: Select all

``````6 7
6 8
6 9
6 11
0 0
``````
Thanks.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
And all cases where m = 6 and n != 3 (mod 7) and n != 5 (mod 7) seems to be "Not found" too.

Programmer
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am
Can you give me output for this tests.

Code: Select all

``````6 5
6 12
``````
Thanks.

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
i wasn't good enough to find any formula but my backtracking solution with some pruning was enough to pass through the time limit.

its really interesting to see that there exists some direct formula. but how did you end up with this pretty thing? just output pattern matching or is there any special method, it would be really nice if you share with us Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
by the way....
outputs for the inputs...

6 5
6 12

Code: Select all

``````
1 8 6 10 3 5

``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I also started with backtracking, but my best solution took minutes for the extreme case m=6 n=400.

I've made a table for small values and guessed the pattern. Linear patterns are especially easy to spot - the difference between two numbers in the sequence is constant.

The formula happens to give simply the base-n expansion of (n^4 - 1) / 5 for m=4, and (n^6 - 1) / 7 for m=6.

But it's still a mistery to me how it might be related to permutations of digits.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I have one of the 0.000s, and here's a hint:

1/7 = 0.142857...

I'm surprised Manzoor didn't realize this solution, and made the bounds so tight, and made a huge dataset accordingly. (Though I don't think he should change it now!)

contest_clarificator
Posts: 20
Joined: Fri Nov 30, 2001 2:00 am

### hmm

This problem is not original. You will get detailed discussion at the book:
How to solve it: Modern Huristics by David B. Fogel and Michalewicz page 274.

So I knew the math soln but did not use it considering it a programming contest . And Kisman's alternate solution was based on math.

filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:
Wow , nice solution.

I solved this problem using brute force (Until now, without any optimization)

Main idea is:

Let X = Xn Xn-1 ... X1 be solution in base B.

We start in this way:

Define Yi(X1) as the most left digit of X1 * i in base B, then Yi(X1) = (X*i) % B;

If there is a solution. Then it have to be some permutation of some N-Vector that is following.

[ Yn(1), Yn-1(1), .., Y1(1) ],
[ Yn(2), Yn-1(2), .., Y1(2) ],
.....
[ Yn(B-1), Yn-1(B-1), .., Y1(B-1) ].

In worst case 6! (permutation) * 400 (MAX value for B) * 5 (Multiply by 2..6) = 1,440,000 operations.

I know is not optimal. But it runs in 0.824.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
filigabriel, I also used your method and got AC in 0:00.434 sec.
To be honest, my solution was kind of a fluke. I was trying my luck. One thing I was sure is, if the method gives a solution for a particular set of input, then it is definitely correct. But I wasn't sure about the wheter 'not found' are really not founds.

In all cases, the time limit for this problem was too high, given the simple nature of this bruteforce solution. filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:
shamim wrote:I was trying my luck
Me too. At least, during online contest .

I dont know if a case exists where previous method doesn't find a solution. I think it's ok. Why?? I don't know how to explain it.

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

### I/O plz

Would you please give me some inputs and outputs.... !
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Hi fellows. What's the meaning of
mf wrote: The formula happens to give simply the base-n expansion of (n^4 - 1) / 5 for m=4, and (n^6 - 1) / 7 for m=6.
Thx in advance mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Antonio Ocampo wrote:Hi fellows. What's the meaning of
mf wrote: The formula happens to give simply the base-n expansion of (n^4 - 1) / 5 for m=4, and (n^6 - 1) / 7 for m=6.
Thx in advance I initially solved this problem by not-very-rigorous means, and obtained formulas for each digit in the output separately. That was enough for me to get accepted.

Trying to prove my results, I made a simpler formula:

Code: Select all

``````  m
n  - 1
--------
m + 1``````
If it produces an integer, which has exactly m digits in base n, and such that no digit is repeated, then the answer is just these digits. Otherwise the answer is "Not found."