Codeforces Round #697 (Div. 3) My Editorial

Revision en1, by three_nil, 2021-01-25 19:46:33

A
The only numbers which do not have a odd multiple are powers of $$${2}$$$, i.e. numbers of form $$${2^x}$$$ where $$${x>=0}$$$
You can create an array $$${B}$$$ of size about 50 such that $$${B[0]=1 ~and ~B[i]=B[i-1]*2}$$$ for $$${i>=1}$$$ and check if the given number is equal to any element of $$${B}$$$. Don't forget about overflow while multiplying with 2.
B
If there exists a answer, $$${n~=~X*2020+Y*2021}$$$ where $$${X>=0 ~and~ Y>=0}$$$. Just iterate over $$${X}$$$. Let $$${m~=~n-X*2020}. If $$${m%2021==0}$$$ answer exists and if $$${m<0}$ break the loop.
C
Create two arrays $$${cnt_{boys}~and~cnt_{girls}}$$$ which maintains in how many pairs is a girl and boy involved.
Now iterate over all given one-boy-one-girl pairs. Let the current pair contain boy numbered $$${X}$$$ and girl numbered $$${Y}$$$. Their partners can be the other pair which does not involve the girl $$${Y}$$$ and boy $$${X}$$$, i.e. $$${(k-1)-(cnt_{boys}[X]-1)-(cnt_{girls}[Y]-1)}$$$.
$$${k-1}$$$ because this paired can't be paired with itself and $$${(cnt_{boys}[X]-1)-(cnt_{girls}[Y]-1)}$$$ because this pair is also counted in $$${X's~and~Y's}$$$ appearance.
You need to divide the final answer by two since each pair is counted twice.
D
This one was a very standard problem.
Make two array $$${a~and~c}$$$ where $$${a}$$$ contains the regular apps and $$${c}$$$ contains important apps. Now sort apps in $$${a}$$$ and $$${c}$$$ in descending order of their memory. It can be proved that between two apps of same importance it is better to remove the one with more memory.
Now iterate over number of apps of regular apps. Let the number of regular apps in current iteration $$${x}$$$. Let $$${sum_a~=~sum ~of ~first ~x ~elements ~of ~a}$$$. Now find out how many apps are required from $$${c}$$$ to create a sum $$${>=m-sum_a}$$$. Let $$${y}$$$ such minimum apps. Then $$${ans=min(ans,x+2*y}$$$

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English three_nil 2021-01-25 20:13:59 574 Tiny change: '-max_{len}$}' -> '-max_{len}}$' (published)
en3 English three_nil 2021-01-25 20:03:39 255
en2 English three_nil 2021-01-25 19:58:46 707 Tiny change: '\choose k}.<br> ' -> '\choose k}$.<br> '
en1 English three_nil 2021-01-25 19:46:33 1883 Initial revision (saved to drafts)