10571 - Products

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

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
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

Magic square?

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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

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

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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

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

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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

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

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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

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

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

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10571 - Products

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

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

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

Post Reply

Return to “Volume 105 (10500-10599)”

Who is online

Users browsing this forum: No registered users and 1 guest