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}$$$.
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
so we conclude these 3 cases now:-
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
so we keep do this step and continue summing until we reach 1
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
we consider $$$a_1=\min(a)$$$ now let's factor $$$p_2-p_1$$$
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$$$
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
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
More Formally
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
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:
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}$$$
A. Arithmetic Array
we have an array $$$b$$$ and we want to achieve the following goal using minimum number of operations :-
This one is absolutely math and greedy . We'll divide the cases into 3 cases W.R.T Sum of array $$$\sum b_i$$$
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.
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
- $$$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
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:-
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
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
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.
by subtracting the system of equations we obtain $$$(x,y)$$$
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
Hope you enjoyed the problems and their solution , Stay tuned for more , I appreciate all suggestions
good job<3
Nice. Upvoted.
In the solution to 1899A - Game with Integers, I think the winning condition should be $$$3 \mid n$$$ instead of $$$n \mid 3$$$.
this would have been Good bye div4 2023 contest Two Divisiors is hard to me and this problem is closer first steop of this problem and weird fact is that I couldn't solve any of those two
Awesome stuff :)