Editorial for GFSSOC '14 Winter S4 - Stalactites
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Straightforward 3-D Binary Indexed Tree. A 3-D Prefix sum array would have TLE'd, as it is too slow in updating queries. The difficulty of this problem is in coming up with the query formula. You should also note that a 32-bit integer would NOT suffice to store the sum for all the stalactites.
Skills needed: Data structures
Time complexity:
Note: If you do not have any prior knowledge on Binary Indexed Trees, this problem is practically impossible. You can find information about them online, and it is recommended you complete the 2-D BIT problem IOI '01 Mobile Phones before this problem.
Comments