Posts

Large language models have had a profound impact in the last three years. Here are some notes on how they have changed my life so far: Emotions AI has helped me eliminate the fear of the unknown. With the knowledge that there is an accessible to learn anything, I have grown more secure and confident in my existing abilities. The advent of search engines must have had a similar effect in the 1990s. I have not used AI as for emotional support and guidance, but I support the idea and think it can be emotionally healthy if done in a controlled way. ...

Today we take a look at the problem ABC241 H. We are given $N \le 16$ distinct numbers $A_1, \cdots, A_N$ and a sequence describing the amount of supply of each number: a sequence $B_1, \cdots, B_N$ where $B_i$ refers to the supply of the number $A_i$. The score of a combination of $M$ chosen numbers is the product of the numbers. That is, suppose we pick $C_i$ occurences of the $A_i$ where $0 \le C_i \le B_i$ and $\sum C_i = M$, then $\text{score}(C) = \prod_{i = 1}^{N} A_i^{C_i}$. The objective is to find the sum of scores over all possible valid combinations. ...

Today I’ll discuss a probability problem from CodeChef. The problem is as follows: we have an $N$-bit number $S$ which is initially $0$. At each step, we pick an $N$-bit number $X$ uniformly randomly and set $S := S \mid X$ (the symbol $\mid$ denotes bitwise-or). The process terminates when $S$ becomes $2^N - 1$ (that is, it is impossible to increase it any further because every bit is 1). What is the expected number of steps until termination? ...

Let’s look at this math problem from the recent AIsing Programming Contest 2020 on AtCoder. The problem is to compute the sum of \[\tag{1}(a_2 - a_1)(b_2 - b_1)(c_2 - c_1)(d_2 - d_1)(e_2 - e_1)\] for all tuples such that \[\tag{2} a_1 + a_2 + b_1 + b_2 + \cdots + e_1 + e_2 \le N\] where $$\tag{3} 0 \le a_1 < a_2, ~ 0 \le b_1 < b_2, \cdots,~ 0 \le e_1 < e_2$$The constraint $N \le 10^9$ makes it worse. ...