GCJ 2008 – Round 1A: Minimum Scalar Product

August 5th, 2008 § 3 comments

This one was really really really too simple. The easiest problem of round 1. Unfortunately I didn’t took part at 1A, I did 1B and 1C and I did not pass :^( Anyway I’ll keep doing those problem just to have some fun :^)

def solve(a,b):
    a.sort()
    b.sort(reverse = True)
    return sum([i[0]*i[1] for i in zip(a,b)])

You have to pass a and b as lists, or if you prefer vectors… I think there is no more to comment here… I did it just thinking about it and I find the solution out in about 3 minutes, but I discovered that mathematicians already thought about that and gave it a name :^D

You can search on wikipedia for Rearrangement inequality. I mean, 4 lines of fully readable python… it was quite simple, wasn’t it?

return YAWN;

Tagged , ,

§ 3 Responses to GCJ 2008 – Round 1A: Minimum Scalar Product"

  • Toé says:

    Here is a part of my code:

    v1.sort()
    v2.sort(reverse=True)
    scalar = 0
    j = 0
    while j < n:
         scalar += int(v1[j]) * int(v2[j])
          j += 1

    I think it’s just but when I submit the output file, they say it’s incorrect

  • Andrea says:

    Try to convert to int before sorting, so far it seems correct to me. Are you sure you’re not messin up with the output? There are some strict rules about that.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>