10825 - Anagram and Multiplication

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10825 - Anagram and Multiplication

Post by mf » Sun Mar 13, 2005 2:16 am

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

Post by Programmer » Sun Mar 13, 2005 11:48 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:

Post by mf » Sun Mar 13, 2005 12:28 pm

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
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am

Post by Programmer » Sun Mar 13, 2005 5:24 pm

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

Code: Select all

6 5
6 12
Thanks.

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Sun Mar 13, 2005 8:02 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 :)

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Sun Mar 13, 2005 8:16 pm

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

6 5
6 12

Code: Select all


Not Found.
1 8 6 10 3 5


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

Post by mf » Sun Mar 13, 2005 9:15 pm

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:

Post by Larry » Mon Mar 14, 2005 9:41 pm

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
Online Contest Administrator
Posts: 20
Joined: Fri Nov 30, 2001 2:00 am

hmm

Post by contest_clarificator » Tue Mar 15, 2005 1:51 am

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.

User avatar
filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:

Post by filigabriel » Tue Mar 15, 2005 4:02 am

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.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon Mar 21, 2005 8:53 am

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:

User avatar
filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:

Post by filigabriel » Tue Mar 22, 2005 8:49 am

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.

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

I/O plz

Post by Niaz » Thu Apr 07, 2005 6:03 am

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

Post by Antonio Ocampo » Mon Apr 11, 2005 3:06 am

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:

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

Post by mf » Mon Apr 11, 2005 12:21 pm

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

Post Reply

Return to “Volume 108 (10800-10899)”