10571 - Products

Algoritmo · Post by **Algoritmo** » Thu Oct 23, 2003 3:32 pm

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.

rbuchan · Post by **rbuchan** » Thu Oct 23, 2003 11:47 pm

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.

BiK · Post by **BiK** » Fri Oct 24, 2003 1:19 pm

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?

Dmytro Chernysh · Post by **Dmytro Chernysh** » Sun Oct 26, 2003 11:48 pm

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

BiK · Post by **BiK** » Wed Oct 29, 2003 12:13 am

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?

Dmytro Chernysh · Post by **Dmytro Chernysh** » Wed Oct 29, 2003 1:59 am

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

BiK · Post by **BiK** » Wed Oct 29, 2003 2:26 am

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?

Dmytro Chernysh · Post by **Dmytro Chernysh** » Wed Oct 29, 2003 2:37 am

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

Per · Post by **Per** » Wed Oct 29, 2003 8:19 am

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

Dmytro Chernysh · Post by **Dmytro Chernysh** » Wed Oct 29, 2003 2:07 pm

Exactly! Try to solve 10419 and 10447 without prunings

TLE for sure!!!

BiK · Post by **BiK** » Thu Nov 13, 2003 12:35 pm

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

lighted · Post by **lighted** » Mon Jul 07, 2014 8:24 pm

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

lighted · Post by **lighted** » Tue Jun 27, 2017 5:54 pm

Solved 10447 with DP in 0.820.

OJ Board

10571 - Products

Magic square?

Re: 10571 - Products

Re: 10571 - Products