Freaks City

[CTS2024] The Gate of All Beings This is a constructive problem on tree traversal. Observation of large test cases shows the answer does not exceed 3. It is posssible to traverse the entire tree with paths of length at most 3. The answer is typically 0 or 1, except for small trees or star-shaped graphs. For small n (≤ 8), a brute-force search o ...

Monotonic Stack Fundamentals Monotonic stacks enable linear preprocessing to find: Prefix/suffix maximum/minimum positions in sequences Next greater/smaller element positions for each index Problem B3666: Suffix Maximum Positions Given a dynamically growing array, after each insertion, find all suffix maximum indices and output their XOR sum. ...

A. Cosmic End Find a number within a given range that is the product of three distinct primes. Given the small constraitn (upper bound ≤ 100), precompute small primes and check all combinations of three distinct ones. The maximum third prime needed is around 100/(2×3) ≈ 16, so checking primes up to 19 suffices. #include <bits/stdc++.h> us ...

Trie (Prefix Tree) Fundamentals Binary trees consist of nodes where each node holds a value and pointers to left and right children: struct Node { int value; Node* left; Node* right; }; A binary tree node has at most two children. When a tree node can have multiple children, it becomes a multi-way tree. Since the number of children ...

Intersection of Linked Lists Problem Link LeetCode 160 Problem Statement Given the heads of two singly linked lists, headA and headB, return the node at which the two lists intesrect. If there is no intersection, return nullptr. The linked lists must retain their original structure after the function returns. You are not allowed to modify th ...

Problem Description You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Examples Example ...

The algorithm works in three phases: Duplicate each node and insert it immediately after its original Copy the random pointers from original nodes to their duplicates Separate the interleaved lists into original and copy C++ Implementation class LinkedListCloner { public: Node* cloneList(Node* head) { if (!head) return nullptr; ...

0/1 Knapsack Given N items and a knapsack with capacity V, each item can only be selected once. Item i has volume v[i] and value w[i]. Determine which items to select to maximize total value without exceeding the knapsack's volume. Constraints: 0 < N, V ≤ 1000 0 < v[i], w[i] ≤ 1000 Time Complexity: O(N × V) int n, m; int f[100010], w[10 ...

Maximum Product of Splitted Binary Tree Given a binary tree with root node, remove exactly one edge to split the tree into two separate subtrees. The goal is to maximize the product of the sums of both resulting subtrees. Return the result modulo 10^9 + 7. Approach The key insight is that during a depth-first search that calculates subtree sums ...

Problem Statement Given an n×m integer matrix and q queries, each query specifies the coordinates of the top-left and bottom-right corners of a submatrix. For each query, compute the sum of all elements within the specified submatrix. Solution Approach The problem can be efficiently solved using 2D prefix sums. By precomputing the cumulative su ...