### three_nil's blog

By three_nil, history, 5 weeks ago,

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

### G

We will iterate over max possible length of the array. The main concept is that if we have a beautiful array of with smallest element ${x}$ and ${y}$ is a factor of ${x}$ then after adding ${y}$ to the array it will still be beautiful. To notice this take any example and sort them in ascending order. Now since ${x}$ is the smallest, it must divide every element of the array and since ${y}$ divides ${x}$, it will also divide all the elements 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])}$.
${max_{len}=max(dp[i],max_{len}}$
${ans=n-max_{len}}$

• +22

 » 5 weeks ago, # |   +17 Great effort and congrats on solving all problems! I can help you with $\TeX$ if you want to.
•  » » 5 weeks ago, # ^ |   0 Oops... There is no editorial for Problem F)
•  » » » 5 weeks ago, # ^ |   0 Maybe it is just too obvious for the author of this blog entry)