Editorial for OTHS Coding Competition 2 P4 - Magic Barrier

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: Ivan_Li, htoshiro

Subtask 1:

The first subtask can be brute forced by checking within the range of each query, and identifying if the queried value is present.

Time Complexity: \mathcal{O}(NMQ)

Subtask 2:

Notice that it is mentioned in the problem statement that all values are unique. Thus, we can store the coordinates of each value present in the original grid using a HashMap. For each query, we can retrieve the coordinates of the value from the HashMap, and check if the coordinates are within the range of the given query.

Note that in languages such as Java, it is more optimal to use HashMap compared to TreeMap.

In Python, a dict can be used, and in C++, an unordered_map or map can be used.

Time Complexity: \mathcal{O}(NM + Q) or \mathcal{O}(NM + Qlog(NM))

Comments


  • 0
    Saikat  commented on Oct. 3, 2024, 5:01 p.m.

    I missed that the grid consists of unique integers and was not able to solve it. How would the problem be solved if the grid did not have necessarily unique numbers ?


    • 0
      Kirito  commented on Oct. 5, 2024, 2:46 p.m. ← edited

      Off the top of my head, you can process the queries offline, by batching them according to their value of k. The problem then reduces to 2d range sum queries, which you can do with coordinate compression and a PSA.

      You should end up with something that looks like \mathcal O((NM + Q)\log(NM) + Q\log Q).


    • 0
      htoshiro  commented on Oct. 4, 2024, 1:03 p.m.

      If the grid is sorted, you can use a Binary Search approach.