Extracting Mathematical Ideas Behind The Problems

Revision en1, by Palestinian_Dream, 2024-01-09 12:30:56

Hello Codeforces, I would really like to start giving examples to illustrate the mathematical ideas behind the problems. I'll begin with simple examples and progress to more challenging ones.

### A. Game with Integers

This one is very straightforward so if $n \mid 3$ then $\mathtt{Vanya}$ wins and the answer is $\mathtt{Second}$ otherwise $\mathtt{Vova}$ wins and the answer is $\mathtt{First}$.

Python Code

### A. Tenzing and Tsondu

Well, Although the statement seems to be complicated but the idea is easy

$\mathtt{Tsondu}$ has $n$ monsters with power units $a_1,a_2,\ldots,a_n$ and $\mathtt{Tenzing}$ has $m$ monsters with power units $b_1,b_2,\ldots,b_n$ , we want to see who'll win the game give that information using a very basic games concept

$\displaystyle \textbf{The player with Highest score wins}$

so we conclude these 3 cases now:-

$\begin{cases} \sum a_i > \sum b_i \rightarrow \mathtt{Tsondu} \\ \sum a_i = \sum b_i \rightarrow \mathtt{Draw} \\ \sum a_i < \sum b_i \rightarrow \mathtt{Tenzing} \\ \end{cases}$
Python Code

### C. Sum in Binary Tree

We can see that every node with value $n$ has $2$ child $2n$,$2n+1$ so we can reversely reach that node by the following form

$\displaystyle \lfloor \frac{x}{2} \rfloor$

so we keep do this step and continue summing until we reach 1

Python Code

### B. Good Kid

By Simple Trying and Following the pattern we can notice that the optimal answer is to choose the smallest non-zero digit but what's the math behind it ?

a good way to prove is to compare the expression such that

$\displaystyle \begin{cases} p_1=a_1 \cdot a_2 \cdot \ldots a_n \\ p_2=(a_1+1)\cdot a_2 \cdot \ldots a_n \\ \end{cases}$

we consider $a_1=\min(a)$ now let's factor $p_2-p_1$

$\displaystyle p_2-p_1= (a_2 \cdot \ldots a_n)(a_1+1-a_1)=(a_2 \cdot \ldots a_n)$

since we want to maximize $p_2$ i.e $p_2=\max(p_2)$ we also want to maximize $p_2-p_1$ , assuming that $a_1=min(a)$

we can see the relation between $\prod_{i=1}^{n}a_i$ and $a_1$ is disproportional , so to maximize the difference $p_2-p_1$ and also $p_2$ , the optimal choice is to minimize $a_1$

$\displaystyle a_1=min(a)$
Python Code

### A. 2023

Well , we have a sequence $b$ that it's product is a constant $2023$ and it's length is $n$ there're $k$ elements removed from the sequence so we need to find any $k$ elements that satisfies , we can take advantage that repetitions are allowed in the sequence $b$ (also in $a$ as well) and one simple pattern is to find if the product of the given sequence $b$ is divisible by $2023$ then we can find an answer otherwise $\mathtt{NO}$ , More Formally an answer is existed if

$\displaystyle 2023 \mid \prod_{i=1}^{n} b_i$

we can take advantage of repetitions-allowed and constructing easily a sequence (Consider $b+c=a$) so our sequence is $c$ since we have $k$ elements $|c|=k$ , we can set $k-1$ elements to $1$ and last element $k_{th}$ element is

$\displaystyle \frac{2023}{\prod_{i=1}^n b_i}$

More Formally

$\displaystyle c=\underbrace{1,1,....,1}_{k-1 \textbf{ ones}},\frac{2023}{\prod_{i=1}^n b_i}$
Python Code

### A. Wallet Exchange

Well ,This example is very simple and personally I think it doesn't require any real analyzing anyway I'll show the math behind it because an implementation solution in $\mathcal{O}(\min(a,b))$ is existed but will give $\mathtt{TLE}$ because $(1 \le a,b \le 10^9)$

You have 2 players : $\mathtt{Alice}$ and $\mathtt{Bob}$ such that : $\mathtt{Alice}$ has $a$ coins and $\mathtt{Bob}$ has $b$ coins , every time we're going to swap wallets

$a \leftrightarrows b$

Every time we're going to decrease exactly $1$ one of the wallets and then exchange them , so consider $(a,b)=(2,3)$ so here's how the process is simulated :-

$\mathtt{Alice}$ chooses to $swap$ the wallets so now $(a,b)=(3,2)$ and decreasing $1$ from $\mathtt{Alice}$'s wallet now the case is $(2,2)$ now again $swap$ we obtain $(1,2)$ after decreasing $1$ from $\mathtt{Bob}$'s wallet again $swap$ and decreasing $1$ from $\mathtt{Alice}$'s wallet now the case is $(0,1)$ , now $\mathtt{Bob}$ will $swap$ so we obtain $(1,0)$ now $\mathtt{Bob}$ can't perform any operation so clearly $\mathtt{Alice}$ Wins

How to generalize the answer for all $(a,b)$ ?

Well, We must play optimally to get a correct answer More formally $\mathtt{Alice}$ is going to start the game.

The game will end when one of the players reaches 0 coins. Let's denote the number of rounds (turns) played by $n$,The total number of coins removed after $n$ rounds is $2n$, At the end of the game, either $\mathtt{Alice}$ or $\mathtt{Bob}$ will have 0 coins. Therefore, the total number of coins they had initially will be equal to the total number of coins removed:

$\displaystyle a+b=2n \rightarrow \frac{a+b}{2}$

Now notice if $(a+b)$ is even then $\mathtt{Alice}$ and $\mathtt{Bob}$ will play \textbf{exactly} $n$ rounds and it becomes $\mathtt{Alice}$'s turn and then we can't do operations anymore so $\mathtt{Bob}$ wins here , but if $(a+b)$ is odd then one player will reach 0 coins one round earlier than the other and this play certainly is $\mathtt{Alice}$

Python Code

### A. Arithmetic Array

we have an array $b$ and we want to achieve the following goal using minimum number of operations :-

$\displaystyle \frac{b_1+\ldots+b_k}{k}=1$

This one is absolutely math and greedy . We'll divide the cases into 3 cases W.R.T Sum of array $\sum b_i$

$\begin{cases} \sum b_i=k \\ \sum b_i < k \\ \sum b_i > k \\ \end{cases}$

Clearly for the first test case , no operations needed because it's already satisfying the condition .

For The Second case for this case we can add one non-negative number that will complete the sum and makes the equation holds and that integer is $(n+1)-\sum b_i$ ,so for this case the answer is always $1$

For the third case : since the sum is larger than the number of elements an optimal choice is increasing the number of elements without changing the sum (appending zeros) , we should append $\sum a_i-n$ zeros.

Python Code

### B. Two Divisors

We're given 2 integers $(a,b)$ such that $a<b$ we need to find a number $x$ ($1 \le x \le 10^9$) such that $(a,b)$ are the two largest divisors of $x$.

Well , we can divide the cases into 2 cases:-

• $b \mod a=0$

in this case since $b>a$ then we can re-express $b$ as $b=ac$ That makes $c=\frac{b}{a}$ and then an optimal answer for that is

$\displaystyle bc=b \cdot \frac{b}{a} \rightarrow \frac{b^2}{a}$
• $b \mod a \neq 0$ consider $c,d$ are the two smallest prime factors of $x$ then $\gcd(a,b)=\frac{x}{c \cdot d}$ then an optimal answer is
$\displaystyle x=bc=b \cdot \frac{a}{\gcd(a,b)}=\text{lcm}(a,b)$
Python Code

### Cardboard for Pictures

We can make a function $f(x)$ which tell us the total area of a cardboard with width $x$ which can be obtained as follows:-

$\displaystyle \sum_{i=1}^{n}(a_i+2x)^2=4nx^2+4x\sum_{i=1}^{n}a_i+\sum_{i=1}^{n}a_i^2=c$

we can rearrange the equation to obtain a quadratic equation with values $a=4n,b=4\sum a_i,c=\sum a_i^2-c$ which leads to quadratic formula that can be solve using quadratic form

$\displaystyle x=\frac{-b+\sqrt{b^2-4ac}}{2a}$
Python Code

### F. Forever Winter

let's denote the central node by $k$ , $k$ is connected with $x$ sub-nodes $(x)\cdot 1=x$ and each sub-node is connected with $y$ ending nodes $x \cdot y = xy$ and of course the central node $k$ (1), since the nodes holding numbers $1,2,3,...,n$ then we can get $n$ in terms of $x,y$ using the previous conclusions we obtain

$\displaystyle n=x+xy+1=x(y+1)+1$

now you can notice if we've another equation we can make a linear system of equations of 2 variables and solve the equations for $x,y$. \ We can notice something special about the graph that : the ending node only appears once and also the count of them is $xy$ since $x$ sub-nodes connected with $y$ ending nodes.

$\displaystyle x(y+1)+1=n$
$\displaystyle xy=count(\textbf{ending nodes})$

by subtracting the system of equations we obtain $(x,y)$

$\displaystyle x=n-count(\textbf{ending nodes})-1$
$\displaystyle y=\frac{count(\textbf{ending nodes})}{n-count(\textbf{ending nodes})-1}$

Now The Solution is completed for all snowflake graphs.\ \

So sometimes we shouldn't do bfs/dfs to get a solution , sometimes simple equations can solve the problem

Python Code

Hope you enjoyed the problems and their solution , Stay tuned for more , I appreciate all suggestions

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 Palestinian_Dream 2024-01-09 12:30:56 11740 Initial revision (published)