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


Help! I need to solve a question with time complexity less than n^2

King Color died and left 3 princes behind Red (22 years old), Green (21), and Blue (20). They inherited a huge piece of land with rectangular shape; the three children had a dispute on how to divide the land between them, until their father’s advisor suggested to use the following method: He partitioned the land into n vertical stripes of random lengths: X1, X2, … Xn, meters and n horizontal stripes of random lengths Y1, Y2, …, Yn meters. These stripes split the land into n x n rectangles. The intersection of vertical stripe i and horizontal stripe j has code number (i + j) mod 3, and hence is given to the prince with the same first digit in his age. For example area X1 Y1 has the code (1+1)%3 = 2, hence it is given to prince Red (22), area Y6 X4 has the code 1 hence it is given to prince Green (21). Your task is to calculate the area of land given to each prince.

The input consists of several problem instances, each starts with the integer n on the first line, followed by two lines each has n integers for the values of X1, ... , Xn, separated with single spaces, followed by the values of Y1, ... , Yn on the next line separated with single spaces. Then next problem instance follows starting with a new n. Problem instances terminate when n = 0. Problem boundaries are: 3≤ n≤ 250000 1≤Yi ,Xi ≤10

asked 20 Sep '18, 16:44

sara_mo's gravatar image

accept rate: 0%

edited 21 Sep '18, 11:04

I think the key observation is:

Consider a single horizontal stripe. Every third piece belongs to respective color, ...BGRBGRBGR.... For this row you'll have some total for red, green and blue on the form: $r\times Y_1$, $g\times Y_1$ and $b\times Y_1$.

What changes for the next line? Depending on $n$ the color pattern either stays in place or is shifted left or right. You can use the previous $r$, $g$, $b$ (in that order or shifted left or right) to calculate the results for the next row in constant time.


answered 21 Sep '18, 10:24

algmyr's gravatar image

accept rate: 37%

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 20 Sep '18, 16:44

question was seen: 117 times

last updated: 21 Sep '18, 11:04