SIMO Retiree Blog

(Glen here.) Recently, there was some discussion about this year's IOI in a group chat, and Ker Yang remarked that the first task, " Souvenirs ", was basically a math question. Of course, I had to have a look. The original description is pretty long, so here's a rewriting in a more math olympiad style: Sheldon is buying french fries from a fast food restaurant, which sells fries in $N$ different sizes (with packagings labelled from largest to smallest from $0$ to $N-1$), with integer costs $P_0 > P_1 > \ldots > P_{N-1} > 0$. To buy fries, Sheldon can pay $\$M$ where $M$ is a positive integer, and then define a sequence $i_1,i_2,\ldots$ as follows: $i_1$ is the smallest integer such that $P_{i_1}\le M$, and in general, $i_k$ is the smallest integer $>i_{k-1}$ such that $P_{i_k} \le M - P_{i_1} - \cdots P_{i_{k-1}}$. If no such $i_k$ can be defined, the sequence terminates. Then, Sheldon receives the fries with labels $i_1,i_2,\ldots$ along with his chang...

(David here.) In this post I want to share a really interesting factoring algorithm that I learnt while taking an advanced cryptography class , and it will serve as a good springboard into talking about the mathematics and algorithms of lattices.

(Yu Peng here) Sometimes, you feel like you should be on the right track in solving a problem, but your solution falls short a little, due to issues like having a suboptimal bound, or having a condition you need but isn't true. At other times, you could just be struggling to find the optimal construction. At such times, it would often do you good to take a step back, and think about how you can optimise your solution.

Wee Kean here. Happy New Years Eve! Lately, my only interaction with math has been through doing Project Euler. So... here's some cool things I've learnt! Unfortunately, there is hardly any structure to this blogpost so I apologize if this comes off as verbal diarrhea.