SWERC 2006 - The Right Tip

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

SWERC 2006 - The Right Tip

Post by mogers » Wed Apr 11, 2007 12:13 am

hi all

The Right Tip at NuevoPortal

i'm quite frustrated with this problem. I solved this problem in swerc 2006 (as contestant) but now i tried to solve it at 'nuevoportal' and i get WA.

This problem is easy, shouldn't be enough a greedy algorithm ?
I can't figure why i'm having WA[/url]
Miguel Oliveira

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sat Apr 14, 2007 10:34 am

Because the greedy algorithm is wrong in this case (not all coin values are divisible by the previous one).
Don't be mistaken, this problem is not so easy. What happens is that at SWERC, test data for this problem was very weak and almost everybody got accepted with the (incorrect) greedy algorithm.

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Post by mogers » Fri May 04, 2007 6:46 pm

it's been a long time since i wrote the post

i don't know if the test data was weak at swerc. in fact, at swerc i didn't use a greedy algorithm. I was confused
sorry,
Miguel Oliveira

Marius
New poster
Posts: 5
Joined: Thu Apr 10, 2008 5:55 pm

Re: SWERC 2006 - The Right Tip

Post by Marius » Mon Apr 14, 2008 8:54 pm

I can't figure out how to solve this problem. Could you give me some hints, please? Thank you in advance.

Post Reply

Return to “Algorithms”