nskybytskyi's blog

By nskybytskyi, 3 years ago, In English

my solutions on github, variable names are mostly reasonable so that you can read it alongside explanations. The screencast with video editorial is coming soon on my YT channel

A. Odd Divisor

A number has an odd divisor iff it is not a power of two.

B. New Year's Number

$$$2020 x + 2021 y = n$$$. Mod out by $$$2020$$$, you get $$$y = n \% 2020$$$. Then simply check that $$$x = (n - 2021 y) / 2020$$$ is nonnegative.

C. Ball in Berland

We have a bipartite graph. All pairs of pairs are good except for the pairs that share a common vertex. There are $$$\binom{k}{2}$$$ pairs in total and $$$\binom{\deg v}{2}$$$ pairs that share a vertex $$$v$$$, hence the answer is $$$\binom{k}{2} - \sum_v \binom{\deg v}{2}$$$.

D. Cleaning the Phone

Among the applications of equal importance we want to delete the heaviest ones first, hence it makes sense to sort. We will delete some prefix of important apps and some prefix of regular apps, so it makes sense to compute prefix sums of both. The for every given important prefix we can find the corresponding regular prefix with a binary search because prefix sums are sorted.

E. Advertising Agency

Some bloggers are marginal (equal to $$$k$$$-th in sorted order) and some are not. If a blogger is strictly better than marginal, then we take it, if it is strictly worse then we don't, and among marginal we can choose for the remaining places. The answer will be some binomial coefficient. To compute them quickly you can precompute factorials.

F. Unusual Matrix

If you flip all rows and all columns nothing will change. In linear algebra, such a set of operations is called linearly-dependent. It means that you can exclude one operation wlog. Let's exclude the first column so that we will never flip it. THen judging by its entries we can determine which rows we have to flip. Once we flipped the rows we can determine which columns (except for the first one) we have to flip. Then we check if we succeeded or not.

G. Strange Beauty

dp[i] will count the max number of elements in a good set whose max element is $$$i$$$. Then dp[i] = max(dp[i/d] + f[i] for d|i), where $$$d\mid i$$$ means that $$$d$$$ is a divisor of $$$i$$$, and f[i] is the frequency map of the array. To ind divisors quickly one can run Erathospenes' sieve once.

Takeaways: prewritten NT helps with speed

  • Vote: I like it
  • +34
  • Vote: I do not like it