FastPrep
Problem · String

Hidden Artifacts

Learn this problem
● MediumIMC logoIMCFULLTIMEOA

Problem statement

An archaeological site is represented by an n-by-n grid. Rows are numbered from 1 through n, and columns are labeled from A through the nth uppercase letter. A cell is written as its row followed by its column, such as 9C.

Each hidden artifact occupies an axis-aligned rectangular group of cells. Artifacts do not overlap, and each artifact has area at most 4.

The string artifacts contains comma-separated artifact descriptors. Each descriptor has the form topLeft bottomRight. The string searched contains distinct searched cells separated by spaces.

An artifact is fully reconstructed when every cell it occupies has been searched. It is partially found when at least one, but not all, of its cells have been searched. Return an integer array [fullyReconstructed, partiallyFound].

Function

findHiddenArtifacts(n: int, artifacts: String, searched: String) → int[]

Examples

Example 1

n = 4artifacts = "1B 2C, 2D 4D"searched = "2B 2D 3D 4D 4A"return = [1,1]

The vertical artifact from 2D through 4D is fully reconstructed. The 2-by-2 artifact has only cell 2B found, so it is partial.

Example 2

n = 3artifacts = "1A 1B, 2C 2C"searched = "1B"return = [0,1]

Only one cell of the first artifact has been found, and the single-cell artifact at 2C has not been found.

Constraints

  • 1 <= n <= 26
  • Every artifact descriptor names the valid top-left and bottom-right cells of an axis-aligned rectangle.
  • Each artifact occupies at most 4 cells.
  • No grid cell belongs to more than one artifact.
  • Every cell in searched is valid and appears at most once.
  • Artifact descriptors and searched cells may appear in any order.

More IMC problems

drafts saved locally
class Solution {
    public int[] findHiddenArtifacts(int n, String artifacts, String searched) {
        // Write your code here.
        return new int[0];
    }
}
n4
artifacts"1B 2C, 2D 4D"
searched"2B 2D 3D 4D 4A"
expected[1,1]
checking account