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

×

RESERVOI - Editorial

Practice
Contest

Author: Praveen Dhinwa
Tester: Istvan Nagy
Editorialist: Misha Chorniy

Difficulty:

Simple

Pre-Requisites:

none

Problem Statement

You are given matrix which presents a water reservoir, each cell can be water, air or brick. You need to check whether a state of the reservoir is stable or not? The state is stable if it will remain in the same state forever.

Explanation

Subtask 1

There are no water cells in matrix. We need to check if no one brick don't have air under itself. If brick has air under itself, it fall down.

ok = true for i=1..n-1 for j=1..m if s[i][j]=='B' and s[i+1][j]== 'A' //this block (i, j) will fall down ok = false

Subtask 2 and 3

Observe that air can't change something, we are interested in movements of bricks and water. Brick only can fall down, if under isn't brick. Water can move to the left(if there are empty or air), to the right(if there are empty or air) or move down(if there are nothing or air). ok = true for i=1..n for j=1..m if s[i][j]=='B' and i+1<=n and s[i+1][j]!='B' // brick (i, j) fall down ok = false if s[i][j]=='W' if j==1 or j==m or i==n //water overflow bounds ok = false else if s[i][j-1]=='A' or s[i][j+1]=='A' or s[i+1][j]=='A' //water can move into adjacent blocks(left, right, down) ok = false

Overall time complexity of this approach is $O(N*M)$.

Solution:

Setter's solution can be found here

Please feel free to post comments if anything is not clear to you.

This question is marked "community wiki".

asked 18 Jan '17, 07:50

mgch's gravatar image

6★mgch
4451436
accept rate: 20%

edited 18 Jan '17, 15:07

admin's gravatar image

0★admin ♦♦
19.8k350498541


I do this much more simple I make walls of air on left and right side of this matrix and put a brick base as

       A            A
       A            A
       .            .
       .            .
       A            A
       BBB...BBBBBBBB

Then checked if there is air in left, right, or below water block then it fails and if there is any water or air block below brick then it also fails these two conditions are sufficient to solve this problem. My solution is here

link

answered 19 Jan '17, 14:09

priyanshu789's gravatar image

2★priyanshu789
152
accept rate: 0%

edited 19 Jan '17, 14:10

Setter solution does not pass the test case 1 2 4 BWWB BWWB He did not consider that if there is water in nth row the system is unstable.

link

answered 18 Jan '18, 19:57

atharva_sarage's gravatar image

5★atharva_sarage
112
accept rate: 0%

According to me we should not check at if(i == n) for water as I hope it is allowed to place it at the bottom but surrounded by the bricks. As BWWWWB is correct as it also get passed and according to your editorials it would not get correct. So please make the questions more clear to understand!

link

answered 30 Oct '18, 18:39

chirag7145's gravatar image

3★chirag7145
1
accept rate: 0%

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,852
×1,191
×968
×125
×4

question asked: 18 Jan '17, 07:50

question was seen: 2,124 times

last updated: 30 Oct '18, 18:39