---

Today was a terrible day. I had two papers today - both mathematics paper and both level 4000 modules. I was terribly slaughtered as I couldn't even do most of the paper (40% for the first and 50% for the second). This experience reinforces my opinion that it is useless to study for mathematics papers as I think it does not help at all.

I have always wondered how do we know whether we've learned a topic properly. Of course, examinations are not a good gauge of our grasp of the topic, but is it the best yardstick that we have? Or are there better means? Also, is there really a need to know how well we've learned a topic?

My journey so far taught me that there is a need for someone to guide you for mathematics as it is difficult to learn by reading mathematics textbook (One professor mentioned that reading mathematics is difficult. It is not like reading a novel - you need to think). Having a lecturer going through the topic with you speeds up the whole learning process. Examinations are good in the sense it points out to you where you've not covered properly in your studies. However, once the examinations are over, we lack the motivation to fix this "problem". Nevertheless, we cannot always rely on people to guide us as the future is uncertain.

I am extremely thankful to all my professors and teachers who have guided me so far. Thank you.

Hello November

Hello November!

I guess for once I should write about a problem I've solved with my team mates in a recent contest. This problem is interesting because it was not expected to run in time limit but it did (probably because the test data for the problem is randomly generated rather than specialised test data designed to break algorithm I have listed). I know no one will be interested but I don't care.

Given an array of integers A of size at most 200,000 (1 <= A[i] <= 10,000) and Q queries (Q <= 15,000) where each query is of the form l, r. For each query, find the minimum |A[i]-A[j]| where l <= i, j <= r.

Now, if we are to find the maximum absolute difference, it will be easy as we just need to find the maximum and minimum integer in the interval. Each query can be easily solved by using a segment tree (with segment tree, we can even support a dynamic version) or dynamic programming in O(log n).

For the above question, I have no idea how to do it except by sorting the numbers in the interval and doing a linear scan. We realised that the range of A[i] is actually quite limited. So, if the difference of l and r is large ( > 10,000), by pigeonhole principle, the answer for the query is 0. For the other case, we just did counting sort to sort the elements in the interval and followed by a linear scan. A rough estimate that we had was that this algorithm will take at least 150 million operations on the worst test data (A = 1,2,...,10,000 with 15,000 queries of l = 1 and r = 10,000). There is supposed to be 10 test cases for this question. However, we managed to get it accepted at 4h 38min and that brought us to rank 5 in the contest. It is not too bad given our lousy start and our extremely large number of wrong submissions to problem A.