𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

def solve(priceList):
    floors = len(priceList)
    frequencies = len(priceList[0])
    dp = [[0] * frequencies for _ in range(floors)]
    for j in range(frequencies):
        dp[0][j] = priceList[0][j]
    for i in range(1, floors):
        for j in range(frequencies):
            min_cost = float('inf')
            for k in range(frequencies):
                if k != j: 
                    min_cost = min(min_cost, dp[i-1][k])
            dp[i][j] = priceList[i][j] + min_cost
    return min(dp[-1])

758 views05:36

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> tree;
vector<int> values;
long long total = 0;

void dfs(int node, int parent, vector<int>& path) {
    path.push_back(values[node]);

    if (path.size() % 2 == 1) {

        vector<int> sorted_path = path;
        sort(sorted_path.begin(), sorted_path.end());
        int median = sorted_path[sorted_path.size() / 2];
        total += median;
    }

    for (int neighbor : tree[node]) {
        if (neighbor != parent) {
            dfs(neighbor, node, path);
        }
    }

    path.pop_back();
}

int main() {
    int n;
    cin >> n;

    values.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> values[i];
    }

    tree.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    vector<int> path;
    dfs(0, -1, path);

    cout << total<< endl;

    return 0;
}

//median path ✅

715 views07:01

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

635 views07:02

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

Photo

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define endl "\n"
#define MOD 1000000007
#define MOD2 998244353
#define vll vector<ll>

struct SegmentTree {
    ll N;
    vll tree;
    ll neutral = 0;

    ll combine(ll a, ll b) {
        return a + b;
    }

    void build(ll u, ll L, ll R, vll &v) {
        if(L == R) {
            tree[u] = v[L];
        } else {
            ll M = (L + R) / 2;
            build(u * 2, L, M, v);
            build(u * 2 + 1, M + 1, R, v);
            tree[u] = combine(tree[u * 2], tree[u * 2 + 1]);
        }
    }

    SegmentTree(vll v) {
        N = v.size() - 1;
        tree.assign(4 * N + 1, 0);
        build(1, 1, N, v);
    }

    ll query(ll lq, ll rq, ll u, ll L, ll R) {
        if(L > rq || R < lq) {
            return neutral;
        } else if(L >= lq && R <= rq) {
            return tree[u];
        } else {
            ll M = (L + R) / 2;
            return combine(query(lq, rq, u * 2, L, M), query(lq, rq, u * 2 + 1, M + 1, R));
        }
    }

    void update(ll idx, ll val, ll u, ll L, ll R) {
        if(L > idx || R < idx) {
            return;
        } else if(L == R) {
            tree[u] = val;
            return;
        } else {
            ll M = (L + R) / 2;
            update(idx, val, u * 2, L, M);
            update(idx, val, u * 2 + 1, M + 1, R);
            tree[u] = combine(tree[u * 2], tree[u * 2 + 1]);
        }
    }
};

const int MAXN = 1e6 + 1;
vector<int> spf(MAXN);

void sieve() {
    spf[1] = 1;
    for (int i = 2; i < MAXN; i++)
        spf[i] = i;
    for (int i = 4; i < MAXN; i += 2)
        spf[i] = 2;
    for (int i = 3; i * i < MAXN; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j < MAXN; j += i)
                if (spf[j] == j)
                    spf[j] = i;
        }
    }
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    sieve();
    int n, q; cin >> n >> q;
    vll arr(n + 1);
    for(int i = 1; i <= n; i++) cin >> arr[i];
    SegmentTree sgt(arr);
    set<int> s;
    for(int i = 1; i <= n; i++)
        s.insert(i);

    while(q--) {
        int type; cin >> type;
        int a, b; cin >> a >> b;
        if(type == 3) {
            sgt.update(a, b, 1, 1, n);
            int temp = a;
            auto it = s.lower_bound(temp);
            if(it != s.end() and s.size() != 0 and *it == a) {
                s.erase(temp);
                s.insert(a);
            } else {
                s.insert(a);
            }
            arr[a] = b;
        } else if (type == 2) {
            cout << sgt.query(a, b, 1, 1, n) << endl;
        } else {
            while(a <= b) {
                int temp = a;
                auto it = s.lower_bound(temp);
                if(it == s.end()) break;
                if(*it > b) break;
                int c = *it + 1;
                sgt.update(a, arr[a] / spf[arr[a]], 1, 1, n);
                if(spf[a] == 1) {
                    s.erase(temp);
                }
                arr[a] = spf[a];
                a = c;
            }
        }
    }
    return 0;
}

Divisor queries ✅

652 viewsedited 07:03

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

int minimize_difference(int N, vector<int>& A, int K, vector<int>& operand) {
    vector<vector<int>> possible_values(N);
    for (int idx = 0; idx < N; ++idx) {
        set<int> values;
        for (int mask = 0; mask < (1 << K); ++mask) {
            int new_value = A[idx];
            for (int i = 0; i < K; ++i) {
                if (mask & (1 << i)) {
                    new_value ^= operand[i];
                }
            }
            values.insert(new_value);
        }
        possible_values[idx] = vector<int>(values.begin(), values.end());
        sort(possible_values[idx].begin(), possible_values[idx].end());
    }
    vector<pair<int, int>> all_values;
    for (int i = 0; i < N; ++i) {
        for (int value : possible_values[i]) {
            all_values.emplace_back(value, i);
        }
    }
    sort(all_values.begin(), all_values.end());
    map<int, int> count;
    int left = 0;
    int min_range = INT_MAX;
    int distinct_count = 0;

    for (int right = 0; right < all_values.size(); ++right) {
        int value = all_values[right].first;
        int index = all_values[right].second;

        if (count[index] == 0) {
            ++distinct_count;
        }
        ++count[index];

        while (distinct_count == N) {
            min_range = min(min_range, value - all_values[left].first);
            int left_value = all_values[left].first;
            int left_index = all_values[left].second;
            --count[left_index];
            if (count[left_index] == 0) {
                --distinct_count;
            }
            ++left;
        }
    }

    return min_range;
}

Xor on Array ✅

741 views07:05

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

646 views07:06

𝗖𝗦 𝗔𝗹𝗴𝗼 💻 🌐 『𝗖𝗼𝗺𝗽𝗲𝘁𝗶𝘁𝗶𝘃𝗲 𝗣𝗿𝗼𝗴𝗿𝗮𝗺𝗺𝗶𝗻𝗴』

def getUnallottedUsers(bids, totalShares):
    sorted_bids = sorted(bids, key=lambda x: (-x[2], x[3]))
    
    allocated_shares = {}
    unallotted_users = set()
    remaining_shares = totalShares
    
    for user_id, shares, price, timestamp in sorted_bids:
        if remaining_shares == 0:
            unallotted_users.add(user_id)
            continue
        
        allocated = min(shares, remaining_shares)
        allocated_shares[user_id] = allocated_shares.get(user_id, 0) + allocated
        remaining_shares -= allocated
        
        if allocated_shares[user_id] < shares:
            unallotted_users.add(user_id)
    
    fully_unallotted = [user_id for user_id, shares in allocated_shares.items() if shares == 0]
    fully_unallotted.extend([bid[0] for bid in bids if bid[0] not in allocated_shares])
    
    return sorted(set(fully_unallotted))

Bny ✅

👍1

711 views07:07

About

Blog

Apps

Platform