imeanup

A tree of n nodes is an undirected connected graph having (n - 1) edges. Given an undirected tree comprising of tree_nodes number of nodes numbered from 0 to tree_nodes - 1, and rooted at node 0. Each node has an initially binary value (0 or 1) represented by the array initiall, and an expected binary value represented by the array expected.

The following operation can be performed on the tree any number of times:

• Pick a node u and flip its value. Also, flip the value of all the nodes v in the subtree of u if v % 2 = u % 2. A node v lies in the subtree of u if u lies on the path from v to root. Flipping the value of a node means flipping its binary value, i.e., from 0 to 1, and vice versa.

The tree is represented by the arrays tree_from[] and tree_to[] where tree_from[i] is connected to tree_to[i] via an edge for $0 \leq i < tree \_ nodes - 1$. Find the minimum number of operations needed such that the final binary value of each node becomes equal to the array

imeanup

Question

Santa and Banta are playing a game of letters. The rules are as follows:

• Initially they have a string consisting of lowercase english alphabets only.

• Each of them take turn.

• In each turn, a player removes some alphabets from the string (at least one).

imeanup

Question

Write a recursive function named stretch that replaces each single binary tree node with multiple nodes with smaller values. Your function accepts two parameters: a reference to a TreeNode pointer representing the root of a binary tree (see reference sheet), and an integer "stretching factor" $K$. Your function should replace each node $N$ with $K$ nodes, each of which stores a data value that is $\dfrac{1}{K}$ of $N$'s original value, using integer division.

The new clones of node $N$ should extend from their parent in the same direction that $N$ extends from its parent. For example, if $N$ is its parent's left child, the stretched clones of $N$ should also be their parent's left child, and vice versa if $N$ was a right child. The root node is a special case because it has no parent; we will handle this by saying that its stretched clones should extend to the left.

For example, suppose a variable named root refers to the root of the tree below at left. If we

imeanup

Maximum displacement

Given a $1-D$ lane, you can move one step ahead (denoted by S) or move one step back (denoted by R). You are given a string of commands and an integer N.

Calculate the maximum displacement that you can achieve from the starting point after changing exactly $N$ commands in the string and executing them.

Function description

Complete the Game() function. This function takes the following 2 parameters and returns the required answer:

• Str: Represents the string containing the commands
• N: Represents the number of commands that must be changed

imeanup

Patterns

---

Minimum (Maximum) Path to Reach a Target
Distinct Ways
Merging Intervals
DP on Strings
Decision Making

Minimum (Maximum) Path to Reach a Target

imeanup

Problem 1

There is a graph with $N$ nodes from $0$ to $N-1$.

For every two nodes $X$ and $Y$, where $X < Y$ there is an undirected edge between $X$ and $Y$ with weight $X ^{\wedge} (X+1) ^{\wedge} \ldots ^{\wedge} Y$. This means that there are $N\times \dfrac{(N-1)}{2}$ weighted edges.

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles, and with the minimum possible total edge weight.

The value of an MST is defined as the sum of edge weights of edges used in MST.

Find the value of MST of the given graph.

imeanup

Brute-Force

Approach:

• Calculate the parent and depth of all nodes in the tree using depth-first search (DFS).
• For each LCA query:
  1. Ensure both nodes have the same depth by moving the deeper node upwards.
  2. Move both nodes up simultaneously until they meet at the LCA node.

Complexity

imeanup

"""
CLRS: Chapter 9
"""


class Pair:
    def __init__(self):
        self.min = 0
        self.max = 0

imeanup

# Page 192 COUNTING-SORT(A, B, k)


def COUNTING_SORT(A, B, k):

    """
    let C(0...k) be a new array

    for i = 0 to k
        c[i] = 0

imeanup

from random import shuffle

''' Bubble sort is popular but inefficient sorting algorithm.

CLRS 

*BUBBLESORT(A):
for i = 1 to A.length - 1
    for j = A.length downto i + 1
        if A[j] < A[j - 1]