CodeForces.com is one of the reasons why I blog quite often. Last week, in round 427 there was an interesting problem, which I was eager to solve. The problem was described as follows:

*The Cartesian coordinate system is set in the sky. There you can see n stars, the i-th has coordinates (x _{i}, y_{i}), a maximum brightness c, equal for all stars, and an initial brightness s_{i} (0 ≤ s_{i} ≤ c).*

*Over time the stars twinkle. At moment 0 the i-th star has brightness s _{i}. Let at moment t some star has brightness x. Then at moment (t + 1) this star will have brightness x + 1, if x + 1 ≤ c, and 0, otherwise.*

*You want to look at the sky q times. In the i-th time you will look at the moment t _{i} and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates (x_{1i}, y_{1i}) and the upper right — (x_{2i}, y_{2i}). For each view, you want to know the total brightness of the stars lying in the viewed rectangle.*

*A star lies in a rectangle if it lies on its border or lies strictly inside it.*

*Input*

*The first line contains three integers n, q, c (1 ≤ n, q ≤ 10 ^{5}, 1 ≤ c ≤ 10) — the number of the stars, the number of the views and the maximum brightness of the stars.*

*The next n lines contain the stars description. The i-th from these lines contains three integers x _{i}, y_{i}, s_{i} (1 ≤ x_{i}, y_{i} ≤ 100, 0 ≤ s_{i} ≤ c ≤ 10) — the coordinates of i-th star and its initial brightness.*

*The next q lines contain the views description. The i-th from these lines contains five integers t _{i}, x_{1i}, y_{1i}, x_{2i}, y_{2i} (0 ≤ t_{i} ≤ 10^{9}, 1 ≤ x_{1i} < x_{2i} ≤ 100, 1 ≤ y_{1i} < y_{2i} ≤ 100) — the moment of the i-th view and the coordinates of the viewed rectangle.*

*Output*

*For each view print the total brightness of the viewed stars.*

I came up with quite a somehow easily. It was just collecting the data, analyzing it and checking for each star separately whether it was in the given **view. **It was running well for the initial tests, I immediately decided to give it a go:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
class StartUp { static void Main() { List NQC = ReadLineAndParseToList(); int n = NQC[0]; // number of stars int q = NQC[1]; // number of views int c = NQC[2]; // number max brightness List<list> StarsInformation = new List<list>(); for (int i = 0; i < n; i++) { StarsInformation.Add(ReadLineAndParseToList()); } for (int i = 0; i < q; i++) { List ViewInformation = ReadLineAndParseToList(); int TotalBrightness = 0; for (int k = 0; k < n; k++) //per star { if (IsItInside(StarsInformation[k], ViewInformation)) { int StarBrightness = StarsInformation[k][2] + ViewInformation[0]; if (StarBrightness > c) { StarBrightness = StarBrightness % (c + 1); } TotalBrightness += StarBrightness; } } Console.WriteLine(TotalBrightness); } } public static bool IsItInside(List StarInformation, List ViewInformation) { int x1Rect = ViewInformation[1]; int y1Rect = ViewInformation[2]; int x2Rect = ViewInformation[3]; int y2Rect = ViewInformation[4]; int xStar = StarInformation[0]; int yStar = StarInformation[1]; return ((x1Rect <= xStar) && (x2Rect >= xStar) && (y1Rect <= yStar) && (y2Rect >= yStar)); } |

Well, it failed in test number 8 due to time limit. This was the first line input of test number 8 –

1 |
100000 100000 10 |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
using System; using System.Collections.Generic; using System.Linq; class StartUp { static void Main() { List NQC = ReadLineAndParseToList(); int n = NQC[0]; // number of stars int q = NQC[1]; // number of views int c = NQC[2]; // number max brightness int maxC = 11; //max brightness, if we need it +1 for 0 int maxXY = 101; //max coordination elements int[,,] ncp = new int[maxC,maxXY,maxXY]; for (int i = 0; i < n; i++) { int[] readArray = new int[3]; readArray = ReadLineAndParseToArray(); ncp[readArray[2],readArray[0],readArray[1]]++; } for (int i = 0; i <= c; i++) { for (int ii = 1; ii < maxXY; ii++) { for (int iii = 1; iii < maxXY; iii++) { ncp[i, ii, iii] += ncp[i, ii - 1, iii] + ncp[i,ii,iii-1] - ncp[i,ii-1,iii-1]; // all stars from left + all stars from right - stars from diagonal // because they are counted twice and we need to count them once only } } } for (int i = 0; i < q; i++) { int[] readArray = new int[5]; readArray = ReadLineAndParseToArray(); int t = readArray[0]; int x1 = readArray[1]; int y1 = readArray[2]; int x2 = readArray[3]; int y2 = readArray[4]; int answer = 0; for (int ii = 0; ii <= c; ii++) { int brightness = (ii + t) % (c + 1); int starsWithTheBrightness = ncp[ii, x2, y2] - ncp[ii, x1 - 1, y2] - ncp[ii, x2, y1 - 1] + ncp[ii, x1 - 1, y1 - 1]; //x2y2 with sum stars from (1,1) - sum of x to 1 - sum y to 1 + the down square, so we do not remove it twice answer += brightness * starsWithTheBrightness; } Console.WriteLine(answer); } } public static List ReadLineAndParseToList() { return Console.ReadLine().Split().Select(int.Parse).ToList(); } static int[] ReadLineAndParseToArray() { return Console.ReadLine().Split().Select(int.Parse).ToArray(); } } |

Although, it looks like the solution has the complexity of N^3, it is not exactly like it. 🙂 You may want to see, that we are reading the data after the 3 nested loops, thus its ok. And the maxXY is only 100, thus we are not looping a lot 🙂

The whole magic is in the following two lines, which I have tried to comment a bit more:

1 2 |
int starsWithTheBrightness = ncp[ii, x2, y2] - ncp[ii, x1 - 1, y2] - ncp[ii, x2, y1 - 1] + ncp[ii, x1 - 1, y1 - 1]; //x2y2 with sum stars from (1,1) - sum of x to 1 - sum y to 1 + the down square, so we do not remove it twice |

and

1 2 3 |
ncp[i, ii, iii] += ncp[i, ii - 1, iii] + ncp[i,ii,iii-1] - ncp[i,ii-1,iii-1]; // all stars from left + all stars from right - stars from diagonal // because they are counted twice and we need to count them once only |

Thus, I hope that it becomes understandable.

Cheers! 🙂