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.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.
10571  Products
Moderator: Board moderators
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.

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 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?
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?

 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 NPcomplete.
And how will you solve 10419 and 10447? Only one way  backtracking!!!
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 NPcomplete.
And how will you solve 10419 and 10447? Only one way  backtracking!!!
Well of course I will use backtracking to solve NPcomplete 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?
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?

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
Why shouldn't there be backtracking problems requiring ingenious ideas? (Pruning can often be tricky, for example.)BiK wrote:Well of course I will use backtracking to solve NPcomplete problems. However, on a competition such as ACM ICPC I expect problems requiring some ingenius ideas instead of exhaustive search.

 Experienced poster
 Posts: 146
 Joined: Sat Apr 26, 2003 2:51 am
Re: 10571  Products
Dmytro Chernysh wrote
But got TLE for 10447
I finally got acc problem 10419 by using DP!!! with runtime 0.315.And how will you solve 10419 and 10447? Only one way  backtracking!!!
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
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