Thread: This one is really hard

Check out this link:-

http://www.iarcs.org.in/inoi/2003/in...er/chamber.pdf

I'm having problem in this particular problem. Before anyone asks what have you tried, my answer is everything I could. I have tried to think of every possible logic I could use, but in vain. Some help would be gladly accepted. I have done many other difficult programs, but none like this. Please help.

Maybe you would like to copy the contents of your link and insert them in your post.
Some people might be driven away from this thread because they do not like to follow unknown links.

The link contains some diagrams I can't copy. Don't worry, it's a PDF file.
Here, open this one.

Hello, so if you tried

..everything I could. I have tried to think of every possible logic I could use, but in vain...

maybe there is no sollution. Unless there is something you didnt tried.

I would want to know what have you tried, so I dont have to post something that is already tested and prooved as not working. Maybe we the answerers will see only small error in your attempt and correct you so you can continue with it. If you are not willing to show us your attempts, why should we post you the whole sollution?

Originally Posted by Zavael

Hello, so if you tried

maybe there is no sollution. Unless there is something you didnt tried.

I would want to know what have you tried, so I dont have to post something that is already tested and prooved as not working. Maybe we the answerers will see only small error in your attempt and correct you so you can continue with it. If you are not willing to show us your attempts, why should we post you the whole sollution?

I said I tried "Everything I could", not everything possible in this world. Obviously there is something I missed (meaning a logic I didn't think maybe). That's why I posted the problem. And this question is solvable, it's just bloody difficult. For your information, this question came in INOI 2003 (Indian National Olympiad of Informatics, 2003) and only 22 students of the 100 selected from all over India could do this program. I have solved other question papers from 2004 to 2013, but this one I cant.

Still, if you want to know what I really tried, then I should let you know.

Once, I tried going along the walls i.e. create a pointer to go along the walls (cells containing value 1) starting from bottom left corner. If while going along the pointer found two routes from its position containing 1's (junction of walls), the I used recursion to go along both one by one and call the same method if another junction is found. In this way, I could count the no. of times the pointer reaches back to its initial position and that would be the no. of chambers. But that posed a problem for chambers in the middle with no contact with the outer walls. Also, counting the area of each chamber is very difficult. I need an Authentic solution for this program. No need for whole programs, just explanation and logic would be very helpful and gladly accepted. Looking forward for answers.


Thank you.

This is a very old problem sometimes called 'the ponds and islands problem'.

The solution will become clear to you if you can visualize the data objects and how they interact. Think like a DBA to see the data schema. This one is simple. There are not many object types. If you use a functional decomposition approach, the problem will become far more difficult.

I'm sorry, but I didn't understand what you are trying to say.

--- Update ---

I know its an old problem but not too old be become obsolete. INOI gives logical problems for which you mostly need basic programming knowledge, but need the logical thinking of a genius. I solved other papers of INOI (2004 - 2013) in less than 40 minutes (average, each program), but this one I'm stuck for 14 days. And it really frustrates when you cant do a program for 14 days. Believe me, it does.

There is more than one decomposition strategy to solve any computing problem. The strategy I see used most often in industry and taught in academia is 'functional decomposition'. You can google this to learn what it means.

This particular problem is difficult to solve using functional decomposition. There is another method of decomposition that will solve this problem. That method is often called data domain decomposition. You can google this too.

Data decomposition is the analysis method used by data modelers to represent any problem. DBA's often use this methodology. The entity relationship diagram (ERD) used to represent a relational database schema is an expression of this thinking model.

Build a data model for this castle / chamber problem. Then map that into Java classes. I would suggest you start with the Castle. What is the Castle? It is either an extension or aggregation of a collection tiles. Yes? Moreover, the problem statement constrain the geometry of this collection. It is a rectangular array of Tiles not less that 1 x 1 or greater than 500 x 500 elements.
The same thinking can be applied to a Tile. The problem statement says a Tile is either a wall or open space and each Tile has a unique location in the Castle. Tiles may have neighbors. This gets a little more complex. In the trivial case, a 1x1 castle, that tile has 0 neighbors and must be a wall! In the 1x2 and 2x1 cases, each tile has 1 neighbor which must also be a wall. ... In the most general case a Tile may have up to 4 adjacent neighbors which themselves may be either walls or spaces. Each Tile which is a space is a member of exactly one Chamber.
A Chamber is a contiguous adjacency of Tiles that are spaces.


Does this help you?

I now understand what you are trying to say, but that's all good for theory. It was one of my ideas, but then the problem comes:- how do I implement it in code. Still thank you for your advice. It did help me a bit. By the way, I didn't know what was data domain decomposition and functional decomposition. It wasn't taught at school. Thank you.

I had guessed your schooling did not teach this. My prior experience with east asian developers indicated to me that education there was not covering these topics. I was intending to teach you how to get the data model into code. Are you interested in learning how to do this?

The next step is to map the ERD into a UML class diagram, which maps to code.

Originally Posted by DarthBane

The next step is to map the ERD into a UML class diagram, which maps to code.

Please Explain.

Originally Posted by DarthBane

I was intending to teach you how to get the data model into code. Are you interested in learning how to do this?

Yes, please do. You are very much welcome.

ERD = Entity Relationship Diagram. These are the large charts you see the DBA's using. google to see what these are and how they work. We already talked about the three top level entities that are going to be represented on this, Castle, Chamber and Tile. An ERD shows the objects, their attributes and their relationships. It does not represent anything of process, that is, no methods.

Enter the class diagram. This is a UML construct. google this to learn about it. It diagrams classes, their relationships, attributes and methods. This is where process begins to enter the picture. The classes, attributes and relationships come directly from the ERD. You will add the methods. A class diagram can go directly to code without a lot of other analysis if the model is simple enough. This problem is a simple candidate.

First step for you : construct your ERD and I will review it with you.

As you tried to go by the walls, i would try to count the space cells instead of walls. I think it could be done without object oriented programming, but it could be really harder.

In OOP it could be done in the way that you create a Castle as object, that can store Chamber objects. Chamber stores reference to "open space" Tiles that belongs to it. Tile has position on the floor and the information if it is gouped to specific chamber (= "chambered") or not yet - and if it is, it knows what the chamber it is from castle's chambers.
The castle can create a new chamber and can merge two chambers into one and preserving all the Tiles from both chambers into that one that remains (or new one with deleting the two others). The castle has the floor plan (maybe two dimensional array of Tiles).
The chamber can add a Tile to its Tiles.

Now with this prototype structure (maybe I missed something that will be needed), you can iterate over all tiles and play around with these rules:

1. If the current Tile is not "chambered" in castle (ie no chamber hold it) check for the 4 neighbour Tiles (if they exist) and if any of the neighbour is already "chambered", associate the current Tile to that chamber.
2. If no neighbour tile is "chambered" create a new chamber in the castle and add the Tile to it. (when you go to the next Tile it will be associated to the same chamber as stated in rule 1)
3. If on one Tile there will be more than one neighbour Tiles "chambered", merge all the chambers in the castle together and add the Tile to them.

The rules shouldnt be hard to implement.
At the end, now in your castle object you know how many chambers do you have and how many Tiles has each of them. I hope this can help.

EDITED - but i would suggest you to go trough the whole process with DarthBane it will teach you a lot more

Of course it can be done without OOP but it is much cleaner, elegant, and more maintainable if it is solved using object technology. I once wrote the solution to this problem is PL1!

One can also write a procedural solution to the problem in Java or C++, but I would argue that is a misapplication of those languages.

--- Update ---

I know this is a lot to learn, but I am trying to teach you how to think about the problem in the data domain instead of the process domain. When you master this mode of thinking you will no longer need to draw the diagrams for simple problems like this one. It will come to you just like your process domain solutions do now.

Hey, I'm back. Just wanted to ask something to DarthBane. Is there a way to solve this problem without constructing an ERD, because frankly speaking, I've never constructed an ERD before and I have solved every problem I have encountered without constructing an ERD with ease (except this). Please help. Moreover, I need a way to solve this kind of problem within 40 minutes, for the competitions. Your posts are highly appreciated.

Thank You.

Originally Posted by Abhilash

Hey, I'm back. Just wanted to ask something to DarthBane. Is there a way to solve this problem without constructing an ERD, because frankly speaking, I've never constructed an ERD before and I have solved every problem I have encountered without constructing an ERD with ease (except this). Please help. Moreover, I need a way to solve this kind of problem within 40 minutes, for the competitions. Your posts are highly appreciated.

Thank You.

I am trying to teach you how to think about the problem so you can solve it quickly. It is clear to me from your posts that you are trying to apply functional decomposition to these problems. That approach can theoretically solve any problem, but some problems, like this one, can present great difficulty using that method. You want to solve this quickly? Learn how to think in the data domain.

The purpose for working through an ERD is to learn how to think in the data domain first. As I said earlier, once you have mastered this technique, the solutions to simple problems like Castle/Chamber will not require you to construct an ERD on paper. They will come to you just as the functional decomposition solutions do today. It is simply a matter of training your mind how to think about these problems as data relationships instead of sequences of processing steps.

Your call. Do you want to get any better at this or do you want to continue to pursue a methodology that is shown to be inadequate in all situations?

Originally Posted by DarthBane

I am trying to teach you how to think about the problem so you can solve it quickly. It is clear to me from your posts that you are trying to apply functional decomposition to these problems. That approach can theoretically solve any problem, but some problems, like this one, can present great difficulty using that method. You want to solve this quickly? Learn how to think in the data domain.

The purpose for working through an ERD is to learn how to think in the data domain first. As I said earlier, once you have mastered this technique, the solutions to simple problems like Castle/Chamber will not require you to construct an ERD on paper. They will come to you just as the functional decomposition solutions do today. It is simply a matter of training your mind how to think about these problems as data relationships instead of sequences of processing steps.

Your call. Do you want to get any better at this or do you want to continue to pursue a methodology that is shown to be inadequate in all situations?

I know I have to use data domain decomposition method, which I am trying to, but is it absolutely necessary to construct ERD?

Originally Posted by Abhilash

I know I have to use data domain decomposition method, which I am trying to, but is it absolutely necessary to construct ERD?

The fact that you are stymied by the problem suggests the ERD will help you see the data pattern more clearly. That is what ERD's are for, visualization of data schema. As an added bonus, you will most certainly encounter these if you ever work professionally with a DataBase Architect, a common working arrangement among Java server developers.

Lets look at the Castle object again. A Castle is comprised of Tiles. It contains some number of Chambers each of which shares some number of Tiles with its Castle. No Tile is a member of more than one Chamber. This tells you a great deal about the ERD data relationships.

Let me try.

After one and a......... sorry 2 months, I finally got the answer.
Thank you.

Originally Posted by Abhilash

After one and a......... sorry 2 months, I finally got the answer.
Thank you.

What method led you to the solution?

The very same method which solves all problems. A method taught to students at high school while programming which helps solving many problems which would require extensive logic just by the use of simple ideas. RECURSION.

Of course, I knew I had to use it, but then the question was the idea. Finally I got the idea a week before my competition(you can see about the competition in my member introduction. You will know which one. It is in one of the replies in my thread.)

The idea was "explore a tile and convert it to a wall". First, I used two for loops to run through the 2D array in the main function. The moment I got a space tile (i.e. cell with value 0), I sent its coordinates(or location) to the 'explore'. There I converted the 0 to 1 (i.e. space to wall) and then checked the neighboring tiles for zeros(space). Each time I got one I again sent its location to the very same explore function(hence, recursion) and the process got repeated. For zeros in multiple directions, I gave preference in the order of down, right, up and left. If no 0 found in any direction, the method would return back to where it was last called from - itself, but with the previous value now which it had used to call itself. Only this time, it would try in some other direction other than the path followed previously. That is the main advantage of using recursion. Ultimately, since it cannot jump squares but only follow the path of zeros, it stays confined in a particular chamber and converts the white tiles to black ones. When all done, it ultimately returns back to the main function, but this doesn't end still. Remember that we are in a loop that runs through the grid, checking for zeros. With one chamber practically erased and its size(area) stored, the loop finds another zero in another chamber(if present) and explore starts from there.

Thus, the program does this to every chamber one by one until no chamber is left. Also while this, I am also calculating the area, incrementing it in a chamber for every 0 converted to 1. After the chamber vanished, I compare it with the previous value found. If greater, I store it in the variable which I compared with just now(this is to find the largest area). The program also keeps count of the chambers. And this is how I did it.

Thank you again.