## 10571 - Products

Moderator: Board moderators

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:
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
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

### Magic square?

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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
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:

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
Exactly! Try to solve 10419 and 10447 without prunings TLE for sure!!!

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10571 - Products

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
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10571 - Products

Solved 10447 with DP in 0.820.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

### Who is online

Users browsing this forum: No registered users and 1 guest