You are not logged in. Please login at www.codechef.com to post your questions!

×

GRIDGM – Editorial

PROBLEM LINK:

Practice
Contest

Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh

DIFFICULTY:

EASY

PREREQUISITES:

2-D Array, Static Array Queries, Prefix Sum

PROBLEM:

We are given a 2-D array A of size N*M, followed by Q queries. In each query, we are given two coordinates (a, b) and (x, y) and we need to find the sum of the elements of the grid between the given coordinates, i.e. within the range (a, b), (a, y), (x, b) and (x, y) inclusive.

QUICK EXPLANATION:

We can solve this problem by constructing a 2-D prefix sum array that can be used to calculate the sum of any rectangular subarray in O(1) time. Each sum in the array corresponds to a subarray that begins at the upper-left corner of the array.

EXPLANATION:

Here the number of queries is very large, hence finding the sum of the elements from (a, b) to (x, y) everytime will cause a TLE. So we need to process the queries efficiently. We can use a prefix sum array for this purpose. Each entry in the array corresponds to the sum of the subarray that begins at the upper-left corner of the array upto that position. This way we can calculate the sum of any rectangular subarray in O(1) time.

In order to build the prefix sum array, we can iterate through the PRE array in order and calculate the sum as PRE[i, j] = PRE[i, j-1] + PRE[i-1, j] – PRE[i-1, j-1] + A[i, j].

Now, to find the sum of the rectangular subarray starting from (a, b) upto (x, y) we can simply find the value of sum = PRE[x, y] – PRE[x, b-1] – PRE[a-1, y] + PRE[a-1, b-1].

AUTHOR'S AND EDITORIALIST'S SOLUTIONS:

Author's and editorialist’s solution can be found here.

This question is marked "community wiki".

asked 08 Oct, 15:13

horsbug98's gravatar image

4★horsbug98
3236
accept rate: 21%

edited 11 Oct, 17:17

admin's gravatar image

0★admin ♦♦
19.6k349497539

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×199
×75
×75
×4
×4
×4
×4

question asked: 08 Oct, 15:13

question was seen: 110 times

last updated: 11 Oct, 17:17