Yet Another problem

We are given a linear array of n numbers e.g.

1 3 7 2 9 8 5

is a linear array of 7 numbers.

We are given m queries, each of the form:

a b

Basically, 2 integers a and b, a <= b. We want to know between the ath and bth element of the array, what the smallest number is.

For example, if a is 2 and b is 5, the range we are interested in (for the above array) is:

3 7 2 9

since 3 is the 2nd element of the array and 9 is the 5th element.

The answer would be 2, which is the smallest number.

We wish for O(n log n) preprocessing and O(1) query, so that for m queries on n numbers, the time complexity is O(n log n + m). [ I guess O(n^2) preprocessing is REALLY REALLY easy ].

Space required: No more than O(n log n).

Thanks to Ivo and Velin for the solution.

It's snowing

-nt-

More problems

This is a pretty standard one:

Given an n x n matrix containing only 1s and 0s, find the area of the largest rectangle (with sides parallel to the ends of the matrices) that contain only 1s.

Time Complexity required:

O(n^3) is trivial.

If anyone has an O(n^2) solution, please tell me!

The solution I have now is O(n^2 log n).

Problem of the day

A sequence of integers is called a "minimum-centered" sequence if it is of odd length and the middle element is the smallest.

For example, 12 13 8 9 10 is a minimum-centered sequence, so is 9 7 3 1 8 6 10. However, 7 2 1 3 5 2 8 isn't.

Given an array of numbers, find the longest consecutive sequence of numbers in this array that is minimum-centered.

Alternate easier problem: Find if there exists a minimum-centered sequence of a given length in this array.

Complexity needed: O(n) [ linear ] for both problems. Of course, if you can come up with an O(n) solution for the second one, there is an easy O(n log n) solution for the first one based on binary search, but that's not we're looking for.

Credit to Daniel for informing me about this problem and its somewhat elegant solution.

Another year passes by

In many civilizations, the age 21 is a sign of maturity. For example, 21 is the legal drinking age in many parts of the USA.

But does it really mean anything? Maturity is not something gained overnight, on the day when you turn 18, 19, 20, 21, or any age for that matter. Maturity is something that is gained gradually over time, as you experience more of the world around you.

Gaining maturity is a painful process. It is the process of losing your childhood innocence. In the real world, childhood altruistic ideals such as sharing and helping often play a bit part behind more materialistic beliefs. But deep inside us, there is a part that wishes that we could live these ideals again. In a way, maturity isn't all that good. Just because we are a certain age, should we say we throw these utopian ideals away?

Furthermore, maturity is subjective. What is mature behavior to one person can seem childish and selfish to another. Mature behavior, contrary to popular belief and its very definition, can defy logic. In this sense, who are we to say what is mature and what is not? Maturity is often defined by societal norms. What happens, then, when there is a clash of two vastly different societies?

In any case, happy 21st. To people on this blog turning (or turned) 21 today, tomorrow, and within the next two weeks, and to all those out there as well. Perhaps this issue of maturity will give you something to think about.

Columbus day weekend

It's a 4 day weekend here! (Monday and Tuesday holiday - most other schools only have monday off I believe).

Many professors here don't respond if you call them "Professor". They simply aren't used to it. I'm not really used to calling them by their first name, as everyone else here does.

As my freshman advisor (and he's a rather famous person) says:

"Rule number one: Call me [first name omitted], not professor."

"Rule number two: There is only one rule."

Bargain of the day

12 cans of Minute Maid lemonade for US$2.

That's less than S$0.30 a can (at current exchange rates).

It's quite easy to lose weight here - just shiver your calories away.

Unfortunately, that's not my goal here.

Reminder to self: Wear shoes, not sandals, unless you like freezing feet.