HackerRank: Equal


HackerRank: Equal
Christy is interning at HackerRank. One day she has to distribute some chocolates to her colleagues. She is biased towards her friends and may have distributed the chocolates unequally. One of the program managers gets to know this and orders Christy to make sure everyone gets equal number of chocolates.

But to make things difficult for the intern, she is ordered to equalize the number of chocolates for every colleague in the following manner,

For every operation, she can choose one of her colleagues and can do one of the three things.
(i) She can give one chocolate to every colleague other than chosen one.
(ii) She can give two chocolates to every colleague other than chosen one.
(iii) She can give five chocolates to every colleague other than chosen one.

Calculate minimum number of such operations needed to ensure that every colleague has the same number of chocolates.

Christy has to equalize the number of chocolates for all the coworkers. The only action she can make at every operation is to increase the count of every others' chocolate by 1,2 or 5 except one of them. This is equivalent to saying, christy can take away the chocolates of one coworker by 1, 2 or 5 while keeping others' chocolate untouched.
Let's consider decreasing a coworker's chocolate as an operation. To minimize the number of operations, we should try to make the number of chocolates of every coworker equal to the minimum one in the group(min). We have to decrease the number of chocolates the ith person A[i] by (A[i] - min). Let this value be x. For this you may consider Coin change algorithms.
we now follow a greedy algorithm so number of operations required is minimum. This can be done in k operations.
k = x/5 +(x%5)/2 + (x%5)%2 
Let f(min) be sum of operations performed over all coworkers to reduce each of their chocolates to min.
However, sometimes f(min) might not always give the correct answer. It can also be a case when
f(min) > f(min-1)
but it is safe to assume that
f(min) < f(min-5)
as f(min-5) takes N operations more than f(min) where N is the number of coworkers.
Therefore, if
A = {min,min-1,min-2,min-3,min-4} 
then,
f(A) <= f(min) < f(min-5)
Compute f(y) ∀ y ∈ A and print the minimum as the answer.

long long int functn (long long int temp)  // similar to greedy Coin-change
{
    long long int x=0;
    if(temp>=5)
    {
        x = temp/5;
        temp = temp%5;
    }
    if(temp>=2)
    {
        x += temp/2;
        temp = temp%2;
    }
    x += temp;
    return x;

}

int array_smallest(long long int array[],int array_length)
{
    long long int smallest = INT_MAX;
    long long int i;
    for (i = 0; i < array_length; i++)
    {
        if (array[i] < smallest) {
            smallest = array[i];
        }
    }
    return smallest;
}

long long int mod(long long int x)
{
    if(x>0)
        return x;
    else
        return (-1)*x;
}

int main()
{
    long long int T,N,i,j,min,sum,temp;
    cin>>T;
    while(T--)
    {
        min = 1000000;
        cin>>N;
        int A[N];
        for(i=0 ; i< N ; i++)
        {
            cin>>A[i];
            if(A[i]<min)
                min = A[i];
        }
        long long int sum[6];
        for(j=0 ; j<=5 ; j++)
        {
            sum[j]=0;
            for(i=0 ; i< N ; i++)
            {
                temp = mod(A[i] - (min-j));
                sum[j] = sum[j] + functn(temp);
            }
        }
        cout<<array_smallest(sum,6)<<endl;
    }
    return 0;
}
https://www.nowtoshare.com/zh/Article/Index/70569
public static int minToEqual(int[] chocolates){ int [] options = new int[]{1,2,5}; int step =Integer.MAX_VALUE; int min=Integer.MAX_VALUE; for(int i=0; i<chocolates.length;i++){ min =Math.min(min, chocolates[i]); } HashMap<Integer, Integer> memo = new HashMap<>(); for(int realMin=Math.max(0,min-4); realMin<=min;realMin++){ int step_cur =0; for(int i=0; i<chocolates.length;i++){ step_cur+=minStep(chocolates[i]-realMin,options, memo); } step =Math.min(step_cur,step); } return step; } public static int minStep(int offset, int[] options, HashMap<Integer, Integer> memo){ if(offset==0) return 0; if(memo.containsKey(offset)) return memo.get(offset); int step =Integer.MAX_VALUE; for(int option : options){ if(offset >=option) step = Math.min(step, minStep(offset-option,options,memo)+1); } memo.put(offset, step); return step; } public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner scan = new Scanner(System.in); int cases = scan.nextInt(); for(int i=0;i<cases; i++){ int colleaguesNum = scan.nextInt(); int[] chocolates = new int[colleaguesNum]; for(int k=0;k<colleaguesNum;k++){ chocolates[k] = scan.nextInt(); } System.out.println(minToEqual(chocolates)); } }

http://blog.csdn.net/junchen1992/article/details/52228803
逆向思维:(1)题目问的是让我们“加”巧克力使得每个人最终巧克力数量一样。这等价于“减”巧克力使得每个人最终巧克力数量一样。(2)用“减”的方法,最终的目标是使得每个人的巧克力数量为原输入数组的最小值或者任意小于该值但不为负。
除某个数之外都增加,可以等效成只有一个数减少。
那么直观来看,最少的应该是所有的数都减到最小的数,记这个和为f(min)
但是因为每次可以-1,可以-2,可以-5。所以这时并不一定是都减到最小的数合适。
比如1 5 10,如果减到1,需要9/5+4/2=3 4/2=2 3+2=5 而如果都减到0,就是5/5=1 10/5=2 1+2+1=4
所以,不能简单的算f(min)。但是注意到f(min-5)是肯定小于f(min)的在往小了肯定是大于f(min)的,所以我们至多只要算导f(min-5)
那么就是o(n)辣
        for(int i = 0; i < n; ++i) {
            scanf("%d", a+i);
            minn = min(minn, a[i]);
        }
        int ans = 100000000;
        for(int i = -5; i <= 0; ++i) {
            int this_ans = 0;
            for(int j = 0, delta; j < n; ++j) {
                delta = a[j] - i - minn;
                this_ans += delta/5 + delta%5/2 + delta%5%2;
            }
            ans = min(this_ans, ans);
        }
        printf("%d\n", ans);
    }

int minVal = A[0];
for(int i = 1; i < N; ++i){
    if (A[i] < minVal){
        minVal = A[i];
    }
}

int minCount = Integer.MAX_VALUE;
for(int i = 0; i <= 5; ++i){
    int count = 0;
    for(short j = 0; j < N; ++j){
        short V = (short)(A[j] - (minVal - i));
        count += V/5 + (V %= 5)/2 + (V & 1);
    }
    if (count < minCount){
        minCount = count;
    }
}

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