Problem Statement: Paint Ball

Amrita has placed N white drawing sheets (represented as rectangles) on a table in her garden. Some sheets lay on top of others, but none of the sheet borders intersect (meaning they are either completely disjoint or strictly nested).

Her brother fires M paintballs of various colors at the sheets. Due to the force of the gun, once a paintball hits a sheet, the color spreads to all of the sheets beneath it.

Given the coordinates of the sheets and the paintballs, write a program to output N lines, where the ith line contains the number of unique colors spread on the ith sheet.

Input Format:

The first line contains N (number of sheets) and M (number of paintballs).
The next N lines contain four integers: P_i, Q_i (lower-left corner) and R_i, S_i (upper-right corner) of the ith sheet.
The next M lines contain three integers: X_j, Y_j (landing coordinates) and K_j (color label) of the jth paintball.

Example Summary:

If a sheet is placed from (1, 1) to (4, 5) and a paintball of color 1 hits at (3, 2), the sheet receives color 1. If another sheet is placed underneath it, the color spreads to that nested parent sheet as well.

ADD COMMENT • link 8 days ago Sarthak • 10

Entering edit mode

Problem 1 Paint Ball Solution

Topics Involved / Prerequisites

2D Geometry (Coordinate checking)
Hash Sets

Overview

Because the sheets are strictly nested or disjoint, a paintball hitting a specific coordinate will penetrate and color every single sheet that encompasses that exact point.
We can determine which sheets are hit by simply checking if the paintball's coordinates fall within each sheet's geometric boundaries.
By using a hash set for each sheet, we can effortlessly collect the colors it receives and automatically ignore any duplicate color hits.

Approach

1. The Geometric Intersection

This is a fantastic logic puzzle that tests your ability to simplify physical rules into code! Since a paintball's force causes the color to bleed through to all sheets beneath the impact point, we don't actually need to build a complex 3D or nested tree structure. Any sheet that contains the (X, Y) coordinate of the paintball within its rectangular bounds is guaranteed to be hit by that paintball.

2. Counting Unique Colors

We can create an array of Hash Sets, one for each of the $N$ sheets. We loop through every paintball, and for each paintball, we loop through every sheet. If the paintball's (X, Y) coordinates are $\ge$ the bottom-left corner and $\le$ the top-right corner of a sheet, we add the paintball's color to that sheet's Hash Set. Because Hash Sets inherently reject duplicate values, the final size of each set will perfectly equal the number of unique colors on that sheet.

Code Implementation (Pseudocode)

function calculatePaintballColors(N, M, sheets, paintballs):
    // sheets[i] contains bounds: {P, Q, R, S} (lower-left to upper-right)
    // paintballs[j] contains: {X, Y, K} (coordinates and color)
    
    // Create an array of Hash Sets to store unique colors for each sheet
    create array of Hash Sets 'colorsOnSheet' of size N
    
    for each ball in paintballs:
        x = ball.X
        y = ball.Y
        color = ball.K
        
      
        for i from 0 to N - 1:
            P = sheets[i].P
            Q = sheets[i].Q
            R = sheets[i].R
            S = sheets[i].S
            
            // If the paintball coordinates fall inside the sheet boundaries
            if x >= P AND x <= R AND y >= Q AND y <= S:
                colorsOnSheet[i].insert(color)
                

    for i from 0 to N - 1:
        print(colorsOnSheet[i].size())

Time Complexity

Time: O(N*M) - We compare every single paintball against the boundaries of every single sheet.
Space: O(N* C) - Where C is the maximum number of unique colors a single sheet can receive, stored in the hash sets.

ADD REPLY • link 8 days ago

Sarthak • 10