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

×

WOUT - Editorial

0
2

PROBLEM LINK:

Contest
Practice

Author: Vitalij Kozhukhivskij
Tester: Hiroto Sekido
Editorialist: Kevin Atienza

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic programming, subarray sums, prefix sums, segment trees

PROBLEM:

There is a grid of $N\times N$ cells. The $N$ blocks of each column are made up of soil, except for a contiguous sequence of cells: from the $l_i$th cell to the $h_i$th cell (starting from the bottom, $0$-indexing). Cells can be cleared of soil.

We need to create a subgrid of length $N$ and height $H$ containing no soil. What is the minimum number of cells needed to be cleared of soil?

QUICK EXPLANATION:

There are only $N-H+1$ possible $N\times H$ subgrids. The answer is the the minimum number of soil cells among all such subgrids. We can preprocess our grid so we can compute the sum of each subgrid in constant time.

To preprocess:

  • We need to know the number of soil cells in each row (denoted by $r_i$ for $0 \le i < N$). $r_i$ is equal to the number of $j$s such that $0 \le j < N$ and $i < l_j$ or $i > h_j$. This is also equal to the following expression: $$ N - \#\{j : 0 \le j < N, i \le h_j\} + \#\{j : 0 \le j < N, i < l_j\} $$ Thus the $r_i$s can be computed quickly by considering the $l_j$s and $h_j$s in sorted order.
  • We also need to know the number of soil cells in each prefix of rows, i.e. let $s_i$ be the sum $r_0 + r_1 + \cdots + r_{i-1}$.

Then the number of soil cells in each $N\times H$ subgrid can be computed as $s_i - s_{i-H}$ for $H \le i \le N$.

EXPLANATION:

Clearly, we need to find the $N\times H$ subgrid with the minimum number of soil cells in it. There are only $N-H+1$ such subgrids: the following illustrates the case $N = 7$ and $H = 3$ (there are $N-H+1 = 5$ subgrids):

.......          #######   .......   .......   .......   .......
.......          #######   #######   .......   .......   .......
.......          #######   #######   #######   .......   .......
....... -------> .......   #######   #######   #######   .......
.......          .......   .......   #######   #######   #######
.......          .......   .......   .......   #######   #######
.......          .......   .......   .......   .......   #######

We can simply construct the $N\times N$ grid, and compute the number of soil cells in these subgrids. Since there are $N-H+1$ subgrids and each one has $NH$ cells to check, this algorithm runs in $O((N-H+1)NH)$ time. The worst case is when $H$ is around half of $N$ (which makes the running time $O(N^3)$), so unfortunately this algorithm is only good for the first subtask. For the second subtask, you can't even store the whole grid due to the memory requirements!

To answer the second subtask, we need a way to sum up these subgrids without constructing the whole grid. The first thing we notice is that the only information we need from its row is the number of soil cells in it, i.e. we don't need to know their positions in the row. Let's say the $i$th row ($0 \le i < N$) contains $r_i$ soil cells. Then the number of soil cells in each of the $N-H+1$ subgrids are the following:

  • $r_0 + r_1 + r_2 + \cdots + r_{H-1}$
  • $r_1 + r_2 + r_3 + \cdots + r_H$
  • $r_2 + r_3 + r_4 + \cdots + r_{H+1}$
  • $r_3 + r_4 + r_5 + \cdots + r_{H+2}$
  • $\ldots$
  • $r_{N-H} + r_{N-H+1} + r_{N-H+3} + \cdots + r_{N-1}$

The smallest of these is the answer! Thus, it would be very helpful if we can compute the sequence $r_0, r_1, \ldots, r_{N-1}$ quickly, without constructing the whole grid!

To do so, we use the following observation: $r_i$ is equal to the number of $j$s such that $0 \le j < N$ and $i < l_j$ or $i > h_j$. Now, counting all such $j$s this way is still not fast enough, so we do some manipulations first. For a statement $\phi(j)$, let $C_{\phi(j)}$ be the number of $j$s such that $0 \le j < N$ and $\phi(j)$ is true. To familiarize yourself with this notation, we give a few basic facts (we invite you to verify each one):

  • $C_{\text{true}} = N$
  • $C_{\text{false}} = 0$
  • $C_{\phi(j)} + C_{\text{not }\phi(j)} = C_{\text{true}} = N$
  • $C_{\phi(j)} = C_{\text{true}} - C_{\text{not }\phi(j)} = N - C_{\text{not }\phi(j)}$
  • $C_{\phi_1(j) \text{ or } \phi_2(j)} = C_{\phi_1(j)} + C_{\phi_2(j)} - C_{\phi_1(j) \text{ and } \phi_2(j)}$
  • $C_{c < f(j)} + C_{c = f(j)} + C_{c > f(j)} = N$ (trichotomy)
  • $C_{c < f(j)} + C_{c = f(j)} = C_{c \le f(j)}$
  • If $f_1(j) \le f_2(j)$ for all $j$, then $C_{f_1(j) \le c \le f_2(j)} = C_{c \le f_2(j)} - C_{c < f_1(j)}$

Now, back to $r_i$. We have the following (using some of the facts above:

$$\begin{align*} r_i &= C_{i < l_j \text{ or } i > h_j} \\\ &= N - C_{\text{not } (i < l_j \text{ or } i > h_j)} \\\ &= N - C_{i \ge l_j \text{ and } i \le h_j} \\\ &= N - C_{l_j \le i \le h_j} \\\ &= N - (C_{i \le h_j} - C_{i < l_j}) \end{align*}$$ The last one is true because $l_j \le h_j$. Now, we have: $$r_i = N - C_{i \le h_j} + C_{i < l_j}$$ To compute the $r_i$s, we just need to compute the quantity $- C_{i \le h_j} + C_{i < l_j}$ for all $0 \le i < N$.

The key to this is to notice that $r_i$ can be computed by a simple adjustment from $r_{i-1}$! In other words, we can just calculate the difference $r_i - r_{i-1}$, and if we have already computed $r_{i-1}$, then we can calculate $r_i$ by adding this difference. In more detail, let's try to compute $r_i - r_{i-1}$: $$\begin{align*} r_i - r_{i-1} &= (N - C_{i \le h_j} + C_{i < l_j}) - (N - C_{i-1 \le h_j} + C_{i-1 < l_j}) \\\ &= N - C_{i \le h_j} + C_{i \le l_j-1} - N + C_{i \le h_j+1} - C_{i \le l_j} \\\ &= C_{i \le h_j+1} - C_{i \le h_j} + C_{i \le l_j-1} - C_{i \le l_j} \\\ &= (C_{i \le h_j+1} - C_{i \le h_j}) + (C_{i \le l_j-1} - C_{i \le l_j}) \\\ &= C_{i = h_j+1} - C_{i = l_j} \end{align*}$$ But we can compute the values $C_{i = h_j+1}$ and $C_{i = l_j}$ for $0 \le i < N$ quickly, via a linear pass of all pairs $(l_j,h_j)$ for $0 \le j < N$! The following pseudocode does it:

# arrays are initialized with zeroes
Ch[0...N]   # Ch[i] will contain C[i = h_j + 1]
Cl[0...N]   # Ch[i] will contain C[i = l_j]
for j = 0...N-1:
    Ch[h_j + 1] += 1
    Cl[l_j] += 1

Now that all the $C_{i = h_j+1}$ and $C_{i = l_j}$ are computed, we can now compute all the $r_i$s using the following recurrence: $$r_{-1} = N$$ $$r_i = r_{i-1} + C_{i = h_j+1} - C_{i = l_j}$$ The following pseudocode does it:

# array is initialized with zeroes
r[0...N]
curr = N
for i in 0...N-1:
    curr += Ch[i] - Cl[i]
    r[i] = curr

Clearly, these pseudocodes run in $O(N)$ time!

Finally, to compute the answer, we need to know the following sums:

  • $r_0 + r_1 + r_2 + \cdots + r_{H-1}$
  • $r_1 + r_2 + r_3 + \cdots + r_H$
  • $r_2 + r_3 + r_4 + \cdots + r_{H+1}$
  • $r_3 + r_4 + r_5 + \cdots + r_{H+2}$
  • $\ldots$
  • $r_{N-H} + r_{N-H+1} + r_{N-H+3} + \cdots + r_{N-1}$

and then compute the minimum among them. But this is easy! Notice that $r_i + r_{i+1} + \cdots + r_j$ is simply $(r_0 + \cdots + r_j) - (r_0 + \cdots + r_{i-1})$, so we can first try computing the prefix sums. Let $s_i$ be the sum $r_0 + r_1 + \cdots + r_{i-1}$. Then $r_i + r_{i+1} + \cdots + r_j$ is simply $s_{j+1} - s_i$. The $s_i$s can be computed in $O(N)$ too, because $s_i = s_{i-1} + r_{i-1}$, with the base case $s_0 = 0$. Afterwards, the sums we need are simply:

  • $s_H - s_0$
  • $s_{H+1} - s_1$
  • $s_{H+2} - s_2$
  • $\ldots$
  • $s_N - s_{N-H}$

Since all the steps of this algorithm runs is $O(N)$, the answer can thus be computed in $O(N)$ time in total!

The following is a sample implementation in Python:

for cas in xrange(input()):
    n, h = map(int, raw_input().strip().split())
    row = [0]*(n+2)
    for i in xrange(n):
        a, b = map(int, raw_input().strip().split())
        row[a+1] -= 1
        row[b+2] += 1
    row[0] = n
    for i in xrange(n): row[i+1] += row[i]
    for i in xrange(n): row[i+1] += row[i]
    print min(row[i] - row[i-h] for i in xrange(h,n+1))

A few things to notice about this implementation:

  • The pairs $(l_j, h_j)$ are never stored in an array: they are obtained from the input on the fly, processed, and thrown away immediately.
  • Instead of having two arrays for $Ch[i]$ and $Cl[i]$, we only use a single array containing $Ch[i] - Cl[i]$.
  • We reuse the same array row to contain the values $Ch[i] - Cl[i]$, $r_i$ and $s_i$. Furthermore, $r_i$ is stored in index $i+1$ of row.

Time Complexity:

$O(N)$

AUTHOR'S AND TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 16 Aug '15, 13:06

kevinsogo's gravatar image

7★kevinsogo
1.7k583142
accept rate: 11%

edited 02 Jun '16, 18:48

admin's gravatar image

0★admin ♦♦
19.6k349497539


14

why editorialists use too much complex thing which really hard to understand why cann't they use some images or any other resources to easily visualization of things...

this question was quite easy who knows about BIT/segment tree data structure(I also know...): P but moment I saw explanation I got stuck and think is this question that much difficult??

is there a way where user also can make editorial too??.1.

Happy coding

link

answered 18 Aug '15, 00:59

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

@rcsldav2017

Dude please tell me the easy way, this editorial has just crossed my head.

(29 Mar '16, 07:07) arpit7282★
(31 Jan, 00:10) worldunique3★

WAYOUT was a regular BIT/segment tree problem. To make the users think about O(n) solution rather than O(nlogn), the time limit could have been made strict, maybe 0.5 seconds or n<=10^6. BIT solution link https://www.codechef.com/viewsolution/7723896.

link

answered 17 Aug '15, 19:53

likecs's gravatar image

6★likecs
3.7k1978
accept rate: 9%

WAYOUT was a regular BIT/segment tree problem. To make the users think about O(n) solution rather than O(nlogn), the time limit could have been made strict, maybe 0.5 seconds or N<=10^6

link

answered 17 Aug '15, 19:51

likecs's gravatar image

6★likecs
3.7k1978
accept rate: 9%

Can someone please explain why my code gives WA on some of the test cases of subtask 2 WOUT

link

answered 17 Aug '15, 21:03

skysarthak's gravatar image

3★skysarthak
453
accept rate: 0%

2

for integer value of constraints answer can be large more than integer limit that's why you got WA it is advice to keep everything in long long for every question from now on :)

(17 Aug '15, 23:29) admin1235★

thanx for looking into the problem @admin123 but i did try long long as well link and still WA

(18 Aug '15, 00:36) skysarthak3★

@admin...but if long long int is required only by 2 or 3 variable why we declare all variable long long int...it slow down solution..because that can not handle at time in 64-bit machine it require double time compare int calculation because long long int 128-bit long variable cpu stored it into two-place and do calculation which simply increase the time required by machine to variable manipulation and calculation... I think it is not good advice...you should only be aware which variable might get value out of range of int[-2^16 2^16-1] integer range is quite long no need too worry much

(18 Aug '15, 00:49) rcsldav20175★

Because everything is in int and ans can come out to be in long.

link

answered 17 Aug '15, 23:20

nik910's gravatar image

5★nik910
4515
accept rate: 0%

I didn't understand the question during the contest. But reading the problem statement in the editorial made me understand. I solved without reading the editorial any further. Should have paid more attention in the contest. Btw why are you using BIT or segment tree? Simple prefix sum works too.

My solution

link

answered 19 Aug '15, 15:02

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

yes .. tutorials are given to make things easier .. but some tutorials uses so much extra things which are really not required . .

(31 Jan, 00:07) worldunique3★

Awesome solution! I dunno why the other users are complaining. Even I used a BIT solution to solve this. Thanks for showing me a faster way!

link

answered 18 Aug '15, 18:56

thespacedude's gravatar image

2★thespacedude
26371627
accept rate: 6%

Segment Tree solution of WayOut:- https://www.codechef.com/viewsolution/7856183

link

answered 18 Aug '15, 21:27

kartikgoyal04's gravatar image

2★kartikgoyal04
111
accept rate: 0%

@nil96 your solution didn't passed as you need to optimize it by avoiding use of long long int. Use int instead and at last you can use long long int.

link

answered 21 Aug '15, 19:11

apptica's gravatar image

5★apptica
939210
accept rate: 17%

this is not a dp question too a far and large extent .. why wrong tag ??

link

answered 31 Jan, 00:10

worldunique's gravatar image

3★worldunique
1297
accept rate: 0%

edited 31 Jan, 00:12

@admin...

but if long long int is required only by 2 or 3 variable why we declare all variable long long int...it slow down solution..because that can not handle at time in 64-bit machine it require double time compare int calculation because long long int 128-bit long variable cpu stored it into two-place and do calculation which simply increase the time required by machine to variable manipulation and calculation... I think it is not good advice...you should only be aware which variable might get value out of range of int[-2^16 2^16-1] integer range is quite long no need too worry much just take care of range only some cases.... Happy coding...

link

answered 18 Aug '15, 00:50

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

I used the same algorithm with Big(O) complexity but still I got TLE , I still don't understand Can anyone help me ? i am new to coding contests I solved a lot of practice problems although https://www.codechef.com/viewsolution/7804230 https://www.codechef.com/viewsolution/7806640

link

answered 18 Aug '15, 21:34

m41_madan2000's gravatar image

3★m41_madan2000
111
accept rate: 0%

edited 18 Aug '15, 21:35

What do we mean by this statement

Let C[ϕ(j)] be the number of js such that 0≤j<N and ϕ(j) is true.

link

answered 19 Aug '15, 16:45

pd17's gravatar image

3★pd17
1
accept rate: 0%

what do we mean by this statement

Let C[ϕ(j)] be the number of js such that 0≤j<N and ϕ(j) is true.

link

answered 19 Aug '15, 16:47

pd17's gravatar image

3★pd17
1
accept rate: 0%

Why my segment tree solution has not passed and given TLE please explain

https://www.codechef.com/viewsolution/7686894

link

answered 21 Aug '15, 09:01

nil96's gravatar image

2★nil96
18071845
accept rate: 5%

sorry can some one explain, how C[i=hj+1] and C[i=lj] are computed in O(N) ? Aren't they supposed to be computed for every row ? In which case it would cost around O(N^2)? I understood the rest of the prefix sum and how it is O(N) though. I am in learning stage, any explanation would be helpful

link

answered 24 Aug '15, 22:21

ironman8888's gravatar image

2★ironman8888
31
accept rate: 16%

This was demonstrated in the first pseudocode of the editorial. Notice that:

  • This code clearly runs in O(N) time.
  • This code computes all C[i=hj+1] and C[i=lj] (for all j).
  • This only needs to be run once, at the beginning.
(25 Aug '15, 13:58) kevinsogo7★

Hi , I used the following approach for solving the problem without using bit/segment trees.

https://www.codechef.com/viewsolution/7726107

Hope this helps!!

link

answered 20 Sep '15, 13:23

jeffa's gravatar image

3★jeffa
101
accept rate: 0%

can you please explain your code?

(04 Aug '17, 13:34) scorpion_ajay4★

I am getting wrong answer in 2 sections of subtask 2. Could somebody look and point out what me be wrong. Here is a link to my solution: https://www.codechef.com/submit/complete/11254238

link

answered 27 Aug '16, 04:01

aman05's gravatar image

4★aman05
111
accept rate: 0%

Why is r-1=N? Couldn't get that.

link

answered 06 Jun '17, 18:59

shankyk's gravatar image

0★shankyk
1
accept rate: 0%

also, if you know more questions like this please let me know. Thanks in advance for that

(06 Jun '17, 21:06) shankyk0★
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:

×15,125
×3,607
×1,962
×199
×186
×61

question asked: 16 Aug '15, 13:06

question was seen: 8,270 times

last updated: 31 Jan, 00:12