loading...

Daily Coding Challenge #103

wingkwong profile image Wing-Kam ・8 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.


/*
August Cook-Off 2020 Division 2
https://www.codechef.com/COOK121B/problems/CHEFNWRK
*/

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef pair<string, string> pss; 
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef vector<pii> vii; 
typedef vector<ll> vl; 
typedef vector<vl> vvl; 

double EPS=1e-9; 
int INF=1000000005; 
long long INFF=1000000000000000005ll; 
double PI=acos(-1); 
int dirx[8]={ -1, 0, 0, 1, -1, -1, 1, 1 }; 
int diry[8]={ 0, 1, -1, 0, -1, 1, -1, 1 }; 
const ll MOD = 1000000007;

#define DEBUG fprintf(stderr, "====TESTING====\n") 
#define VALUE(x) cerr << "The value of " << #x << " is " << x << endl 
#define OUT(x) cout << x << endl 
#define debug(...) fprintf(stderr, __VA_ARGS__) 
#define READ(x) for(auto &(z):x) cin >> z;
#define FOR(a, b, c) for (int(a)=(b); (a) < (c); ++(a)) 
#define FORN(a, b, c) for (int(a)=(b); (a) <= (c); ++(a)) 
#define FORD(a, b, c) for (int(a)=(b); (a) >= (c); --(a)) 
#define FORSQ(a, b, c) for (int(a)=(b); (a) * (a) <= (c); ++(a)) 
#define FORC(a, b, c) for (char(a)=(b); (a) <= (c); ++(a)) 
#define EACH(a, b) for (auto&(a) : (b)) 
#define REP(i, n) FOR(i, 0, n) 
#define REPN(i, n) FORN(i, 1, n) 
#define MAX(a, b) a=max(a, b) 
#define MIN(a, b) a=min(a, b) 
#define SQR(x) ((ll)(x) * (x)) 
#define RESET(a, b) memset(a, b, sizeof(a)) 
#define fi first 
#define se second 
#define mp make_pair 
#define pb push_back 
#define ALL(v) v.begin(), v.end() 
#define ALLA(arr, sz) arr, arr + sz 
#define SIZE(v) (int)v.size() 
#define SORT(v) sort(ALL(v)) 
#define REVERSE(v) reverse(ALL(v)) 
#define SORTA(arr, sz) sort(ALLA(arr, sz)) 
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz)) 
#define PERMUTE next_permutation 
#define TC(t) while (t--) 
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)


void solve() {
    int n, k;
    cin >> n >> k;
    vi w(n);
    READ(w);
    // if w[i]>k, Chef can't carry it
    // print -1 and return
    REP(i,n){
        if(w[i]>k) {
            OUT(-1);
            return;
        }
    }
    int ans=0,i=0;
    // greedy 
    while(i<n){
        int cur=0;
        ans++;
        while(i<n&&w[i]+cur<=k){
            cur+=w[i];
            i++;
        }
    }
    OUT(ans);
}

int main()  
{ 
    FAST_INP;
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r", stdin);
    freopen("output.txt","w", stdout);
    #endif

    int tc; cin >> tc;
    TC(tc) solve();

    return 0; 
} 

/*
August Cook-Off 2020 Division 2
https://www.codechef.com/COOK121B/problems/KFOLD
*/

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef pair<string, string> pss; 
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef vector<pii> vii; 
typedef vector<ll> vl; 
typedef vector<vl> vvl; 

double EPS=1e-9; 
int INF=1000000005; 
long long INFF=1000000000000000005ll; 
double PI=acos(-1); 
int dirx[8]={ -1, 0, 0, 1, -1, -1, 1, 1 }; 
int diry[8]={ 0, 1, -1, 0, -1, 1, -1, 1 }; 
const ll MOD = 1000000007;

#define DEBUG fprintf(stderr, "====TESTING====\n") 
#define VALUE(x) cerr << "The value of " << #x << " is " << x << endl 
#define OUT(x) cout << x << endl 
#define debug(...) fprintf(stderr, __VA_ARGS__) 
#define READ(x) for(auto &(z):x) cin >> z;
#define FOR(a, b, c) for (int(a)=(b); (a) < (c); ++(a)) 
#define FORN(a, b, c) for (int(a)=(b); (a) <= (c); ++(a)) 
#define FORD(a, b, c) for (int(a)=(b); (a) >= (c); --(a)) 
#define FORSQ(a, b, c) for (int(a)=(b); (a) * (a) <= (c); ++(a)) 
#define FORC(a, b, c) for (char(a)=(b); (a) <= (c); ++(a)) 
#define EACH(a, b) for (auto&(a) : (b)) 
#define REP(i, n) FOR(i, 0, n) 
#define REPN(i, n) FORN(i, 1, n) 
#define MAX(a, b) a=max(a, b) 
#define MIN(a, b) a=min(a, b) 
#define SQR(x) ((ll)(x) * (x)) 
#define RESET(a, b) memset(a, b, sizeof(a)) 
#define fi first 
#define se second 
#define mp make_pair 
#define pb push_back 
#define ALL(v) v.begin(), v.end() 
#define ALLA(arr, sz) arr, arr + sz 
#define SIZE(v) (int)v.size() 
#define SORT(v) sort(ALL(v)) 
#define REVERSE(v) reverse(ALL(v)) 
#define SORTA(arr, sz) sort(ALLA(arr, sz)) 
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz)) 
#define PERMUTE next_permutation 
#define TC(t) while (t--) 
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)


void solve() {
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    // just math
    int zero=0, one=0;
    EACH(c,s) {
        if(c=='0') zero++;
        else one++;
    }
    int seg = n/k;
    if(zero%seg||one%seg) {
        OUT("IMPOSSIBLE");
        return;
    }
    zero/=seg, one/=seg;
    FORN(i,1,seg){
        if(i&1){
            FORN(j,1,zero) cout << 0;
            FORN(j,1,one) cout << 1;
        }else{
            FORN(j,1,one) cout << 1;
            FORN(j,1,zero) cout << 0;
        }
    }
    OUT("");
}

int main()  
{ 
    FAST_INP;
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r", stdin);
    freopen("output.txt","w", stdout);
    #endif

    int tc; cin >> tc;
    TC(tc) solve();

    return 0; 
} 

/*
Thousand Separator

Given an integer n, add a dot (".") as the thousands separator and return it in string format.

Example 1:

Input: n = 987
Output: "987"
Example 2:

Input: n = 1234
Output: "1.234"
Example 3:

Input: n = 123456789
Output: "123.456.789"
Example 4:

Input: n = 0
Output: "0"


Constraints:

0 <= n < 2^31
*/

class Solution {
public:
    string thousandSeparator(int n) {
        string s = to_string(n), ans;
        int sz = s.size();
        for(int i=0;i<sz;i++){
            if(i&&(sz-i)%3==0) ans+='.';
            ans+=s[i];
        }
        return ans;
    }
};

class Solution2 {
public:
    string thousandSeparator(int n) {
        string s = to_string(n), ans;
        int cnt=0, sz=s.size();
        reverse(s.begin(),s.end());
        for(int i=0;i<sz;i++){
            if(cnt&&cnt%3==0) ans+='.';
            ans+=s[i], cnt++;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

/*
Minimum Number of Vertices to Reach All Nodes

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from node fromi to node toi.

Find the smallest set of vertices from which all nodes in the graph are reachable. It's guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
Output: [0,3]
Explanation: It's not possible to reach all the nodes from a single vertex. From 0 we can reach [0,1,2,5]. From 3 we can reach [3,4,2,5]. So we output [0,3].

Example 2:

Input: n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
Output: [0,2,3]
Explanation: Notice that vertices 0, 3 and 2 are not reachable from any other node, so we must include them. Also any of these vertices can reach nodes 1 and 4.


Constraints:

2 <= n <= 10^5
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi < n
All pairs (fromi, toi) are distinct.
*/

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        vector<int> ans, indegrees(n);
        // if indegree > 0, that means it is reachable 
        // so we just need to find those nodes with indegree = 0
        for(auto edge:edges) indegrees[edge[1]]++;
        for(int i=0;i<indegrees.size();i++) {
            if(indegrees[i]==0) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

/*
Minimum Numbers of Function Calls to Make Target Array


Your task is to form an integer array nums from an initial array of zeros arr that is the same size as nums.

Return the minimum number of function calls to make nums from arr.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: nums = [1,5]
Output: 5
Explanation: Increment by 1 (second element): [0, 0] to get [0, 1] (1 operation).
Double all the elements: [0, 1] -> [0, 2] -> [0, 4] (2 operations).
Increment by 1 (both elements)  [0, 4] -> [1, 4] -> [1, 5] (2 operations).
Total of operations: 1 + 2 + 2 = 5.
Example 2:

Input: nums = [2,2]
Output: 3
Explanation: Increment by 1 (both elements) [0, 0] -> [0, 1] -> [1, 1] (2 operations).
Double all the elements: [1, 1] -> [2, 2] (1 operation).
Total of operations: 2 + 1 = 3.
Example 3:

Input: nums = [4,2,5]
Output: 6
Explanation: (initial)[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5](nums).
Example 4:

Input: nums = [3,2,2,4]
Output: 7
Example 5:

Input: nums = [2,4,8,16]
Output: 8


Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
*/

class Solution {
public:
    int minOperations(vector<int>& nums) {
        // to think backwards instead
        // if the num is odd, decrement it by 1 (operation 0)
        // else divide it by 2 (operation 1)
        int op0=0,op1=0,highest=0;
        for(int num:nums){
            int bits=0;
            while(num>0){
                if(num&1) op0++;
                bits++;
                num>>=1;
            }
            // find the highest bit for op 1
            highest=max(highest,bits);
        }
        op1=highest-1;
        return op0+op1;
    }
};

/*
Detect Cycles in 2D Grid

Given a 2D array of characters grid of size m x n, you need to find if there exists any cyclic consisting of the same value in grid.

A cyclic is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it - in one of the four directions (up, down, left, or right), if it has the same value of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cyclic (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.

Return true if any cyclic of the same value exists in grid, otherwise, return false.


Example 1:


Input: grid=[["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
Output: true
Explanation: There are two valid cyclics shown in different colors in the image below:

Example 2:

Input: grid=[["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
Output: true
Explanation: There is only one valid cyclic highlighted in the image below:

Example 3:

Input: grid=[["a","b","b"],["b","z","b"],["b","b","a"]]
Output: false


Constraints:

m==grid.length
n==grid[i].length
1 <= m <= 500
1 <= n <= 500
grid consists only of lowercase English letters.
*/

class Solution {
public:
    bool containsCycle(vector<vector<char>>& grid) {
        int n=grid.size(), m=grid[0].size(), dirx[4]={-1,0,1,0}, diry[4]={0,1,0,-1}; 
        vector<vector<int>> visited(n,vector<int>(m,0)); 

        // check if the grid[x][y] is valid (i.e. in the bound)
        function<bool(int,int)> isValid = [&](int x, int y) {
            return (x<n&&x>=0&&y<m&&y>=0);
        };

        // check if it is cyclic
        function<bool(int,int,int,int)> dfs = [&](int x, int y, int fromX, int fromY) {
            // mark it visited
            visited[x][y]=1; 
            // check the next cells in four directions
            for(int k=0; k<4; k++) { 
                int toX=x+dirx[k], toY=y+diry[k]; 
                if (isValid(toX, toY)&&grid[toX][toY]==grid[x][y]&&!(fromX==toX&&fromY==toY)) { 
                    if (visited[toX][toY] || dfs(toX, toY, x, y)) return true; 
                } 
            } 
            return false; 
        };

        // dfs approach
        for(int i=0; i<n; i++) { 
            for(int j=0; j<m; j++) { 
                // if the current cell is not visited, 
                // then check if it is cyclic 
                if (!visited[i][j]&&dfs(i, j, -1, -1)){
                    return true;
                }
            } 
        } 
        return false;
    }
};

There are other programming solutions in the following repositories below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / hackerrank

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / codeforces

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / atcoder

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / cses

Migrated to https://github.com/wingkwong/competitive-programming

GitHub logo wingkwong / timus

Migrated to https://github.com/wingkwong/competitive-programming

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

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

Discussion

pic
Editor guide