This blog is my personal reflection on what I have learned in Trie

Thank you to anyone help created the problem

Thank you to anyone reading

Thank for Codeforces support

Note

Problem that mention Standard / Easy means repeating ideas.

Theory

Trie is used for string searching and searching using a limited amount of character each time.
Basically, if for every position you could have x number, you can use Trie to store the answ so it is very powerful.

Template

struct Trie{
    struct Node{
        bool end;
        Node* children[26];
        Node(){
            end = false;
            for (int i = 0; i < 26; i++){
                children[i] = nullptr;
            }
        }
    };
    Node* root;
    Trie(){
        root = new Node();
    }
    void add(string s){
        int p = 0;
        Node* cur = root;
        while (p < s.size()){
            int mychar = s[p] - '0';
            if (cur->children[mychar] == nullptr){
                cur->children[mychar] = new Node();
            }
            cur = cur->children[mychar];
            p++;
        }
        cur->end = true;
    }
    bool find(string s){
        int p = 0;
        Node* cur = root;
        while (p < s.size()){
            int mychar = s[p] - '0';
            if (cur->children[mychar] == nullptr){
                return false;
            }
            cur = cur->children[mychar];
            p++;
        }
        return (cur->end);
    }
};

NOTE

BECAREFUL OF TRIE, IT WILL MLE IF YOU DONT MANAGE THE MEMORY RIGHT.

Explanation

Everytime you add a string, for every position if the character Node has been created then you just go that node otherwise create a new one and do the same thing.
For the find, just go do the same thing as add, and in the end check if there is a string ending there.

Problems that I have done

Problem explanation

PHONELIST

For every string check if there is any node moving out of that node they are in, if there is then its NO, otherwise YES.

WORD COMBINATIONS

For this problem just do normal dp[i] when dp[i] represent amount of ways to build the string from 0 -> i.
For every i run j : i -> n - 1; if string (i..j) is a valid string then dp[j] += dp[i - 1] or 1 if i == 0.

Vasiliy's Multiset

For this problem just create a idk chatgpt called it a dynamic Trie.
To handle max XOR different we give the following function.
Struct node: each node must have 2 children, a running_count, a count amount of number ending and value of this Node.
decompose(x): convert a number into base 2 when a[0] == biggest bit and a[31] = smallest bit.
add(x): do just like template but for each position running_sum += delta, at the end, cnt += delta.
find(x): At every step, do the following:
if there is a number ending here, take max(x ^ val);
if children[current_bit ^ 1] is avaliable go there;
otherwise go to the children[current_bit].

A Lot of Games

This problem we're going to perfom dfs on Trie.
Make a normal Trie but include each node the following: bool dp[2].
dp[0] represent can lose, dp[1] represent can win.
Lets do a dfs: if we say this Node can win, then there must be a children node that cannot win and the same for lose.
At the end we are going to have a certain can_win and can_lose combination for the root.
We do casework below:
if Root.can_win = false, then the Second person always win;
if Root_canwin = true and canlose = true, then the first person can force losing until last round and win the last round, First person win;
if Root_canwin = true and Root_canlose = false, the answer would be k % 2, explanation:
- if the Winning person know that they can force the losing person on the losing person's turn to win so the parity stays the same;
- The winning person could force the win which allow the winning person to keep the parity.

Sausage Maximization

The idea of this problem is still dynamic trie like 3rd problem, for every prefix, create a trie containing a bunch of suffixes and 0, and find max(query of prefix[i], suffix[i]) over all i.

Xor Subsequence (Hard Version)

Amazing problem, seems impossible at first because we need to store 2 queries at the same time which I believe would be impossible (my opinion).
But lets consider the following, at position i is the position where abp+1 ^ bp > abp ^ bp+1, we can fix all the other one to be equal which means that:
The fix positions would be abp+1 ^ bp+1, from 0 -> i - 1, and then for positon we do the following casework:
Let fix_bit = abp+1 ^ bp+1; call bit_node = bit of abp+1 at pos i, and bit_index = bit of bp+1 at pos i.
If bit_node == bit_index:
if bit_node == bit_index == 1, we need a abp where pos i = abp = 0 and bp = 1;
if bit_node == bit_index == 0, abp = 1 and bp = 0 (in pos i).
If bit_node != bit_index:
if bit_node == 1 then we need abp = 0 and bp = 0;
if bit_index == 0 then we need abp = 1 and bp = 1.
So we just add to the Struct of Node a dp[2] to it to store the above parameters and we just go to each position, query lis every time, find max, LIS[i] = query_answ + 1, and then update Trie again.

Yasya and the Mysterious Tree

Pretty good problem, My solution might not be as neat as the other ones.
So we can do the following, store the path from u -> root (root = 1) in the trie and every query, we just need to query path from v -> root ^ x ^ max query(of u -> root) so the part from lca(u,v) gonna cancel out.
To keep this use a dynamic trie and 2 trie to keep one that is static trie and ones not, because if depth[node] % 2 == 0 then u -> root nots gonna change on query 1 and but if its == 2 then its gonna change.
So store one that is static ones not and find the answer each time.