Equal Beauty CodeChef SnackDown 2021 Round 1A Question The beauty of an (non-empty) array of integers is defined as the difference between its largest and smallest element. For example, the beauty of the array [2,3,4,4,6] is 6−2=4. An array A is said to be good if it is possible to partition the elements of A into two non-empty arrays B1 and B2 such that B1 and B2 have the same beauty. Each element of array A should be in exactly one array: either in B1 or in B2. For example, the array [6,2,4,4,4] is good because its elements can be partitioned into two arrays B1=[6,4,4] and B2=[2,4], where both B1 and B2 have the same beauty (6−4=4−2=2). You are given an array A of length N. In one move you can: Select an index i (1≤i≤N) and either increase Ai by 1 or decrease Ai by 1. Find the minimum number of moves required to make the array A good. Input Format The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow. Each test
Snake Eating CodeChef SnackDown 2021 Beginner Practice Contest
Question
The Chef has acquired a vicious bunch of snakes, and these snakes are ever hungry and end up eating each other. In particular, each snake i has a length Li, whose initial value is given to you. A snake can eat any other snake which is not longer than itself. That is, snake i can eat snake j (i ≠ j), if Li ≥ Lj. And when a snake eats another snake, its length increases by 1. That is, Li increases by 1. A snake can eat multiple other snakes.
The Chef doesn't care about snakes eating each other. All he wants is to have as many snakes as possible, which are at least some particular lengths long. You are given Q values: K1, K2, .., KQ. Treat each of them independently and output the answer for each. That is, for each Ki, assume that you start out from the beginning with all the snakes alive and the lengths as the initial values given in the input, and find out the maximum number of snakes you can get whose length is at least Ki.
Input
- The first line contains an integer T, which is the number of testcases. The description of each testcase follows.
- The first line of each testcase contains two integers: N and Q, which denote the number of snakes initially, and the number of queries, respectively.
- The second line contains N space separated integers: L1, L2, .., LN, the initial lengths of the snakes.
- The i-th of the next Q lines contains a single integer, Ki.
Output
- For each testcase, output Q lines, the i-th of which should have a single integer: The maximum number of snakes the Chef can get which are of length at least Ki.
Constraints
- 1 ≤ T ≤ 5
- 1 ≤ N, Q ≤ 105
- 1 ≤ Li ≤ 109
- 1 ≤ Ki ≤ 109
Example Input
2
5 2
21 9 5 8 10
10
15
5 1
1 2 3 4 5
100
Example Output
3 1 0
Explanation
In the first testcase, first query, the second snake (length 9) can eat the fourth snake (length 8), and hence make its length 10. Now, there are four snakes left, and their lengths are {21, 10, 5, 10}. So, we have three snakes with length ≥ 10: Two snakes of length 10 and one snake of length 21. This is the best you can do.
In the second query, no matter what happens, you cannot get more than one snake of length ≥ 15.
In the second testcase, no matter what happens, you cannot get any snake of length ≥ 100. Hence the answer is 0.
Program Code in C++
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MX = 100005;
int a[MX], n;
ll sum[MX];
int cal(int x, int last)
{
if(last==0)
return 0;
int diff = a[n-1] - x;
int l = 0, r = last;
int ans = 0;
while(l<=r)
{
int mid = (l+r)/2;
if(mid==0)
{
l = mid+1;
continue;
}
ll need = (sum[last] - sum[mid-1]) - 1LL*diff*(last - mid + 1);
if(mid>=need)
{
ans = last-mid+1;
r = mid-1;
}
else l = mid+1;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t, q, x;
cin>>t;
while(t--)
{
cin>>n>>q;
for(int i = 0; i< n; i++)
{
cin>>a[i];
}
sort(a, a+n);
sum[0] = 0LL;
for(int i = 1; i< n; i++)
sum[i] = 1LL*sum[i-1] + 1LL*(a[n-1] - a[i]);
while(q--)
{
cin>>x;
int cnt = 0;
int idx = lower_bound(a, a+n, x) - a;
cnt=(n-idx);
cnt+=cal(x, idx-1);
cout << cnt << "\n";
}
}
return 0;
}
Important Links:
More information
CodeChef is one of the largest online coding platform and SnackDown is one of it's of grandest programs held ever year. SnackDown is a global programming event that invites programmers all over the world to participate in India's most prestigious multi-round programming competition. SnackDown is open to everyone who has a knack in programming.
This question that is Snake Eating is of CodeChef SnackDown 2021 Beginner Practice Contest. Here you will get a brief explanation of the problem and after reading the explanation if you are still stuck and have no clue to understand the problem then you can visit the solution of the question given above.
Hope you learnt something from this explanation and solution. Code it guys, practice coding more and more.
Comments
Post a Comment