Codeforces Round #697 (Div. 3) My Editorial

Revision en3, by three_nil, 2021-01-25 20:03:39

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)}$$$
E
I guess constraints were there to fool participants towards a dp solution instead of easier combination solution
Let $$${cnt[i]}$$$ be the number of bloggers with $$${i}$$$ follower. Let $$${X}$$$ be the person with least followers in optimal selection. Let $$${p}$$$ be the number of followers of $$${X}$$$. Let $$${k}$$$ be the number of bloggers with $$${p}$$$ followers in the optimal selection. Then the $$${cnt[p] \choose k}$$$.
To find out $$${X~and~}$$$ sort in decreasing order of followers and keep on choosing till $$${sum of followers>=required followers}$$$.
F
We will iterate over max possible length of the array. Let $$${cnt[i]=the ~number ~of ~times ~i ~appears ~in ~the ~array}$$$.
Let $$${dp[i]=the ~length ~of ~maximum ~array ~with ~smallest ~element ~i}$$$.
Now iterate from $$${i=max_n ~to ~i=0}$$$. Do $$${dp[i]+=cnt[i]}$$$ to include elements equal to $$${i}$$$
If $$${dp[i]>0}$$$ then for all factors $$${X}$$$ of $$${i}$$$, $$${dp[x]=max(dp[x],dp[i])}$$$

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)