DOCSEARCHbyAlgolia
Submit Docs

Felix's Blog

website·Indexed 31 days ago

https://felixesintot.top/

A personal technical blog focusing on competitive programming, featuring algorithm templates for data structures, graph theory, number theory, and string processing. It includes detailed problem editorials for platforms like Luogu and AtCoder, as well as reflections and logs from various internal mock contests and competitions such as NOIP and CSP.

Tokens
18.8K
Snippets
65
Records
80
Agent score
52%

What's inside Felix's Blog

  1. Understand Vertex-Biconnected Components and Cut-Vertices

    Vertex-Biconnected Components (V-BCCs) are maximal subgraphs such that any two vertices in the component can be connected by at least two vertex-disjoint paths. A vertex that, when removed, increases the number of connected components in the graph is called a cut-vertex (articulation point). Any vertex connecting two different vertex-biconnected components must be a cut-vertex.

  2. Optimize Tree-based Knapsack Complexity to O(nm)

    Standard tree-based knapsack problems (where items have dependencies based on a tree structure) typically have a complexity of $O(nm^2)$. By optimizing the upper and lower bounds of the loops during the DFS merge process, the complexity can be reduced to $O(nm)$.
    int dfs(int u) {
    int p = 1;
    f[u][1] = s[u];
    for (auto v : e[u]) {
        int siz = dfs(v);
        // Optimize loop bounds to only consider merged subtrees 
        // and valid course counts to achieve O(nm)
    }
    // ...
}

  3. Solve the problem based on CF468A (Special Judge construction)

    For the problem based on CF468A, the goal is to construct a solution. For inputs 1, 2, and 3, there is no solution. For inputs 4 and 5, solutions can be manually constructed. For inputs where n > 5, the strategy is to repeatedly output the operation n - (n-1) = 1 and 1 * 1 = 1 to effectively remove the numbers n and n-1 from the set. This reduces the problem size by 2 until n reaches 4 or 5, at which point the manual construction is used.

  4. Solve Luogu P3403 using Dijkstra's algorithm on modulo residues

    To find the minimum floor reachable for each residue modulo $x$, model the problem as a shortest path problem on a graph where nodes represent residues $0$ to $x-1$.

    1. Start from node $1$ (representing the 1st floor).
    2. For each node $i$ ($0 \le i < x$), create edges to $(i+y) \pmod x$ with weight $y$ and to $(i+z) \pmod x$ with weight $z$.
    3. Run Dijkstra's algorithm starting from node $1$. The resulting shortest path distance $dis[i]$ represents the lowest floor number $f$ such that $f \equiv i \pmod x$ that can be reached.
    4. For a total of $h$ floors, the number of reachable floors for a specific residue $i$ is calculated as: if $h \ge dis[i]$, then the count is $\lfloor (h - dis[i]) / x \rfloor + 1$.
    5. Sum these counts for all $i$ from $0$ to $x-1$ to get the total answer.
    // Core logic for calculating total reachable floors
long long total_ans = 0;
for (int i = 0; i < x; ++i) {
    if (h >= dis[i]) {
        total_ans += (h - dis[i]) / x + 1;
    }
}

  5. Solve the problem based on P4552 using Difference Sequences

    For the problem based on P4552, convert the original sequence into a difference sequence. The objective is to make all elements from index 2 to n equal to 0 using two types of operations: incrementing one element while decrementing another, or changing a single element by ±1.

    1. The minimum number of operations is the maximum of the sum of all positive numbers and the absolute sum of all negative numbers in the difference sequence (from index 2 to n).
    2. The number of possible values for the first element is determined by the difference between the positive sum and the negative sum: abs(negative_sum - positive_sum) + 1.

  6. Calculate the number of divisors for the product of two integers

    To find the number of divisors for the product $A \times B$, perform prime factorization on both $A$ and $B$ separately. Sum the exponents of the same prime factors across both numbers. The total number of divisors is calculated by taking each resulting exponent, adding one to it, and multiplying these values together. When implementing the factorization, ensure you handle prime factors up to $\sqrt{A}$ and $\sqrt{B}$.
    #include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 10000012;
ll a, b, ans = 1, cnt[maxn];

// Function to perform prime factorization and count exponents
void pl(ll& dc) {
    for(ll i = 2; i * i <= dc; ++i) {
        while(dc % i == 0) {
            cnt[i]++;
            dc /= i;
        }
    }
    if (dc > 1) cnt[dc]++; // Handle remaining prime factor
}

int main() {
    // Input two numbers a and b
    if (!(cin >> a >> b)) return 0;
    
    pl(a);
    pl(b);
    
    // Calculate total divisors based on prime exponents
    // Note: The provided source code has specific logic for a==b
    // but the general mathematical rule is: product of (exponent + 1)
    for(int i = 2; i < maxn; ++i) {
        if(cnt[i] > 0) {
            ans *= (cnt[i] + 1);
        }
    }
    
    printf("%lld", ans);
    return 0;
}

  7. Calculate the modular multiplicative inverse

    Depending on the properties of the modulus $p$, use different methods to find the modular inverse of $a$:

    1. When $p$ is prime: Use Fermat's Little Theorem: qp(a, p - 2, p).
    2. When $\gcd(a, p) = 1$: Use Euler's Theorem: qp(a, phi(p) - 1, p).
    3. Using Extended Euclidean Algorithm (exGCD): General method for $\gcd(a, p) = 1$.
    4. Linear Preprocessing: Efficiently compute inverses for all $i$ from $1$ to $n$ in $O(n)$.
    // exGCD version
ll inv(ll a, ll p) {
    ll tx, ty;
    exgcd(a, p, tx, ty);
    return (tx % p + p) % p;
}

// Linear preprocessing version (for all i up to n)
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
    inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}

  8. Optimize Tree DP Knapsack complexity to O(nm)

    In a tree-based 0-1 knapsack problem (where each node has a cost of 1 and a specific value), the standard complexity is often O(nm^2). This can be optimized to O(nm) by restricting the inner loops of the DP transition to the current size of the merged subtrees and the maximum capacity m. Specifically, when merging a subtree rooted at v into a parent node u, the loops should only iterate up to the current size of the processed components of u and the size of subtree v, while ensuring the total items do not exceed m + 1.
    int dfs(int u) {
    int p = 1; // Current size of subtree rooted at u
    f[u][1] = s[u]; // Initial value for picking only node u
    for (auto v : e[u]) {
        int siz = dfs(v);
        // Optimization: Limit loops by current size p and subtree size siz
        // Only consider states up to m + 1
        for (int i = min(p, m + 1); i; i--) {
            for (int j = 1; j <= siz && i + j <= m + 1; j++) {
                f[u][i + j] = max(f[u][i + j], f[u][i] + f[v][j]);
            }
        }
        p += siz;
    }
    return p;
}

  10. Solve the Garbage Landscape (P1156) problem using dynamic programming

    This problem is a variation of the knapsack problem where the goal is to reach a target height (dep) by trading time for height. The core strategy is to maintain a DP array f[i] representing the maximum time available when at height i.

    Key logic:

    1. Sort the available items (garages) by their required time t in ascending order.
    2. Use a DP array f initialized to a very small value, with f[0] set to the starting time (e.g., 10).
    3. For each item, if the current time at height j (f[j]) is greater than or equal to the item's required time nl[i].t, you can transition:
      • If the new height j + nl[i].d reaches or exceeds the target dep, the current item's time nl[i].t is the answer.
      • Otherwise, update the maximum time at the new height: f[j + nl[i].d] = max(f[j], f[j + nl[i].d]) and increase the time at the current height by the item's length: f[j] += nl[i].l.
    const int maxn=152;int dep,n,f[maxn],ans;struct garage{    int t,l,d;}nl[maxn];inline bool cmp(garage x,garage y){    return x.t<y.t;}int main(){    dep=in();n=in();    fru(i,1,n)
    {        nl[i].t=in();        nl[i].l=in();        nl[i].d=in();    }
    memset(f,-0x3f,sizeof f);    f[0]=10;    sort(nl+1,nl+n+1,cmp);    fru(i,1,n)
    {        frd(j,dep,0)
        if(f[j]>=nl[i].t)
        {            if(j+nl[i].d>=dep)
            {                out(nl[i].t);                return 0;            }
            f[j+nl[i].d]=max(f[j],f[j+nl[i].d]);            f[j]+=nl[i].l;
        }    }
    out(f[0]);    return 0;}

  11. Solve P5056 using Dynamic Programming and Bitmasking

    This solution addresses problem P5056 using a DP approach with state compression. The key insight is that for strings of length up to 13, the number of valid bracket sequences is relatively small (approximately 45,000), making a brute-force or state-compressed DP feasible. A critical implementation detail for handling nested brackets (e.g., '((') is to identify the most recent unmatched bracket to maintain validity.
    #include<bits/stdc++.h>
#define fru(i,j,k) for(int i=j;i<=k;i++)
#define frd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
using ll = long long;

char c=' ';
int in(void){
    int x=0;bool f=false;
    while(!isdigit(c)){f^=c=='-';c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}

const int maxn=20,maxk=60012;
int n,m,ex,ey,bs[maxn];
char ch[maxn][maxn];
unordered_map<int,ll>f[2];
ll ans=0;

inline int gt(int num,int tp){
    return (num>>(tp<<1))&3;
}

int main(){
    n=in();m=in();
    fru(i,1,n)
    {
        scanf("%s",ch[i]+1);
        fru(j,1,m)if(ch[i][j]=='.')ex=i,ey=j;
    }
    bs[0]=1;
    fru(i,1,m) bs[i]=bs[i-1]<<2;
    
    f[0][0]=1;
    short int pr=1,dc=0,d1,d2,tp,tm;
    fru(i,1,n)
    {
        swap(pr,dc);
        f[dc].clear();
        for(auto j:f[pr])if(!gt(j.first,m))f[dc][j.first<<2]+=j.second;
        
        fru(j,1,m)
        {
            swap(pr,dc);
            f[dc].clear();
            for(auto k:f[pr])
            {
                d1=gt(k.first,j-1);d2=gt(k.first,j);
                if(ch[i][j]=='*')
                {
                    if(!d1&&!d2)f[dc][k.first]+=k.second;
                }
                else if(!d1&&!d2)f[dc][k.first+bs[j-1]+bs[j]*2]+=k.second;
                else if(!d1&&d2)
                {
                    f[dc][k.first]+=k.second;
                    f[dc][k.first+bs[j-1]*d2-bs[j]*d2]+=k.second;
                }
                else if(d1&&!d2)
                {
                    f[dc][k.first]+=k.second;
                    f[dc][k.first-bs[j-1]*d1+bs[j]*d1]+=k.second;
                }
                else if(d1==1&&d2==1)
                {
                    tp=0;
                    fru(l,j+1,m)
                    {
                        tm=gt(k.first,l);
                        if(tm==1)tp++;
                        else if(tm==2)tp--;
                        if(tp==-1)
                        {
                            f[dc][k.first-bs[j-1]-bs[j]-bs[l]]+=k.second;break;
                        }
                    }
                }
                else if(d1==2&&d2==2)
                {
                    tp=0;
                    frd(l,j-2,0)
                    {
                        tm=gt(k.first,l);
                        if(tm==1)tp++;
                        else if(tm==2)tp--;
                        if(tp==1)
                        {
                            f[dc][k.first-bs[j]*2-bs[j-1]*2+bs[l]]+=k.second;break;
                        }
                    }
                }
                else if(d1==2&&d2==1)f[dc][k.first-bs[j]*1-bs[j-1]*2]+=k.second;
                else if(i==ex&&j==ey&&d1==1&&d2==2&&k.first-bs[j-1]-bs[j]*2==0)ans+=k.second;
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

  12. Model problems using Minimum Cut

    A problem can be modeled using a Minimum Cut if it involves nodes with binary states where assigning a state incurs a cost, and constraints can be expressed as: 'If node A is in state C, then node B must also be in state C'.