DOCSEARCHbyAlgolia
Submit Docs

lsk404's Programming Notes and Competitive Programming Solutions

website·Indexed 30 days ago

https://lsk404.github.io/

A collection of competitive programming solutions and technical notes. Includes problem analyses and C++ and Python implementations for contests such as Codeforces, AtCoder, Nowcoder, ICPC Asia Regionals, and the Lanqiao Cup. The site also features academic study notes for Computer Organization, Data Structures, and Operating Systems from ZZU's School of Cyber Security, as well as guides on C++ knowledge points, number theory, and dynamic programming.

Tokens
78K
Snippets
278
Records
390
Agent score
74%

What's inside lsk404

  1. Study guide for Introduction to Software Engineering exam

    The Introduction to Software Engineering exam covers the following key areas:

    Core Concepts to Define:

    • Software
    • Software Project Management
    • White-box Testing
    • Software Life Cycle

    Key Topics for Short Answer/Essay Questions:

    • Waterfall Model: Definition, advantages, and disadvantages.
    • Coding Standards: Benefits of good coding habits and examples of widely recognized coding practices.
    • Design Phases: The specific tasks involved in General Design (Overall Design) versus Detailed Design.
    • Requirements Analysis: Definition, primary tasks, and common difficulties/challenges.
    • Feasibility Analysis: Definition and the rationale for why it is necessary.
    • DevOps: Be prepared for objective/multiple-choice questions regarding DevOps concepts.

  2. Understand the Sprague-Grundy (SG) Theorem for Impartial Games

    The SG theorem is used to analyze Impartial Combinatorial Games (ICG), where the available moves depend only on the state of the game, not on which player is moving. Any such game can be modeled as a game on a Directed Acyclic Graph (DAG).

    Key Concepts:

    • MEX (Minimum Excluded value): The smallest non-negative integer that is not present in a set.
    • SG Value: For a node $x$, $SG(x) = mex{{SG(y) \mid y \text{ is reachable from } x}}$.
    • Winning/Losing States: A state is a losing state (P-position) if $SG(x) = 0$, and a winning state (N-position) if $SG(x) > 0$.
    • Sum of Games: For a game composed of multiple independent sub-games (like multiple piles in NIM), the SG value of the combined state is the XOR sum of the SG values of the individual sub-games: $SG(G) = SG(G_1) \oplus SG(G_2) \oplus \dots \oplus SG(G_n)$.
    • NIM Game: A specific ICG where players remove items from piles. The first player wins if and only if the XOR sum of the pile sizes is non-zero.

  3. Handle high-precision integers

    Python natively supports arbitrary-precision integers (high-precision arithmetic), meaning there is no overflow for standard integer addition, subtraction, and multiplication regardless of the number of digits.
    # High precision addition
a, b = int(input()), int(input())
print(a + b)

# High precision floor division
print(a // b)

  4. Compare Policy Iteration and Value Iteration algorithms

    Policy Iteration and Value Iteration are two fundamental RL algorithms. The primary difference lies in how they update values and policies: Value Iteration performs a policy update immediately after the first value calculation, whereas Policy Iteration iteratively refines the policy until convergence. Truncated Policy Iteration is a hybrid approach that stops the iteration process at a specific intermediate step.

  5. Understand Markov Decision Process (MDP) fundamentals

    A Markov Decision Process (MDP) is defined by a set of states, actions, and rewards, characterized by the 'Markov property' (the future is independent of the past given the present state). Key components include:

    • State (s): A representation of the current situation (e.g., a grid cell).
    • Action (a): A move that changes the state.
    • State Transition Probability: The probability $P(s'|s, a)$ of reaching state $s'$ from state $s$ after taking action $a$.
    • Reward (r): A real number representing the immediate benefit of a transition.
    • Policy ($\pi$): A mapping $\pi(a|s)$ defining the probability of taking action $a$ in state $s$.
    • Trajectory: A sequence of states, actions, and rewards.
    • Return: The sum of rewards in a trajectory, often calculated as a discounted return: $r_0 + \gamma r_1 + \gamma^2 r_2 + \dots$ where $\gamma \in [0, 1)$ is the discount rate.

  6. Find the number of distinct prime factors of a number

    To find the number of distinct prime factors of a given integer (e.g., 2024), you can use the Fundamental Theorem of Arithmetic. Iterate from 2 up to the number; if the number is divisible by the current iterator, increment the count and repeatedly divide the number by that factor until it is no longer divisible.
    #include<bits/stdc++.h>
using namespace std;
int main() {
    int n = 2024;
    int cnt = 0;
    for(int i = 2; i <= n; i++) {
        if(n % i == 0) {
            cnt++;
            while(n % i == 0) {
                n /= i;
            }
            cout << i << ' ';
        }
    }
    return 0;
}

  7. Manage C++ I/O streams and buffers

    C++ I/O relies on iostream and fstream. Including <iostream> automatically creates 8 stream objects: cin, cout, cerr, and clog (each in narrow and wide character versions).

    Key Concepts:

    • Buffering: Data is stored in a buffer and transferred to the destination in blocks (typically 512 bytes) to improve efficiency. This process is called 'flushing'.
    • Redirection: Standard input (<) and output (>) can be redirected from the default keyboard/monitor. Note that redirecting standard output does not affect cerr or clog, ensuring error messages still reach the screen.
    • Flushing the Buffer: The output buffer is flushed when:
      1. A newline character is sent to the buffer.
      2. An input operation is about to occur.
      3. std::endl is used.
      4. std::flush is used or flush(cout) is called.

  8. Solve the 'Berserk Monsters' problem using a doubly linked list

    The problem involves $n$ monsters in a row. In each round, a monster dies if the sum of the attack powers of its current living neighbors exceeds its own defense value. You must output the number of monsters that die in each round.

    Strategy:

    1. Use a doubly linked list (implemented via pre and nxt arrays) to maintain the current living neighbors of each monster.
    2. A monster can only change its status (die) if one of its neighbors died in the previous round, as this changes the total attack power it receives.
    3. Maintain a queue (next) of monsters to check in the current round. Initially, all monsters are added.
    4. In each round:
      • Iterate through the queue and identify monsters whose neighbors' attack sum $> d[p]$.
      • Mark them as dead and add their neighbors to the queue for the next round.
      • Update the doubly linked list to remove the dead monsters by linking their pre and nxt neighbors to each other.
    #include<bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 5), d(n + 5);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> d[i];

    vector<bool> over(n + 5, false);
    vector<int> pre(n + 5), nxt(n + 5), check_list;
    for(int i = 1; i <= n; i++) {
        pre[i] = i - 1; nxt[i] = i + 1;
        check_list.push_back(i);
    }

    for(int round = 1; round <= n; round++){
        vector<int> next_round_check, dead_this_round;
        int dead_count = 0;
        for(auto p : check_list){
            if(over[p]) continue;
            if(a[pre[p]] + a[nxt[p]] > d[p]){
                over[p] = true;
                if(pre[p] != 0) next_round_check.push_back(pre[p]);
                if(nxt[p] != n + 1) next_round_check.push_back(nxt[p]);
                dead_count++;
                dead_this_round.push_back(p);
            }
        }
        for(auto p : dead_this_round){
            pre[nxt[p]] = pre[p];
            nxt[pre[p]] = nxt[p];
        }
        cout << dead_count << ' ';
        check_list = next_round_check;
    }
    cout << endl;
}

  9. Solve Rudolf and k Bridges using Dynamic Programming and Priority Queue

    The problem requires finding the minimum cost to build $k$ consecutive bridges across a grid of $n$ rows and $m$ columns. Each bridge must start at column 1 and end at column $m$, with no two adjacent pillars exceeding distance $d$. The cost of a pillar is its seawater depth plus one.

    To solve this, calculate the minimum cost for each row independently using DP: $dp[i]$ is the minimum cost to place a pillar at column $i$. The transition is $dp[i] = ext{depth}[i] + 1 + \min(dp[j])$ where $i - j ≤ d$. To optimize the $\min(dp[j])$ lookup from $O(m)$ to $O(\log m)$, a priority queue is used to store pillars and their costs, popping elements that exceed the distance $d$ (expired elements).

    After calculating costs for all $n$ rows, use a prefix sum array to find the minimum sum of $k$ consecutive rows in $O(n)$ time.

    #include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;

struct Node {
    int x;    // index
    int wast; // cost
    friend bool operator<(Node n1, Node n2) {
        return n1.wast > n2.wast;
    }
};

void solve() {
    int n, m, k, d;
    cin >> n >> m >> k >> d;
    vector<int> ans;
    ans.push_back(0);
    int t = n;
    while(t--) {
        priority_queue<Node> pq;
        int x;
        cin >> x; // depth of first column (always 0)
        pq.push({1, 1}); // cost is depth + 1
        for(int i = 2; i <= m; i++) {
            cin >> x;
            while(pq.top().x + d + 1 < i) {
                pq.pop();
            }
            if(i == m) {
                ans.push_back(pq.top().wast + x + 1);
                break;
            }
            pq.push({i, pq.top().wast + x + 1});
        }
    }
    for(int i = 1; i <= n; i++) {
        ans[i] += ans[i-1];
    }
    int res = INF;
    for(int i = k; i <= n; i++) {
        res = min(res, ans[i] - ans[i-k]);
    }
    cout << res << endl;
}

signed main() {
    int T = 1;
    cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

  10. Solve the 'Birthday Gift' array partitioning problem

    The goal is to partition an array of length $n$ into the maximum number of contiguous segments $k$ such that the bitwise OR of the XOR sums of these segments is $\le x$.

    Key logic:

    1. Use prefix XORs: Let $sum_i$ be the XOR sum of the first $i$ elements. The XOR sum of a segment $[l, r]$ is $sum_r \oplus sum_{l-1}$.
    2. The condition $(sum_{r_1} \oplus sum_{l_1-1}) \mid (sum_{r_2} \oplus sum_{l_2-1}) \mid \dots \mid (sum_{r_k} \oplus sum_{l_k-1}) \le x$ can be simplified by observing that if we pick $l_1=1$ (so $sum_{l_1-1}=0$), the condition relates to the prefix XORs at the boundaries of the partitions.
    3. To maximize $k$, iterate through each bit $k$ of $x$. If the $k$-th bit is 1, you can potentially create a tighter bound by setting that bit to 0 and all lower bits to 1.
    4. For a target mask $xx$, a prefix XOR $sum_i$ is a valid partition boundary if $(sum_i \mid xx) == xx$.
    5. The final prefix XOR $sum_n$ must satisfy the condition $(sum_n \mid xx) == xx$ for the partition to be valid.
    #include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)

void solve(){
    int n,x;
    cin>>n>>x;
    vector<int> vec(n+5);
    rep(i,1,n){
        cin>>vec[i];
        vec[i] ^= vec[i-1]; // Prefix XOR
    }
    int ans = -1;
    rep(k,0,32){
        int xx = x;
        int cnt = 0;
        if((x>>k) & 1){
            xx -= 1<<k;
            xx |= ((1<<k)- 1);
        }
        // The total XOR sum must fit within the mask xx
        if((vec[n] | xx) != xx) {continue;}
        rep(i,1,n){
            if((vec[i] | xx) == xx){
                cnt++;
                ans = max(ans,cnt);
            }
        }
    }
    if(ans > 0) cout<<ans<<'\n';
    else cout<<-1<<'\n';
}

signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

  11. Enable HDR and GPU acceleration for browser videos in Windows

    To improve video quality and enable frame interpolation for browsers, you can configure Windows system settings:

    1. Enable HDR (if supported) via Settings -> System -> Display -> Use HDR.
    2. Enable GPU acceleration for specific browsers via Settings -> System -> Display -> Graphics by adding your preferred browser to the list.

  12. Implement inline functions for performance

    Use the inline keyword to suggest to the compiler that the function body be expanded at the call site. This can reduce the overhead of function calls for small, frequently used functions.