CommonLounge is a community of learners who learn together. Get started with the featured resources above, ask questions and discuss related stuff with everyone.
[LEADGAME] Lead Game
Problem statement clarification:
Now I get it, I was misinterpreting question all this time. Actually after finish of each round, lead is not the difference between points of that round. But the lead is difference between the points achieved through all rounds including current round - Lakpa Tashi Bhutia
A sequence (array) is really just a function which associates integers (indices) with the corresponding values. However, there is no reason to restrict our usage of binary search to tangible sequences. In fact, we can use the same algorithm described above on any monotonic function f. ... The only difference is that we replace an array lookup with a function evaluation: we are now looking for some x such that f(x) is equal to the target value.
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.