The Minimum Number Of Moves

The Minimum Number Of Moves

Little chief has his own restaurant in the city. There are N workers there. Each worker has his own salary. The salary of the i-th worker equals to W_i (i = 1, 2, ..., N). Once, chief decided to equalize all workers, that is, he wants to make salaries of all workers to be equal. But for this goal he can use only one operation: choose some worker and increase by 1 salary of each worker, except the salary of the chosen worker. In other words, the chosen worker is the loser, who will be the only worker, whose salary will be not increased during this particular operation. But loser-worker can be different for different operations, of course. Chief can use this operation as many times as he wants. But he is a busy man. That's why he wants to minimize the total number of operations needed to equalize all workers. Your task is to find this number.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the number of workers. The second line contains N space-separated integers W₁, W₂, ..., W_N denoting the salaries of the workers.

Output

For each test case, output a single line containing the minimum number of operations needed to equalize all workers.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100
• 0 ≤ W_i ≤ 10000 (10⁴)

Example

Input:
2
3
1 2 3
2
42 42

Output:
3
0

Explanation

Example Case 1. Chief can equalize all salaries in 3 turns:

Turn ID	IDs of involved workers	Salaries after the move
1	1 2	2 3 3
2	1 2	3 4 3
3	1 3	4 4 4

Problem Solving

1. This problem took me some time to grasp. Do not think otherwise but the issue here is that I did jump on solving the solution, however first I wanted to formally convince myself that a solution to this problem exists.
2. Turns out that no one on the editorial or discussion have answered this issue. How do I know that in any configuration of W there will exist a solution where are salaries will be equal after performing the mentioned operation multiple times. 
3. So to do that I thought of using induction, Clearly if f -> true when the solution to problem exists then f(1) is always true, because for 1 worker all salaries are already equal & number of operations are also = 0. 
4. Thinking about f(2), if there are only 2 workers and since this operation always increases the value therefore the min moves would be to make the salary of the lesser worker equal to the worker whose salary is more i.e (Max(W[])-Min(W[])) number of moves. and also that the solution does exists. 
5. So lets assume that f(k) -> true. with some X operations. 
6. If we can argue that f(k + 1)  is also true then we would conclusively prove that a solution to this problem exists for every k >0.
7. Now for f(k+1) out of k + 1 lets partition them in 2 groups of k say G1 and  1 say G2, such that the group G2 has only one element which is the max element of all k + 1 elements, 
8. Now the group G1 is solvable by induction hypothesis - (5) by X operations. 
9. That means that the after performing X operations in all k+1 elements where we always choose candidate for operation from group G1, the final value of G2 would be value of G2 elements + X. (since each operation will expand the G2 group by 1. 
10. Now the final configuration after X operations would be that all salaries in G1 group would be equal say equal to E and G2 group salary would be increased by X. 
11. Finally we can perform X - E operations by always selecting G2 candidate and so that G2 candidate never increases and the rest in  G1 which were equal already would all increase to be equal to G2. 
12. Therefore all salaries can be made equal. QED 
13. So I convinced myself that a problem can be solved. 
14. Now for the number of operations, also took sometime to ponder, If the only operation is increase all but one, that means that the minimum number of the set should dictate the number of operations. 
15. Doing sample examples would show that keeping max as the candidate and pulling up all the rest will yield the min number of operations. 
16. Now this is tricky to imagine but if you pull up your min to the successor on the min value, then we have a case just like in the proof, where we try to make all other equal and then finally we can just move all except for the one that is max. So we can try pulling up min to the next min in every iteration. 
17. This operation sequence will give us the min operations required. 
18. However instead of modelling this behavior, one can calculate how many operations does that mean. 
19. That means that in each iteration I make min equal to a next element therefore for every element this happens equal to the difference to the min value. 
20. Therefore E (0,n) (Wi - min(w)) is the answer. 

• For implementation 
• we can see that most variables are in int range and the summation would max to 10^4 * 100 = 10 ^ 6 which is also integer range. so no overflow requirements. 
• Next we see that we can find the summation and min elements in one scan of the input and the compute the answer so time can be O(1) and space also O(1).  
• No extra edge cases here. 
• The submission went successful here . 

Learning 

• Proof by induction was the best thing about this problem solving. The ability to convince oneself that yes there is a solution is great, also it provides insights to solve the actual problem.
• The problem can seem much easier if one thinks in a relative aspect. Since the only thing that matters is that all salaries become equal so the operation can also be thought of pushing one salary down each time instead of pulling all salaries except for one. In relative terms these are the same thing. 
• The relative aspect is great but to get the final salary, it becomes is difficult. 
• The final salary in the above approach is easy to think as min + number of total operations. (since in each operation the min have always increased, and the min was never a candidate to not increase the salary, the final = min + num of operations) 
• This problem was of cake walk difficulty, however it took me some time to ponder on the details. A lot of time compared to time requirements  of competitive programming. 
• This however should not sadden me, as my goal here is to learn and solve everything instead solve it fast. 
• Let's see what other problems have to offer. :)

Chef and Notebooks

Problem Statement 

The link to problem is here.  

Chef likes to write poetry. Today, he has decided to write a X pages long poetry, but unfortunately his notebook has only Y pages left in it. Thus he decided to buy a new CHEFMATE notebook and went to the stationary shop. Shopkeeper showed him some N notebooks, where the number of pages and price of the i^th one are P_i pages and C_i rubles respectively. Chef has spent some money preparing for Ksen's birthday, and then he has only K rubles left for now.

Chef wants to buy a single notebook such that the price of the notebook should not exceed his budget and he is able to complete his poetry.

Help Chef accomplishing this task. You just need to tell him whether he can buy such a notebook or not. Note that Chef can use all of the Y pages in the current notebook, and Chef can buy only one notebook because Chef doesn't want to use many notebooks.

Input

The first line of input contains an integer T, denoting the number of test cases. Then T test cases are follow.

The first line of each test case contains four space-separated integers X, Y, K and N, described in the statement. The i^th line of the next N lines contains two space-separated integers P_i and C_i, denoting the number of pages and price of the i^th notebook respectively.

Output

For each test case, Print "LuckyChef" if Chef can select such a notebook, otherwise print "UnluckyChef" (quotes for clarity).

Constraints and Subtasks

• 1 ≤ T ≤ 10⁵
• 1 ≤ Y < X ≤ 10³
• 1 ≤ K ≤ 10³
• 1 ≤ N ≤ 10⁵
• 1 ≤ P_i, C_i ≤ 10³

Subtask 1: 40 points

• Sum of N over all test cases in one test file does not exceed 10⁴.

Subtask 2: 60 points

• Sum of N over all test cases in one test file does not exceed 10⁶.

Sample

Input
3
3 1 2 2
3 4
2 2    
3 1 2 2
2 3
2 3    
3 1 2 2
1 1
1 2

Output
LuckyChef
UnluckyChef
UnluckyChef

Explanation

Example case 1. In this case, Chef wants to write X = 3 pages long poetry, but his notebook has only Y = 1 page. And his budget is K = 2 rubles, and there are N = 2 notebooks in the shop. The first notebook has P₁ = 3 pages, but Chef cannot buy it, because its price is C₁ = 4 rubles. The second notebook has P₂ = 2 pages, and its price is C₂ = 2 rubles. Thus Chef can select the second notebook to accomplish the task. He will write 1 page of poetry in the old notebook, and 2 page of poetry in the new notebook.

Example case 2. Chef cannot buy any notebook, because the prices exceed the Chef's budget.

Example case 3. No notebook contains sufficient number of pages required to write poetry.

Problem Solving

• The Chef's requirement Req= X - Y, no of pages required 
• Since X > Y is given no need to check this condition
•  The Solution is that out of all (P,C) if there exists a (P,C) such that P >= Req && C <=K then the chef can work else not, 
• Note we should not worry about finding the optimal solution since the objective is only to find one solution but not the best one. 
• Looking at limits of the inputs unsigned int is sufficient  
• The submission is successful, here

Learning

• This problem was not any different from the previous one. 
• The only smart thing to do was to reduce the comparison operation by using a bool once the answer was found. 
• Let's see if the next problem would be any different. 

Little Elephant and Candies 

Intro 

The link to the problem is here. 

Problem Statement 

A Little Elephant and his friends from the Zoo of Lviv like candies very much.

There are N elephants in the Zoo. The elephant with number K (1 ≤ K ≤ N) will be happy if he receives at least A_K candies. There are C candies in all in the Zoo.

The Zoo staff is interested in knowing whether it is possible to make all the N elephants happy by giving each elephant at least as many candies as he wants, that is, the K^th elephant should receive at least A_K candies. Each candy can be given to only one elephant. Print Yes if it is possible and No otherwise.

Input

The first line of the input file contains an integer T, the number of test cases. T test cases follow. Each test case consists of exactly 2 lines. The first line of each test case contains two space separated integers N and C, the total number of elephants and the total number of candies in the Zoo respectively. The second line contains N space separated integers A₁, A₂, ..., A_N.

Output

For each test case output exactly one line containing the string Yes if it possible to make all elephants happy and the string No otherwise. Output is case sensitive. So do not print YES or yes.

Constraints

1 ≤ T ≤ 1000

1 ≤ N ≤ 100

1 ≤ C ≤ 10⁹

1 ≤ A_K ≤ 10000, for K = 1, 2, ..., N

Example

Input:
2
2 3
1 1
3 7
4 2 2

Output:
Yes
No

Explanation

Case 1. We can give one candy to the first elephant and two candies to the second elephant and make them both happy. Hence the answer is Yes. Alternatively we can give one candy to each elephant and left one candy for ourselves but they again will be happy.

Case 2. Even if we give four candies to the first elephant and two candies to the second elephant we will have only one candy left and can not make last elephant happy since he needs two candies for his happiness. Hence the answer is No.

 Problem Solving

• Since each elephant will be happy only when it receives Ak candies therefore the total candies required is a sum of all Ak for (1<k<N) and this sum should be less than C. 
• From coding perspective all limits are trivial and if int is 4 bytes than all datatypes can be ints
• But we need to think about integer overflow , since all A can be max 1000 and there can be max of 1000(N) of them  therefore the summation cannot be more than 10^6 which can also be accommodated in an unsigned int, so extra care required. 
• Okay the submission went successful, here.

 Learning

• There are few learning from this submission
• First cin is slower than scanf which is slower than getchar which is slower than getchar_unlocked. Read about it here.  
• One would be tempted to early exit when required candies are more than the C at input is yet to be processed. However this is futile as you anyways have to read all the inputs otherwise that input will be used by next test case. 
• Also we avoided the use of array altogether by just summing up the numbers as they became available.

Arrays

Arrays 

Intro 

Array are the most fundamental data structure that can be used to store same type of data in a linear fashion. 

The data layout is not only linear in terms of traversal but contiguous in memory too. This being contiguous memory gives this data structure advantage since one can do pointer arithmetic to jump to any location on array in constant time. 

Usage 

• Store any type of data 
• Insert in O(1)
• Remove in O(1) 
• Access in O(1)

Pitfalls

• Cannot expand or decrease on fly. 

Note

• Since arrays are constant size, they are useful in situations where the size of data is already known at compile time.
• Values like alphabet size or constant range fit into this.

Array Implementation

• This simple implementation lets us create an array of any type T of constant size C.
• It provides access reference of T values so that we can read and update them as required.
• It also gives us option to print the whole array which is useful for demonstration purposes. 
• For every array each memory location is exactly size of type T and contiguous.
• It can be nested to form nested array structures. 
• Nested array structure should not be confused with a two dimensional arrays which can be created with int[4][5], this structure is very different in memory as compared to a nested array structure.
• The above point can be proved by printing the memory address of each element in nested structure
• Elements which belong to the same array are contiguous and size(T) distance.
• In the nested structure of nested_array the inner arrays i.e. the printed row memory address will be a constant of 4 bytes apart. since size(int) = 4; 
• The outer array in nested_array should have a each starting address of each row at a distance of sizeof(array<int,5>) distance apart i.e 24 bytes. However when I ran this it turns out that the outer array elements are 32 bytes distance apart and not 24 bytes. This is due to Memory Padding, read about it more here.
• In a two dimensional array only one malloc/new call is performed which gives a large chunk of memory = Sizeof(int) * 4 * 5 , the whole chunk is contiguous. 
• In a nested array structure there are multiple calls to malloc/new and therefore the total size of memory allocated remains the same but instead of one big chunk we get individual chunks of contiguous memory. 
• There was (prior to revision 11) a memory leak in the destructor call in nested structure, only the outer array is deleted not all elements inside the arrays.

 Next Steps

Now that we have a working array data structure, we shall move on in syllabus to solve the problems presented in the syllabus. If it is required to implement any algorithm then we shall first implement the algorithm and the follow on from there. 

Recurse Shall we ..?

After pondering over life for long time, I have finally created another blog. Over years I have tried and failed several times to start writing about my learning. I am not sure if this time would be any different. However, I will never know unless I try.

In this blog series I would like to cover the syllabus of Code Chef Certification on data structures and algorithms. I would like to go through each part of syllabus and get hands dirty by implementing each data structure and algorithm on the way. I would like to do this in C++ as it's the language that my thinking most resonates with. I would have tried out python as well but I know picking up multiple tasks is not a good recipe for starting out.

The syllabus also covers the asymptotic analysis of these structures and algorithms which instead of creating a separate section, I would like to do with every data structure /algorithm / problem I solve.

I would post all code on github repo, so anyone who come across this blog can find reference to the code