BAKE - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

This problem presents a typical OLAP problem scenario with multiple dimensions with each having an hierarchy of levels. In this problems the dimensions were product, location, gender and age. The level hierarchy for the location dimension, for example, is country->province->city->region.

The expected solution for this is to pre-aggregate the sale information at different levels of dimensions so that queries can be efficiently answered. The combinations of levels of each dimension at which a query can be asked are as follows

product_id.product_size, country.province.city.region, gender, age
product_id.product_size, country.province.city, gender, age
product_id.product_size, country.province, gender, age
product_id.product_size, country, gender, age
product_id, country.province.city.region, gender, age
product_id, country.province.city, gender, age
product_id, country.province, gender, age
product_id, country, gender, age

So, pre-aggregate the data at all these levels. For example, say for the combination {product_id, country.province.city, gender, age} there is a 4-dimensional matirx, say mat, where mat[PID][CITYID][GID][YRS] keeps the totals sales for the product with id PID, in city with id CITYID, done by person of gender GID of age YRS. Similarly, maintain a matrix for the the combinations because a query can only ask about sale information at these levels. Hence, for a single input, you will have to update multiple matrices at all the appropriate matrices.

But because for the fourth dimension, i.e. age, there can be range queries that is give me the sum for age START _ AGE to END _ AGE. So, for the fourth dimension, I used Binary Indexed Tree (BIT) to maintain range aggregates. They are easy and efficient to both update and query.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.