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

Posted: **Thu Oct 23, 2003 3:32 pm**

by **Algoritmo**

Per wrote:(Assuming you've solved the problem by exhaustive search)

Why would that be so much harder?

Your branching factor would increase by a factor two, which shouldn't be critical for this problem. Otherwise there should just be some minor implementation details.

The difficult thing would not to implement a program that can give solutions with negative numbers. The difficult part would be to realize in a contest that negative numbers were also possible.

### Magic square?

Posted: **Thu Oct 23, 2003 11:47 pm**

by **rbuchan**

Isn't this problem somewhat related to the magic multiplication square? I was looking for a pattern to the placements of the numbers, but haven't come up with anything so far. Another method I was thinking of is the divisors of each of the words flagged in an array and then try to do a comparison that way...not sure if time will allow.

Posted: **Fri Oct 24, 2003 1:19 pm**

by **BiK**

**Dmytro_Chernysh wrote:**
But the problem is super -- no one managed to solve on the original contest in St. Petersburg

Indeed the problem is extreemly dificult for me. Could somebody explain how this problem can be solved?

Posted: **Sun Oct 26, 2003 11:48 pm**

by **Dmytro Chernysh**

The official (author's) solution is by backtracking.

However, I've read that somebody suggested to solve it by "magic multiplication square". You know ... maybe

Posted: **Wed Oct 29, 2003 12:13 am**

by **BiK**

Backtracking on the dividers of the numbers written besides the columns and rows. Is this what you mean?

I was disappointed when I read that the problem should be solved with backtracking. I thought that backtracking has died out as a method for solving ACM ICPC problems.

2rbuchan:

What is your idea about the magic squares?

Posted: **Wed Oct 29, 2003 1:59 am**

by **Dmytro Chernysh**

>>I thought that backtracking has died out as a method for solving ACM >>ICPC problems.

Hmm.. Hmm.. Did you really mean that backtracking died? Well, than how are you going to solve for example 10068? There is no way to solve this problem exept for backtracking since the problem is NP-complete.

And how will you solve 10419 and 10447? Only one way -- backtracking!!!

Posted: **Wed Oct 29, 2003 2:26 am**

by **BiK**

Well of course I will use backtracking to solve NP-complete problems. However, on a competition such as ACM ICPC I expect problems requiring some ingenius ideas instead of exhaustive search.

Anyway, you haven't answer my basic question. The backtracking should be on the dividers of the numbers written besides the columns and rows. Is this true?

Posted: **Wed Oct 29, 2003 2:37 am**

by **Dmytro Chernysh**

Yep, of course with some prunings, but basically you are right

As you can see, it's quite easy to beat author's solution -- many people got time like 0:00.010

Posted: **Wed Oct 29, 2003 8:19 am**

by **Per**

BiK wrote:Well of course I will use backtracking to solve NP-complete problems. However, on a competition such as ACM ICPC I expect problems requiring some ingenius ideas instead of exhaustive search.

Why shouldn't there be backtracking problems requiring ingenious ideas? (Pruning can often be tricky, for example.)

Posted: **Wed Oct 29, 2003 2:07 pm**

by **Dmytro Chernysh**

Exactly! Try to solve 10419 and 10447 without prunings

TLE for sure!!!

Posted: **Thu Nov 13, 2003 12:35 pm**

by **BiK**

Ok. I tried some problems requiring backtracking and now I changed my opinion. Backtracking is a usefull technique almost always requiring ingenious pruning.

Best regards

### Re: 10571 - Products

Posted: **Mon Jul 07, 2014 8:24 pm**

by **lighted**

Dmytro Chernysh wrote

And how will you solve 10419 and 10447? Only one way -- backtracking!!!

I finally got acc problem 10419 by using DP!!! with runtime 0.315.

But got TLE for 10447

### Re: 10571 - Products

Posted: **Tue Jun 27, 2017 5:54 pm**

by **lighted**

Solved 10447 with DP in 0.820.