Array and simple queries

Problem link: Array and simple queries

Topic Name: Treaps

Code:

Share:

Read More

Cut the sticks

Problem link: Cut the sticks

Share:

Read More

Is Fibo

Is Fibo

Topic: Fibonacci

Share:

Read More

Counting Inversions

Merge Sort: Counting Inversions

Concept:

 Count Inversions in an array

Implementation:

Share:

Read More

Video Conference

Video Conference

Topic: trie

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

vector<string> solve (vector<string> names) { unordered_set<string> s; unordered_map<string, int> mp; vector<string>ans; for(const auto& name: names){ auto it = mp.find(name); if(it != mp.end()){ it->second++; ans.push_back(name + ' ' + to_string (it->second)); } else{ mp[name] = 1; string t; bool inserted = false; for(auto c : name){ t += c; auto p = s.insert(t); if(!inserted && p.second){ inserted = true; ans.push_back(t); } } if(!inserted) ans.push_back(t); } } return ans; }

Another Solution

Share:

Read More

Merging Communities

Merging Communities

Topic: DSU

Solution 01:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include <bits/stdc++.h> using namespace std; #define INF 1<<30 #define MAX 100005 #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); int parent[MAX*2], Rank[MAX]; void Initialization(int n) { for(int i = 0; i <= n; i++) parent[i] = i, Rank[i] = 1; } int find_parent(int x) { if(parent[x] == x) { return x; } return parent[x] = find_parent(parent[x]); } void make_union(int x, int y) { int p = find_parent(x); int q = find_parent(y); if(p != q){ if(Rank[p] < Rank[q]) swap(p,q); parent[q] = p; Rank[p] += Rank[q]; } } bool isUnion(int x, int y) { return find_parent(x) == find_parent(y); } int main() { //FASTIO /* //double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("error.txt", "w", stderr); #endif //*/ int N,Q; cin >> N >> Q; Initialization(N); int cnt = 1; map<string, int> mp; for(int i = 1; i <= Q; i++){ int x,y; char ch; cin >> ch; if(ch == 'M'){ cin >> x >> y; make_union(x,y); } else{ cin >>x; cout << Rank[find_parent(x)]<<endl; } //cerr << Rank[find_parent(x)] << " " <<Rank[find_parent(y)]<<endl; } //double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; }

Another Solution

Share:

Read More

Construct the Array

Construct the Array

Topic: DP

Complexity: O(n) 

Solution:

Code:

const long long mod = 1000000000+7;
long countArray(int n, int k, int x) {
    // Return the number of ways to fill in the array.
    vector<long long> a(n), b(n);
    a[0] = x == 1 ? 1 : 0;
    b[0] = x == 1 ? 0 : 1;

    for(int i = 1; i < n; i++){
        a[i] = b[i - 1] % mod;
        b[i] = (a[i- 1]*(k-1) + b[i-1] * (k-2) )%mod;
    }
    return a[n-1];
}

Share:

Read More