Contest Link: https://www.codechef.com/CTON2020
JOHNY : Editorial
Author : CodeChef repository
Difficulty Level : Easy
Problem:
Vlad enjoys listening to music. He lives in Sam’s Town. A few days ago he had a birthday, so his parents gave him a gift: MP3-player! Vlad was the happiest man in the world! Now he can listen his favorite songs whenever he wants!
Vlad built up his own playlist. The playlist consists of N songs, each has a unique positive integer length. Vlad likes all the songs from his playlist, but there is a song, which he likes more than the others. It’s named “Uncle Johny”.
After creation of the playlist, Vlad decided to sort the songs in increasing order of their lengths. For example, if the lengths of the songs in playlist was {1, 3, 5, 2, 4} after sorting it becomes {1, 2, 3, 4, 5}. Before the sorting, “Uncle Johny” was on K-th position (1-indexing is assumed for the playlist) in the playlist.
Vlad needs your help! He gives you all the information of his playlist. Your task is to find the position of “Uncle Johny” in the sorted playlist.
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 one integer N denoting the number of songs in Vlad’s playlist. The second line contains N space-separated integers A1 , A2 , …, AN denoting the lenghts of Vlad’s songs. The third line contains the only integer K - the position of “Uncle Johny” in the initial playlist.
Output
For each test case, output a single line containing the position of “Uncle Johny” in the sorted playlist.
Constraints
1 ≤ T ≤ 10001 ≤ K ≤ N ≤ 1001 ≤ Ai ≤ 109
SOLUTION : CPP 14
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t,k,n,value;
cin>>t;
while(t - -)
{
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cin>>k;
value=a[k-1];
sort(a,a+n);
for(int j=0;j<n;j++)
{
if(a[j]==value)
{
cout<<j+1<<endl;
}
}
}
return 0;
}
SEAARASU : Editorial
Author : CodeChef Repository
Difficulty Level : Easy
PROBLEM :
Sereja has an array A of N positive integers : A[1], A[2], A[3], … , A[N].
In a single operation on the array, he performs the following two steps :
- Pick two indices i, j s.t. A[i] > A[j]
- A[i] -= A[j]
Sereja can apply these operations any number of times (possibly zero), such that the sum of resulting elements of the array is as small as possible.
Help Sereja find this minimum sum.
Input
First line of input contains an integer T - the number of test cases. T test cases follow.
First line of each test case contains the integer N. The next line contains N integers — A[1], A[2], A[3], … , A[N].
Output
For each test case, output a single line with the answer.
Constraints
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ A[i] ≤ 109
SOLUTION : CPP 14
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–)
{
long int n;
cin>>n;
long int arr[n];
for(int i=0; i<n; i++) {
cin >> arr[i];
}
long int ans=arr[0];
for(int i=1; i<n; i++) {
ans = __gcd(ans, arr[i]);
}
cout<<ans*n<<endl;
}
return 0;
}
MINSUBAR : Editorial
Author : CodeChef Repository
Difficulty Level : Easy
PROBLEM :
You are given a sequence of n integers a1, a2, …, an and an integer d.
Find the length of the shortest non-empty contiguous subsequence with sum of elements at least d. Formally, you should find the smallest positive integer k with the following property: there is an integer s (1 ≤ s ≤ N-k+1) such that as + as+1 + … + as+k-1 ≥ d.
Input
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers n and d.
- The second line contains n space-separated integers a1, a2, …, an.
Output
For each test case, print a single line containing one integer — the length of the shortest contiguous subsequence with sum of elements ≥ d. If there is no such subsequence, print -1 instead.
Constraints
- 1 ≤ T ≤ 105
- 1 ≤ n ≤ 105
- -109 ≤ d ≤ 109
- -104 ≤ ai ≤ 104
- 1 ≤ sum of n over all test cases ≤ 2 · 105
SOLUTION : CPP 14
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
long n;
long d;
cin>>n>>d;
long long arr[n+1], ans = LLONG_MAX, flag=0;
for(long long i=0; i<n; i++)
{
cin>>arr[i];
if(arr[i] >= d)
{
ans = 1;
flag = 1;
}
}
if(d <= 0)
{
if(!flag)
ans = -1;
}
else
{
if(!flag)
{
long long currsum = 0;
long long start = 0;
for(long long i=0; i<n;i++)
{
currsum = currsum + arr[i];
if(currsum > 0)
{
if(currsum >= d)
{
ans = min(ans, i-start+1);
//cout<<i<<" "<<start<<endl;
long long temp_start = start;
long long temp_sum = currsum;
while(start < i)
{
currsum = currsum - arr[start];
start++;
if(currsum >= d)
{
ans = min(ans,i-start+1);
temp_start = start;
temp_sum = currsum;
}
}
currsum = temp_sum;
start = temp_start;
}
}
else
{
currsum = 0;
start = i+1;
}
}
}
}
if(ans == LLONG_MAX)
ans = -1;
cout<<ans<<endl;
}
return 0;
}
TADELIVE : Editorial
Author : CodeChef Repository
Difficulty Level : Medium
PROBLEM :
Andy and Bob are the only two delivery men of Pizza-chef store. Today, the store received N orders. It’s known that the amount of tips may be different when handled by different delivery man. More specifically, if Andy takes the i th order, he would be tipped Ai dollars and if Bob takes this order, the tip would be Bi dollars.
They decided that they would distribute the orders among themselves to maximize the total tip money. One order will be handled by only one person. Also, due to time constraints Andy cannot take more than X orders and Bob cannot take more than Y orders. It is guaranteed that X + Y is greater than or equal to N, which means that all the orders can be handled by either Andy or Bob.
Please find out the maximum possible amount of total tip money after processing all the orders.
Input
- The first line contains three integers N, X, Y.
- The second line contains N integers. The i th integer represents Ai.
- The third line contains N integers. The i th integer represents Bi.
Output
- Print a single integer representing the maximum tip money they would receive.
Constraints
All test:
- 1 ≤ N ≤ 105
- 1 ≤ X, Y ≤ N; X + Y ≥ N
- 1 ≤ Ai, Bi ≤ 104
10 points:
- 1 ≤ N ≤ 20
30 points:
- 1 ≤ N ≤ 5000
60 points:
- 1 ≤ N ≤ 105
SOLUTION : CPP 14
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x,y,temp=0;
long long ans=0;
vector<pair<int,int>> dp;
cin>>n>>x>>y;
int a[n],b[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
dp.push_back({abs(a[i]-b[i]),i});
}
sort(dp.begin(),dp.end());
for(int i=n-1;i>=0;i–){
int ind = dp[i].second;
if(a[ind]>b[ind]){
if(x>0){
ans+=a[ind];
x–;
}else{
ans+=b[ind];
y–;
}
}else{
if(y>0){
ans+=b[ind];
y–;
}else{
ans+=a[ind];
x–;
}
}
}
cout<<ans<<endl;
return 0;
}
SUBLCM : Editorial
Author : CodeChef Repository
Difficulty Level : Medium
PROBLEM :
Given an array A1,A2…AN, you have to print the size of the largest contiguous subarray such that LCM of all integers in that subarray is equal to the product of all integers in that subarray.
Formally,
For a subarray Ai,Ai+1…Aj where 1 ≤ i < j ≤ N to be valid: LCM(Ai,Ai+1…Aj) should be equal to *AiAi+1…Aj. You have to print the size of the largest valid subarray.
If no subarray satisfies output -1.
**Note:**A single element is not considered a subarray according to definition in this problem.
Input
First line contains T, the number of testcases. Each testcase consists of N in one line followed by N integers in next line.
Output
For each testcase, print the required answer in one line.
Constraints
- 1 ≤ T ≤ 50
- 2 ≤ N ≤ 105
- 1 ≤ Ai ≤ 106
SOLUTION : CPP 14
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define ll long long
#define pii make_pair
#define pb push_back
#define ff first
#define ss second
int ceil(int a, int b) { if(a%b==0) return a/b; else return a/b+1; }
bool checkbit(int pos, int mask) { return mask&(1<<pos); }
int turnon(int pos, int mask) { return mask|(1<<pos); }
bool ar[1000005];
int tmp[1000005], cal[100005], inp[100005], dp[100005];
vectorfact[1000005], tf;
void sieve()
{
memset(ar, true, sizeof(ar));
for(int i=2; i<=1000005; i++) {
//cout<<i<<endl;
if(ar[i]) {
for(int j=i; j<=1000005; j+=i) {
fact[j].pb(i);
ar[j]=false;
}
}
}
}
void ccal(int n, int pos)
{
for(int i=0; i<fact[n].size(); i++) {
cal[pos]=max(cal[pos], tmp[fact[n][i]]);
tmp[fact[n][i]]=pos;
}
}
main()
{
fastio;
sieve();
int t, n;
cin>>t;
while(t–) {
int len=0, ans=0;
memset(cal, 0, sizeof(cal));
memset(tmp, 0, sizeof(tmp));
memset(dp, 0, sizeof(dp));
cin>>n;
for(int i=1; i<=n; i++) {
cin>>inp[i];
ccal(inp[i], i);
}
for(int i=1; i<=n; i++) {
dp[i]=min(dp[i-1]+1, i-cal[i]);
ans=max(ans, dp[i]);
}
if(ans==1) cout<<“-1”<<endl;
else cout<<ans<<endl;
}
}
ARRAYTRM : Editorial
Author : CodeChef Repository
Difficulty Level : Medium
PROBLEM :
Given n numbers, you can perform the following operation any number of times : Choose any subset of the numbers (possibly empty), none of which are 0. Decrement the numbers in the subset by 1, and increment the numbers not in the subset by K.
Is it possible to perform operations such that exactly n - 1 numbers become 0 ?
Input :
The first line contains the number of test cases T. 2*T lines follow, 2 for each case. The first line of a test case contains the numbers n and K. The next line contains n numbers, a_1…a_n.
Output :
Output T lines, one corresponding to each test case. For a test case, output “YES” if there is a sequence of operations as described, and “NO” otherwise.
Sample Input :
3
2 1
10 10
3 2
1 2 2
3 2
1 2 3
Sample Output :
YES
YES
NO
Constraints :
1 <= T <= 1000
2 <= n <= 100
1 <= K <= 10
0 <= a_i <= 1000
SOLUTION : CPP 14
#include
#include <bits/stdc++.h>
using namespace std;
int checkPoss(int arr[],int n, int k,int m){
int ans = 2;
for(int i=0;i<n && ans>=0;i++){
int temp = arr[i] + k*m;
if(temp % (k+1)!=0){
ans–;
}
}
return ans;
}
int main() {
int n,k;
int t;
cin>>t;
for (int j = 0; j < t; j++){
cin>>n>>k;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
if(n==2){
cout<<“YES”<<endl;
}
else{
int larg = std::max(arr[0],arr[1]);
int sec_larg = std::min(arr[0],arr[1]);
for(int i=2;i<n;i++){
if(arr[i]>=larg){
sec_larg = larg;
larg = arr[i];
}
else if(arr[i]>=sec_larg){
sec_larg = arr[i];
}
}
int success = checkPoss(arr,n,k,larg);
if(success >0){
cout<<“YES”<<endl;
continue;
}
success = checkPoss(arr,n,k,sec_larg);
if(success>0){
cout<<“YES”<<endl;
continue;
}
cout<<“NO”<<endl;
}
}
return 0;
}