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

Code: Select all

6 7
6 8
6 9
6 11
0 0
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.

Code: Select all

6 5
6 12
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

Code: Select all


Not Found.
1 8 6 10 3 5


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 :o , 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. :roll:

Posted: Tue Mar 22, 2005 8:49 am
by filigabriel
shamim wrote:I was trying my luck
Me too. At least, during online contest :D.

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

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