Google Code Jam 2008 - Minimum Scalar Product

Recently, I was just trying to solve some problems from GCJ - 2008 and started off with a problem, which looked pretty easy. This problem is from the 'Round 1 A' and is called 'Minimum Scalar Product'. The problem statement is as below:

Problem
-------

You are given two vectors v1=(x1,x2,...,xn) and v2=(y1,y2,...,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+...+xnyn.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

Input
-----

The first line of the input file contains integer number T - the number of test cases. For each test case, the first line contains integer number n. The next two lines contain n integers each, giving the coordinates of v1 and v2 respectively.
Output

For each test case, output a line
Case #X: Y
where X is the test case number, starting from 1, and Y is the minimum scalar product of all permutations of the two given vectors.

Limits
------

Small dataset
-------------

T = 1000
1 ≤ n ≤ 8
-1000 ≤ xi, yi ≤ 1000

Large dataset
-------------

T = 10
100 ≤ n ≤ 800
-100000 ≤ xi, yi ≤ 100000

Sample Input
------------

2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

Output
------

Case #1: -25
Case #2: 6


The solution for the above problem is pretty easy, as all that you gotta do, is to multiply the largest/smallest element from X-Array to smallest/largest element in Y-Array. If you are using Java, it is probable that your solution might pass through, for small input file, but not for the large one. This is because the data in the larger input file, might cause an overflow of the 'int' value. So, care should be taken to use 'BigInteger' or 'BigDecimal', instead of primitive 'int'. Here's the bare bones Java code, for that problem:



After reading the input from the file, I pass the X-Array (v1) and Y-Array (v2), to the above method, get the result and write back to the output file. Thats it! :-)

1 comment:

  1. HOW I GOT MY LOAN (Lexieloancompany@yahoo.com)!!!

    My Name is Nicole Marie, I live in USA and life is worth living comfortably for me and my family now and i really have never seen goodness shown to me this much in my life, As i am a struggling mum with two kids and i have been going through a serious problem as my husband encountered a terrible accident last two weeks, and the doctors stated that he needs to undergo a delicate surgery for him to be able to walk again and i could not afford the bills for his surgery then i went to the bank for a loan and they turn me down stating that i have no credit card, from there i ran to my father and he was not able to help me, then when i was browsing through yahoo answers i came across a God fearing man (Mr Martinez Lexie) who provides loans at an affordable interest rate and i have been hearing about so many scams on the Internet mostly Africa, but at this my desperate situation, i had no choice than to give it an attempt due to the fact that the company is from United State of America, and surprisingly it was all like a dream, i received a loan of $82,000.00 USD and i payed for my husband surgery and thank GOD today he is ok and can walk, my family is happy and i said to myself that i will shout to the world the wonders this great and God fearing Man Mr Martinez Lexie did for me and my family; so if anyone is in genuine and serious need of a loan do contact this GOD fearing man via Email: ( Lexieloancompany@yahoo.com ) or through the Company website: http://lexieloans.bravesites.com OR text: +18168926958 thanks


    ReplyDelete

Note: Only a member of this blog may post a comment.