Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Extracting Mathematical Ideas Behind The Problems

Правка en1, от 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

Теги math

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Palestinian_Dream 2024-01-09 12:30:56 11740 Initial revision (published)