SPOJ GM Plants IOPC1207 Problem

Hello guys.

This problem has been asked on Codechef discuss a few times in the past, but I didn’t find a really convincing explanation. The problem in question is

I have a few questions:

  1. The problem asks us to find no. of red plants in the region (x1, y1, z1) to (x2, y2, z2) where these co-ordinates are diagonally opposite points in space. Do we need to find the red plants in the plane? bounded by these points?

  2. If the answer to the question is yes, the queries in this question only ask us to modify plants one axis at a time(x, y or z). Doesn’t all the plants modified will be on either of the three straight lines of the cube? (x, 0, 0), (0, y, 0), or (0, 0, z)? So won’t the answer be zero for all the queries with non zero (x, y, z)? Have I understood the problem wrongly?

  3. If I have understood it wrongly, the one in the solution booklet says, the problem can be decomposed into 3 indvidual 1-d queries and provides a formula r1r2r3 +r1g2g3 +g1r2g3 +g1g2r3. where r1, r2 and r3 are the red plants on individual axis of the cube(similar argument for all the g’s). I am not able to visualize the problem precisely.

I know the question is too long, but I really need to learn how to think before getting my hands to code. Any insight will be really helpful. Thanks :slight_smile: