loading...

Daily Coding Challenge #86

wingkwong profile image Wing-Kam ใƒป3 min read

About

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!

GitHub logo wingkwong / leetcode

๐Ÿ† A Collection of my LeetCode Solutions with Explanations ๐Ÿ†

GitHub logo wingkwong / hackerrank

๐Ÿ† A Collection of my HackerRank Solutions with Explanations ๐Ÿ†

GitHub logo wingkwong / codeforces

๐Ÿ† A Collection of my Codeforces Solutions with Explanations ๐Ÿ†

GitHub logo wingkwong / atcoder

๐Ÿ† A Collection of my AtCoder Solutions with Explanations ๐Ÿ†

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

markdown guide