Part of list:

Lasers (ZCO 2017: India)

Lasers (ZCO 2017: India)

You are given an m *x* n grid with 3 types of cells - empty, black and white. There are b black cells, and w white cells.

A laser starts from an empty cell and travels towards the right. The laser stops on encountering either a black cell, or when it encounters its second white cell (or if neither happens, it stops when it reaches the boundary).

L(i, j) denotes the length travelled by a laser starting at (i, j). Note that the length is inclusive of both the columns, i.e. if the laser starts from (i, j) and ends at (i, k) when its length travelled is = k - j + 1.

Find the sum of L(i, j) for all i, j

Constraints: n, m <= 10^6 and b, w <= 10^5

*Thanks Samarjeet for the problem statement. *

*Zonal Computing Olympiad is round 1 out of 3 for selection into Indian IOI team.*

Read more…(155 words)

Mark as completed

Part of lists:

Previous

Four Sum (ZCO 2017: India)

Next

Quiz: Recursion

About the author:

Keshav Dhandhania

Loading…

Have a question? Ask here…

Post

Part of list:

Lasers (ZCO 2017: India)

About the author

Keshav Dhandhania

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.