Um_nik uploading screen cast on YouTube while the contest is running ? what?

Link

Archive

UPDATE: The video is deleted but this didn't change the fact that there are a good number of guys who copied the code in the last 40 minutes of the contest

Um_nik blog

You Can Find it Here

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}$$$.

for _ in range(int(input())):
    if(int(input())%3==0):
        print("Second")
    else:
        print("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:-

t = int(input())
for _ in range(t):
    tr = input()
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    if sum(a) > sum(b): print('Tsondu')
    elif sum(a) < sum(b): print('Tenzing')
    else: print('Draw')

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

from math import *
for _ in range(int(input())):
    n=int(input())
    a=0
    while(n>0):
        a=a+n
        n=n//2
    print(a)

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$$$

from math import *
for _ in range(int(input())):
    n=int(input())
    x=list(map(int,input().split()))
    x[x.index(min(x))]+=1
    print(prod(x))

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

from math import *
for _ in range(int(input())):
    n,k=map(int,input().split())
    b=list(map(int,input().split()))
    if(2023%prod(b)==0):
        print("YES")
        s='1 '*(k-1)
        print(s+str(2023//prod(b)))
    else:
        print("NO")

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}$$$

def solve():
  a,b=map(int,input().split())
  if(a%2==b%2):
    print("Bob")
  else:
    print("Alice")
for _ in range(int(input())):
  solve()

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.

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if(sum(a)==n):
        print(0)
    elif(sum(a)>n):
        print(sum(a)-n)
    else:
        print(1)

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

from math import *
for _ in range(int(input())):
    a,b=map(int,input().split())
    if(b%a==0):
        print(b*b//a)
    else:
        print(a*b//gcd(a,b))

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

from math import *
def sq(x): return x*x
def solve(a,b,c):
    return (-b+sqrt(b*b-4*a*c))//(2*a)
for _ in range(int(input())):
    n,c=map(int,input().split())
    a=list(map(int,input().split()))
    b=a.copy()
    b=list(map(sq,b))
    qa,qb,qc=4*n,4*sum(a),sum(b)-c
    print(int(solve(qa,qb,qc)))

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

for _ in range(int(input())):
    n,m=map(int,input().split())
    x=[]
    c=[]
    for i in range(m):
        u,v=map(int,input().split())
        x.extend([u,v])
    e1=max(x)-1
    o=0
    for i in range(1,n+1):
        if(x.count(i)==1):
            o+=1
        else:
            c.append([x.count(i),i])
    xs=e1-o
    ys=o//xs
    print(xs,ys)

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