10825 - Anagram and Multiplication

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

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

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

[Programmer]

Thanks Mf for reply.
Can you give me output for this tests.

Code: Select all

6 5
6 12

Thanks.

[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

[Dreamer#1]

by the way....
outputs for the inputs...

6 5
6 12

Code: Select all

Not Found.
1 8 6 10 3 5

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

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

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

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

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

[filigabriel]

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]

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

[Antonio Ocampo]

Hi fellows. What's the meaning of

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]

Hi fellows. What's the meaning of

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