DOCSEARCHbyAlgolia
Submit Docs

Chasech Technical Notes

website·Indexed 30 days ago

https://chasech.top/

A collection of technical documentation and learning resources covering algorithm design, data structures (such as Disjoint Set Union, Monotonic Queue, and Adjacency Lists), number theory (including Euler's totient function and Extended Euclidean algorithm), and mobile development guides for Android Studio and Flutter.

Tokens
29.8K
Snippets
92
Records
125
Agent score
47%

What's inside Chasech

  1. Design a Dynamic Programming (DP) algorithm

    To design a dynamic programming algorithm, follow these fundamental steps: 1. Define a starting point for your pointer (e.g., starting from the head or the tail of the data structure). 2. Initialize state variables to track the optimal value (e.g., a variable to store the current maximum profit). 3. Iterate through the data by moving the pointer and updating the state variables based on the transition logic.

  2. Understand the KMP 'next' array concept

    In the KMP algorithm, the next array (often denoted as ne[]) is used to avoid redundant comparisons. For a pattern string p, next[i] = j indicates that the longest proper prefix of the substring p[0...i-1] that is also a suffix of that substring has a length of j.

    Specifically, if next[i] = j, then the first j characters of the pattern are identical to the last j characters of the substring ending at i-1 (p[0...j-1] == p[i-j...i-1]).

  3. Understand the SPFA (Shortest Path Faster Algorithm) logic

    SPFA is a queue-optimized version of the Bellman-Ford algorithm. It is based on the principle that a node's distance dist[v] can only be updated if the distance to its predecessor dist[u] has decreased. Therefore, only nodes whose distances have been updated need to be added to a queue to potentially update their neighbors.

    Algorithm Steps:

    1. Add the starting node to a queue.
    2. Poll a node from the queue and attempt to relax all its outgoing edges (update the distance to neighboring nodes).
    3. If a neighbor's distance is successfully shortened and that neighbor is not already in the queue, add it to the queue.
    4. Repeat until the queue is empty.

  4. Understand Disjoint Set Union (DSU) core concepts

    DSU uses a tree-based representation for sets:

    • Basic DSU: Each set is a tree. The root node's ID represents the set ID. Each child node stores the ID of its parent.
    • Path-Optimized DSU: During the search for the root, child nodes are updated to point directly to the root node, reducing the depth of the tree and speeding up future lookups.

  5. Understand the Relaxation operation in Bellman-Ford

    The relaxation operation is the core mechanism of the Bellman-Ford algorithm. It continuously updates the estimated shortest distance to a node. For an edge from node u to node v with weight w, the operation checks if the current distance to v can be improved by traveling through u: dist[v] = min(dist[v], dist[u] + w).

  6. Modify power strip LED circuit for durability

    To prevent LED failure in power strips, implement the following circuit modifications:

    1. Prevent Reverse Breakdown: Connect a 1N4007 rectifier diode in parallel with the LED (anti-parallel). During the negative half-cycle of the AC, the 1N4007 conducts, clamping the reverse voltage across the LED to approximately 0.7V.
    2. Manage Surge Currents: Add a current-limiting resistor. This is critical because current-limiting capacitors may fail to handle the surge current generated when a charger is plugged into the strip, which could otherwise cause forward breakdown of the LED.
    3. Additional Components: Incorporate a current-limiting capacitor and a discharge resistor for overall circuit stability.

  7. Implement a Monotonic Queue for sliding window maximum/minimum

    A monotonic queue is used to optimize problems where you need to find the maximum or minimum value within a sliding window. The queue stores indices rather than values to allow the head pointer to track whether an element has slid out of the current window.

    Selection Logic (Mnemonic):

    • To find the Maximum: Maintain a Monotonically Decreasing queue (the head is always the maximum).
    • To find the Minimum: Maintain a Monotonically Increasing queue (the head is always the minimum).

    Algorithm Steps:

    1. Remove the head element if it has slid out of the window range.
    2. Remove elements from the tail that violate the monotonic property (based on the new element being added).
    3. Push the current index onto the tail.
    // Applicable scenario: Find the maximum/minimum value in a sliding window
// q stores indices to allow tracking of window boundaries
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    // 1. Check if the head of the queue has slid out of the window
    while (hh <= tt && check_out(q[hh])) hh ++ ;

    // 2. Maintain monotonicity: remove elements from the tail
    while (hh <= tt && check(q[tt], i)) tt -- ;

    // 3. Add current index to the queue
    q[ ++ tt] = i;
}

  8. Implement Prim's Algorithm for Minimum Spanning Tree (MST)

    Prim's algorithm finds the Minimum Spanning Tree of a connected, weighted undirected graph by greedily expanding a tree from a starting node. The core logic is as follows:

    1. Select an arbitrary starting node and add it to the spanning tree.
    2. Find the node closest to the current spanning tree (the node with the minimum edge weight connecting it to any node already in the tree) and add it to the tree.
    3. Repeat step 2 until all connected nodes have been added to the spanning tree.
    import java.util.*;

public class Main {
    static int N = 510,
        INF = 0x3f3f3f3f;
    static int[][] g = new int[N][N];
    // dist[i] stores the shortest distance from node i to the current MST
    static int[] dist = new int[N];
    // st[i] marks whether node i has been added to the MST
    static boolean[] st = new boolean[N];
    static int n, m;
        
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        
        for(int i = 1; i <= n; i ++ ) Arrays.fill(g[i], INF);

        while(m -- > 0)
        {
            int from = in.nextInt(), to = in.nextInt(), weight = in.nextInt();
            g[from][to] = Math.min(g[from][to], weight);
            g[to][from] = g[from][to];
        }
        
        int t = prim();
        if(t == INF) System.out.println("impossible");
        else System.out.println(t);
    }
    
    static int prim()
    {
        Arrays.fill(dist, INF);
        dist[1] = 0;
        
        int res = 0;
        for(int i = 0; i < n; i ++ )
        {
            int t = -1;
            for(int j = 1; j <= n; j ++ )
            {
                if(!st[j] && (t == -1 || dist[j] < dist[t]))
                    t = j;
            }
            
            // If the closest node is unreachable, the graph is not connected
            if(dist[t] == INF) return INF;
            
            res += dist[t];
            st[t] = true;
            
            // Update the shortest distance from remaining nodes to the expanded MST
            for(int j = 1; j <= n; j ++ ) 
                dist[j] = Math.min(dist[j], g[t][j]);
        }
        
        return res;
    }
}

  9. Understand Flutter framework search paths in Xcode

    Depending on how Flutter is integrated into the iOS project, different search paths are used to locate the flutter.framework. Use the following guide to determine which path applies to your scenario:
    PathDescriptionUsage Scenario
    ${PODS_ROOT}/FlutterCocoaPods installed Flutter.frameworkWhen Flutter is managed via Pods
    ${PODS_ROOT}/../FlutterLocally generated Flutter.frameworkGenerated during flutter build ios
    $(FLUTTER_ROOT)/.ios/FlutterFlutter SDK's built-in iOS support filesOlder projects or direct SDK dependencies

  10. Apply mirror sources in build.gradle.kts

    Add the mirror source configurations within the repositories block of the allprojects section in the root build.gradle.kts file to apply them to all modules in the project.
    allprojects {
    repositories {
        // Add Aliyun mirror configurations here
        google()
        mavenCentral()
    }
}

  11. Implement the Two-Pointer algorithm for sequence intervals

    The Two-Pointer algorithm optimizes brute-force solutions by leveraging the monotonicity of pointer movement. It is commonly used in two scenarios: maintaining a specific interval within a single sequence, or maintaining a specific order across two different sequences (such as merging two sorted arrays in Merge Sort).
    for (int i = 0, j = 0; i < n; i++) 
{
    while (j < i && check(i, j)) j++;

    // Implement specific problem logic here
}

  12. Apply mirror sources in settings.gradle.kts

    To configure mirrors for Gradle plugins, add the mirror source configurations within the repositories block of the pluginManagement section in the root settings.gradle.kts file.
    pluginManagement {
    repositories {
        // Add Aliyun mirror configurations here
        google()
        mavenCentral()
        gradlePluginPortal()
    }
}