Problem B. Dancing With the Googlers - Qualification Round 2012 - Google Code Jam


Dashboard - Qualification Round 2012 - Google Code Jam
You're watching a show where Googlers (employees of Google) dance, and then each dancer is given a triplet of scores by three judges. Each triplet of scores consists of three integer scores from 0 to 10 inclusive. The judges have very similar standards, so it's surprising if a triplet of scores contains two scores that are 2 apart. No triplet of scores contains scores that are more than 2 apart.
For example: (8, 8, 8) and (7, 8, 7) are not surprising. (6, 7, 8) and (6, 8, 8) are surprising. (7, 6, 9) will never happen.

The total points for a Googler is the sum of the three scores in that Googler's triplet of scores. The best result for a Googler is the maximum of the three scores in that Googler's triplet of scores. Given the total points for each Googler, as well as the number of surprising triplets of scores, what is the maximum number of Googlers that could have had a best result of at least p?
10 9 10
6 6 8 (*)
2 3 3
6 6 6
6 6 6
6 7 8 (*)
For example, suppose there were 6 Googlers, and they had the following total points: 29, 20, 8, 18, 18, 21. You remember that there were 2 surprising triplets of scores, and you want to know how many Googlers could have gotten a best result of 8 or better.
With those total points, and knowing that two of the triplets were surprising, the triplets of scores could have been:
10 9 10  6 6 8 (*)  2 3 3  6 6 6  6 6 6  6 7 8 (*)  
The cases marked with a (*) are the surprising cases. This gives us 3 Googlers who got at least one score of 8 or better. There's no series of triplets of scores that would give us a higher number than 3, so the answer is 3.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing integers separated by single spaces. The first integer will be N, the number of Googlers, and the second integer will be S, the number of surprising triplets of scores. The third integer will be p, as described above. Next will be N integers ti: the total points of the Googlers.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the maximum number of Googlers who could have had a best result of greater than or equal to p.

Limits

1 ≤ T ≤ 100.
0 ≤ S ≤ N.
0 ≤ p ≤ 10.
0 ≤ ti ≤ 30.
At least S of the ti values will be between 2 and 28, inclusive.

Small dataset

1 ≤ N ≤ 3.

Large dataset

1 ≤ N ≤ 100.

4
3 1 5 15 13 11
3 0 8 23 22 21
2 1 1 8 0
6 2 8 29 20 8 18 18 21


Case #1: 3
Case #2: 2
Case #3: 1
Case #4: 3

http://samfoust.com/Blog/Post/problem-b-dancing-with-the-googlers

            for (int i = 0; i < count; i++// For every dance score set
            {
                var DanceScoreSet = Inputs[i].Split(' ').ToList();
                NumberOfDancers = int.Parse(DanceScoreSet[0]);
                SuprisingTriplets = int.Parse(DanceScoreSet[1]);
                TargetScore = int.Parse(DanceScoreSet[2]);
                DanceScoreSet.RemoveRange(03);
                //We now have all the information, and SanceScoreSet is left with the list of scores from each dancer.

                //Number of dancers that we say are at or above target score, including surprising triples.
                SuccessCount = 0;

                foreach (var dancescore in DanceScoreSet)
                {
                    //If it is normal and not a surprising triple
                    if (IsNormal(int.Parse(dancescore),TargetScore))
                    {
                        SuccessCount++;
                        continue;
                    }

                    // If score was not normal but is a surprising triple and we still have a few suppressing triples left to score
                    else if (IsSupprising(int.Parse(dancescore), TargetScore) &&SuprisingTriplets > 0)
                    {
                        SuccessCount++;
                        SuprisingTriplets--;
                    }
                }
                //Output our result, in specified format for scoring.
                Console.WriteLine("Case #"+(i+1)+": " + SuccessCount);
            }
            //Stall console app so we can see the output.
            Console.ReadLine();
        }

        //If the score differs no more than 4 total it isn't surprising Ex 9,7,7 is the max a normal can be and its only 4 off of 9,9,9 considering target is 9
        private static bool IsSupprising(int DancerScore, int TargetScore)
        {
            if (DancerScore < TargetScore)
                return false;
            return (DancerScore -  (TargetScore * 3)) >= -4;
        }

        //If the score differs no more than 2 total it isn't surprising Ex 9,8,8 is the max a normal can be and its only 2 off of 9,9,9 considering target is 9
        private static bool IsNormal(int DancerScore, int TargetScore)
        {
            if (DancerScore < TargetScore)
                return false;
            return (DancerScore - (TargetScore * 3)) >= -2;

        }

X. http://united-coders.com/christian-harms/solutions-for-the-google-code-jam-2012-qualify-round/
How to identify the highest values of a “not surprising” and “surprising” triple? Simply remember the MODULO operator.
def maxNotSurprising(n):
    b = n / 3
    #1: 0+0+1
    #2: 0+1+1
    if n%3>0:
        return b+1
    #0+0+0
    return b
def maxSurprising(n):
    b = n / 3
    #2: 0+0+2
    if n%3==2:
        return b+2
    #1: 0+1+0
    if n%3==1:
        return b+1
    #3: 0+1+2
    if n%3==0 and n>0:
        return b+1
    #0: 0+0+0
    return b
And the result script has to check if there are surprising triples left and count the p-hits.
import sys
input = file(sys.argv[1])
def solve(s, p, ti):
    c = 0
    for t in ti:
        maxNot = maxNotSurprising(t)
        maxSur = maxSurprising(t)
        if s>0 and maxSur>maxNot and maxSur>=p and maxNot= p: // the order should be swithced
                c+=1
                s-=1
        else:
            if maxNot>=p:
                c+=1
    return c
for case in range(int(input.readline())):
    values = [int(x) for x in input.readline().split()]
    print "Case #%d: %d" % (case+1, solve(values[1], values[2], values[3:]))
Scala: http://techrant.tegla.net/2012/06/google-code-jam-in-scala-dancing-with.html
import scala.math.{min,max}
def solve(s:Int,p:Int,ts:List[Int]):Int = {
  val normal_limit = p + max(0, p-1) + max(0, p-1)
  val suprising_limit = p + max(0, p-2) + max(0, p-2)
  val normals = ts.count(_>=normal_limit)
  val suprisings = ts.count(t=> t>=suprising_limit && t<normal_limit)
   
  return min(s,suprisings) + normals
}

http://google-tale.blogspot.com/2012/04/gcj-2012-dancing-with-googlers.html

public int findMaxGooglers(int N, int s, int p, ArrayList<Integer> scoreList) { int res = 0;
int surpriseNum = s;
int threshold = p + (2 * (p - 2));
Collections.sort(scoreList); // any special reason to sort? no need to sort.
for(Integer score: scoreList) {
if(score >= p) {
System.out.print("Score : " + score + " divided into : ");
int[] triplet = split(score);
if(triplet[2] >= p) {
res++;
} else if(surpriseNum > 0 && score >= threshold) {
res++;
surpriseNum--;
}
}
}
return res;
}
private int[] split(int score) {
int div = score/3;
int rem = score - (3 * div);
int[] triplet = new int[3];
triplet[0] = div;
triplet[1] = div;
triplet[2] = div;
//System.out.println("Div : " + div + " Init Rem : " + rem);
int index = 0;
while(rem > 0) {
if(index > 2) {
index = 0;
}
triplet[index] += 1;
index++;
rem--;
}
Arrays.sort(triplet);
System.out.println(triplet[0] + " - " + triplet[1] + " - " + triplet[2]);
return triplet;
}
Read full article from Dashboard - Qualification Round 2012 - Google Code Jam

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts