ACM ICPC 2019 Dhaka Regional Problem H (Droplets)

Finally, the contest is over. And it’s time for the editorial of my problem. This year, I have submitted two questions for the regionals. Between these two problems, one got selected for the Dhaka regional. And that problem appeared as number H (Droplets) in the contest. Hence this problem itself was quite simple, it was supposed to be the 3rd most manageable problem of the contest. But, somehow, it turned out to be the 2nd easiest one.

[Few days before the contest, we realized that a similar problem appeared in a national-level contest in RUET. But ICPC committee decided to keep the problem because this is a much much easier version, the RUET version was one of the hardest problem in that contest.]

The Problem

The problem is about filling up a matrix with water. There is a matrix given and you have to imagine it as a 2-d box. Some parts of the matrix are enclosed. Now, you need to find out the amount of water the matrix can hold. Please read the full statement here carefully before proceeding.

These are the pictures I used in the statement to describe the problem. What the problem asked you to do is quite clear from these pictures.

The Solution

Let’s consider the smallest unit of the matrix first to solve this problem. Here, the smallest unit is the little squares. Now, for each square in the matrix, how to identify whether there is water in the square or not?
For that to happen, the water must have a way to reach the square from the top. If you understand this part, you already know this is a graph problem. Therefore, treat every square as a node of the graph. And, a node is connected to its neighbor if no lines are blocking them.

As you have the graph now, scan the top squares from left to right. Every time you encounter a square on the first row whose top is not blocked, you found a way for the water to enter into the matrix. Afterward, run a depth-first-search from that node and mark all the nodes you can reach. Keep continuing this process, and in the end, the number of nodes you reached is the answer.

The time complexity of this solution is O(n * m) for each test case.

Here is the judge solution:

That’s it, I hope you enjoyed the problem!

Last but not least

Not sure whether you have noticed it or not, I have used climate-change as the theme of this problem. Recently 11000 scientists from all over the world declared a climate change emergency, which is quite alarming for all of us. Certainly, it is high time we need to be conscious about the rapidly changing climate. I am personally anxious about it, and you should be too. Let’s do whatever we can to reduce resource wastage, plastic usage, and whatever we need to save our mother planet.

Thank you.

Shafaet Ashraf

2 Comments

  1. But you copied the problem. Harder version of this problem already appeared in RUET IUPC 2019. The problem statement is also almost identical. I don’t see any point of using this problem in the regional contest where almost identical problem was already used in a contest few days ago.
    Now please don’t say that you didn’t know about that problem like some other setter said because at least half of the judges should already know that problem.ok

    • I didn’t copy the problem. We came to know about thee Ruet version a few days before the contest but at that time it was too late to change. As it’s an easy problem, the committee decided to keep the problem as it is.
      Anyway I am adding a note on the top of this article for clarifying this.

Leave a Reply

Your email address will not be published. Required fields are marked *