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

• PHONELST
• Word Combinations
• Vasiliy's Multiset
• A Lot of Games
• Sausage Maximization
• Xor Subsequence (Hard Version)
• Yasya and the Mysterious Tree

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.

Additional Pratice

• CF 888G
• CF 817E
• CF 979D
• CF 1625D