11 October 2018: Workshop

From UMCPC Wiki
Jump to navigation Jump to search

Trapping Rain Water

  • https://leetcode.com/problems/trapping-rain-water/description/
    class Solution {
    public:
        int trap(vector<int>& H) {
            int n = H.size();
            
            vector<int> L(n);
            for (int i = 1; i < n; i++) {
                L[i] = max(H[i - 1], L[i - 1]);
            }
            
            vector<int> R(n);
            for (int i = n - 2; i >= 0; i--) {
                R[i] = max(H[i + 1], R[i + 1]);
            }
            
            int ans = 0;
            for (int i = 0; i < n; i++) {
                ans += max(0, min(L[i], R[i]) - H[i]);
            }
            
            return ans;
        }
    };
    

Sum of Subsequence Widths

  • https://leetcode.com/problems/sum-of-subsequence-widths/description/
    class Solution {
    public:
        int sumSubseqWidths(vector<int>& A) {
            int n = A.size();
            long MOD = 1e9 + 7;
            long ans = 0;
    
            sort(A.begin(), A.end());
    
            for (long i = 0, p = 1; i < n; i++, p = (p << 1) % MOD) {
                ans += p * A[i];
                ans -= p * A[n - i - 1];
                ans %= MOD;
            }
    
            if (ans < 0) {
                ans += MOD;
            }
    
            return ans;
        }
    };
    

Paths in a Tree

  • https://pcs.ucc.asn.au/problem/pathsinatree
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int N;
    vector<pair<int, long>> g[112345];
    long ans = 0;
    
    long dfs(int at, int parent) {
        int cnt = 1;
        for (auto edge : g[at]) {
            if (edge.first != parent) {
                auto m = dfs(edge.first, at);
                ans += m * (N - m) * edge.second;
                cnt += m;
            }
        }
        return cnt;
    }
    
    int main() {
        cin >> N;
        for (int i = 0; i < N-1; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            u--; v--;
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }
        dfs(0, -1);
        cout << ans << endl;
    }