Page **1** of **2**

### 10825 - Anagram and Multiplication

Posted: **Sun Mar 13, 2005 2:16 am**

by **mf**

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
);
...
```

Posted: **Sun Mar 13, 2005 11:48 am**

by **Programmer**

Hello.

Can you give me output for these tests please.

Input

Thanks.

Posted: **Sun Mar 13, 2005 12:28 pm**

by **mf**

They're all "Not found."

And all cases where m = 6 and n != 3 (mod 7) and n != 5 (mod 7) seems to be "Not found" too.

Posted: **Sun Mar 13, 2005 5:24 pm**

by **Programmer**

Thanks Mf for reply.

Can you give me output for this tests.

Thanks.

Posted: **Sun Mar 13, 2005 8:02 pm**

by **Dreamer#1**

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

Posted: **Sun Mar 13, 2005 8:16 pm**

by **Dreamer#1**

by the way....

outputs for the inputs...

6 5

6 12

Posted: **Sun Mar 13, 2005 9:15 pm**

by **mf**

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.

Posted: **Mon Mar 14, 2005 9:41 pm**

by **Larry**

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!)

### hmm

Posted: **Tue Mar 15, 2005 1:51 am**

by **contest_clarificator**

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.

Posted: **Tue Mar 15, 2005 4:02 am**

by **filigabriel**

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.

Posted: **Mon Mar 21, 2005 8:53 am**

by **shamim**

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.

Posted: **Tue Mar 22, 2005 8:49 am**

by **filigabriel**

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.

### I/O plz

Posted: **Thu Apr 07, 2005 6:03 am**

by **Niaz**

Would you please give me some inputs and outputs.... !

Posted: **Mon Apr 11, 2005 3:06 am**

by **Antonio Ocampo**

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

Posted: **Mon Apr 11, 2005 12:21 pm**

by **mf**

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:

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."