Problem Statement

Dominoes is a game played with rectangular tiles. Each tile (domino) is split in half, and each half is painted with some color. It takes one second to repaint one half of a domino. Return the minimal time needed to make all the dominoes look the same (a domino can be rotated in no time, so a domino painted red and blue looks the same as a domino painted blue and red).

You will be given a String[] dominoes. Each element of dominoes will be formatted as "A1 B1 NUM1 A2 B2 NUM2 ... Ak Bk NUMk", where each triple (Ai, Bi, NUMi) represents NUMi dominoes painted with colors Ai and Bi, where Ai and Bi are each integers..

Definition

Class:              ColoredDominoes
Method:             optimalRepaintings
Parameters:         String[]
Returns:            int
Method signature:   int optimalRepaintings(String[] dominoes)
(be sure your method is public)

Constraints

• dominoes will contain between 1 and 50 elements, inclusive.
• Each element of dominoes will be formatted as "A1 B1 NUM1 A2 B2 NUM2 ... Ak Bk NUMk".
• Each element of dominoes will contain between 1 and 50 characters, inclusive.
• Each Ai and Bi will be integers, with no leading zeros, between 0 and 9999, inclusive.
• Each NUMi will be an integer, with no leading zeros, between 1 and 5000, inclusive.
• The sum of all NUMi will not be greater than 5000.

Examples

0)



{"0 0 2 1 2 2", "0 2 1", "1 1 1"}
Returns: 6
 
0 represents blue, 1 represents green, and 2 represents red. The best choice is to repaint every domino blue-red.
1)

{"0 0 1 0 0 1 1 1 1"}
Returns: 2

2)

{"1 2 1", "2 1 1"}
Returns: 0
Nothing to repaint.
3)

{"1 2 1", "2 3 1"}
Returns: 1

4)

{"1 2 2500", "3 4 2500"}
Returns: 5000

5)

{"1 2 1", "1 3 1", "1 4 1", "5 6 1", "7 6 1", "8 6 1"}
Returns: 6

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Google India Code Jam 2006 - Table of Contents

1. Main Page - Google India Code Jam 2006
2. Qualification Round
   • Set 1,10,13,16,25,28 :: Problem 250: ExamQuestions; Problem 1000: UnNestable
   • Set 2,9,15,20,21,27 :: Problem 250: GeneralElection; Problem 1000: UnNestable
   • Set 3,8,11,19,23,26 :: Problem 250: Sort01; Problem 1000: UnNestable
   • Set 4,7,14,18,22,29 :: Problem 250: PatternFiller; Problem 1000: PerfectNumbers
   • Set 5,6,12,17,24,30 :: Problem 250: TowerLifts; Problem 1000: PerfectNumbers
3. Elimination Round
   • Problem 250: MatrixConstructor
   • Problem 500: PalindromesAnalyzer
   • Problem 1000: VectorSet
4. Championship Round
   • Day 1, Take off to Bangalore, India (April 6, 2006)
   • Day 2, Code Jam Contest (April 7, 2006)
     • Breakfast and Google Tech Talk 1
     • The Contest Begins!!
       • Problem 300: InverseLca
       • Problem 500: ColoredDominoes
       • Problem 1000: InterestingString
     • Le Meridien and Google Tech Talk 2
     • Awards Winner announcements
     • Google Tech Talk 2 (continued) and dinner
   • Day 3, Interview with Google (April 8, 2006)
5. Links/Blogs/News