Daily Coding Challenge #86

Wing-Kam ・3 min read

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

/*
Codeforces Round #661 (Div. 3) - A. Remove Smallest
https://codeforces.com/contest/1399/problem/A
*/

#include <bits/stdc++.h>
using namespace std;
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)
typedef long long ll;
const ll MOD = 1000000007;

int main()
{
FAST_INP;
// if |ai-aj|=1 cannot be fulfilled, then the ans is NO
// hence, sort the input and check if a[i]-a[i-1]>1
// if so, print NO
// else, print YES
int t,n;
cin >> t;
while(t--){
cin >> n;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
sort(a.begin(),a.end());
int ok=1;
for(int i=1;i<n;i++){
if(a[i]-a[i-1]>1) {
ok=0;
break;
}
}
if(ok) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}


/*
Codeforces Round #661 (Div. 3) - B. Gifts Fixing
https://codeforces.com/contest/1399/problem/B
*/

#include <bits/stdc++.h>
using namespace std;
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)
typedef long long ll;
const ll MOD = 1000000007;

int main()
{
FAST_INP;
int t,n;
cin >> t;
while(t--){
cin >> n;
vector<int> a(n),b(n);
int min_a=1e9+5,min_b=1e9+5;
// read candy n find the min number of candy
for(int i=0;i<n;i++) {
cin >> a[i];
min_a=min(min_a,a[i]);
}
// read orange  n find the min number of orange
for(int i=0;i<n;i++) {
cin >> b[i];
min_b=min(min_b,b[i]);
}
ll ans=0;
for(int i=0;i<n;i++){
// calculate how many operations we need for each gift
// if we take the max from a and b, the other one must be also covered
ans+=max(a[i]-min_a, b[i]-min_b);
// the logic can be also implemented as below
/*
if(a[i]==min_a&&b[i]==min_b) continue;
else if(a[i]==min_a&&b[i]>min_b) ans+=b[i]-min_b;
else if(b[i]==min_b&&a[i]>min_a) ans+=a[i]-min_a;
else if(a[i]>min_a&&b[i]>min_b){
if(a[i]-min_a < b[i]-min_b) {
ans+=a[i]-min_a;
ans+=b[i]-min_b-(a[i]-min_a);
} else {
ans+=b[i]-min_b;
ans+=a[i]-min_a-(b[i]-min_b);
}
}
*/
}
cout << ans << endl;
}
return 0;
}


/*
Codeforces Round #661 (Div. 3) - C. Boats Competition
https://codeforces.com/contest/1399/problem/C
*/

#include <bits/stdc++.h>
using namespace std;
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)
typedef long long ll;
const ll MOD = 1000000007;

// WA
//int solve(vector<int>& a, int n){
//  unordered_map<int,int> m;
//  int max_cnt=0;
//  for(int i=0;i<n-1;i++){
//      for(int j=i+1;j<n;j++){
//          m[a[i]+a[j]]++;
//          max_cnt=max(m[a[i]+a[j]],max_cnt);
//      }
//  }
//  int sum=0;
//  vector<int> q;
//  for(auto x:m){
//      if(max_cnt==x.second){
//          sum=x.first;
//          q.emplace_back(x.first);
//      }
//      printf("%d %d\n", x.first, x.second);
//  }
//  int ans=0;
//  for(auto k: q){
//      vector<int> v(n,0);
//      int cnt=0;
//      for(int i=0;i<n-1;i++){
//          if(v[i]) continue;
//          for(int j=i+1;j<n;j++){
//              if(!v[j]&&(a[i]+a[j]==k)){
//                  cnt++;
//                  v[j]=1;
//                  break;
//              }
//          }
//      }
//      ans=max(ans,cnt);
//  }
//  return ans;
//}

int solve(vector<int>& a, int n){
int ans=0;
// let i be the total weight
for(int i=2;i<=n*2;i++){
vector<int> c(n*2,0);
int cnt=0;
for(int k:a){
// if the total weight > current weight
// and a pair can be made
if(i>k&&c[i-k]){
c[i-k]--;
cnt++;
}else{
// increase c[k] by 1 to wait for the pair
c[k]++;
}
}
ans=max(ans,cnt);
}
return ans;
}

int main()
{
FAST_INP;
int t,n;
cin >> t;
while(t--){
cin >> n;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
cout << solve(a,n) << endl;
}
return 0;
}


The source code is available in corresponding repo below. Star and watch for timely updates!

wingkwong / atcoder

Posted on by:

Wing-Kam

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.