CSES Subtree Queries

You are given a rooted tree consisting of n nodes. The nodes are numbered 1,2,…,n, and node 1 is the root. Each node has a value.

Your task is to process following types of queries:

1. change the value of node s to x

2. calculate the sum of values in the subtree of node s

Constraints

$1\le n, q \le 2 \cdot 10^5$
$1≤a,b,s≤n$

$1≤v_i,x≤10^9$

CSES Exponentiation II

Problem : Find the value of $(a^{b^c})mod(10^9+7)$ where $1\le n\le 10^5$ and $1\le a,b,c \le 10^9$

In order to solve this problem, we need to understand the Fermat's little theorem:

$(a^p\equiv a) mod(p)$ Where p is a prime number.

CSES Tree Matching

Tree Matching solved with dynamic programming

Let's define :

$dp(P,0)$ : The max matching number that DOES NOT INCLUDE node P.

$dp(P,1)$ : The max matching number that INCLUDES node P.

Naive Bayes Classifier VS Logistic Regression

Both classification models are linear functions of features

Joint Distribution VS Conditional Distribution

Naive Bayes models the joint distribution:  $P(X,Y) = P(Y)P(X|Y)$

Logistic Regression models the conditional distribution: $P(Y|X)$

Correlated VS Independent features

Speeding up numpy: Cupy

   Numpy is a widely used python library. It runs on CPU mainly. Sometimes machine learning deal with a huge amount of data set. Cupy is a similar library that works on cuda GPUs. While running on GPU, it mainly speeds up the arithmetic operations on large size arrays.

Installation of Cupy:
https://cupy.chainer.org/

Linear regression: Ridge regression

Why should we add a $\lambda$ to the matrix?
1. To reduce the value of the weights $\omega$.
2. Make $X^{T}X$ invertible.
3. Prevent overfitting

Why will $X^{T}X$ become not invertible?

$$\omega_{LMS}=(X^{T}X)^{-1}X^{T}y$$

1. Data points of X is less than the dimension of $\omega$
2. Columns of X are not linear independent. Such as: a column is a duplicate of one of the features, a column is the scaled version of another. Those columns are dependent between each others.
Example:

Linear regression: Polynomial basis function

From the previous post, a first order model fitted the data like this:

To fit a known data better, we need more information and a more complex model. Here is a first order model used in the plot above:

$$y=ax+b$$

Let's turn it into second-order model:

$$y=ax^{2}+bx+c$$