CodeForces – Star Sky

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⁵, 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⁹, 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:

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 –

100000 100000 10

100K stars and 100K views. It’s obvious that the solution should have been rebuilt. From scratch. And some algorithms should be actually used. Like an old school algorithm, or giving a difference between two sets of data, by writing the cumulative result on the new one. Something similar to this one here, about Karen and her Coffee.

The problem is one step more difficult – we do not have our data in a line, but in a Cartesian Coordinate System. Thus, if we always have the sum of the left and the upper (see the black square on the picture), the left and the upper would be containing each the yellow square. Thus, we would have the sums there twice. But, being able to realize this, makes it possible to solve the whole problem using it.

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:

                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

                    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! 🙂

CodeForces – Star Sky

Related posts: