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. :lol: :lol: :lol:
But got TLE for 10447 :x

Re: 10571 - Products

Posted: Tue Jun 27, 2017 5:54 pm
by lighted
Solved 10447 with DP in 0.820. :lol: