FENCING Editorial - Unofficial

editorial
1

Simple implementation without using data structures
Imagine an M*N matrix where blocks are given consecutive numbers

  • for a given row all the numbers are consecutive
  • make sure that the last number of a row and the first number of the next row are not consecutive (I’m using row gap 1)
  • let ‘T’ be the number of trees
  • consider an array of size T now run a loop for taking tree positions as input and simultaneously store the block number of tree block in the array
    /* for(i=0;i<trees;i++)
    {
    scanf(“%ld”,&r);
    scanf(“%ld”,&c);
    block_number[i] = c + ((r-1)*(columns+1)); // row gap 1
    } */
  • now sort the array block_number[ T ] using quick sort
  • search(using binary seach) the left,right,up,down block numbers for each tree block in the array block_number[ T ]
    if found add 1 to count ( number of removable fences )
  • Maximum number of fences possible = 4*trees
  • Number of required fences = 4*trees - count
    here’s my implementation using C
1 Like
2

Here’s my solution to this problem. Pairs are used to note down the co-ordinates where trees are present. All such pairs are pushed into a set. Now we iterate over the elements of the set. In every iteration, we find out whether around a tree, there are trees present on each of it’s four sides or not. If not, we increment the count of fence length, initially set to zero by one, for each of the sides where there was no tree. Iterating over the entire set using the above logic gives the required fence length.

Here’s the solution to this:
https://www.codechef.com/viewsolution/23884954

1 Like
3

You are complicating the solution bro. There is a simple-10-line solution with maps. Just learn to use maps :slight_smile: It will help a lot in future :slight_smile:

4

could you please attach the implementation using map’s @anon55659401
I’m not familiar with STL containers and mostly I use C to solve , probably I’ll make it this summer

1 Like
5

Currently a bit busy,I’ll attach it till night!

6

https://www.codechef.com/viewsolution/23911001
Here is a solution using set ( similar to map) …
If it helps…
Feel free to ask queries

1 Like
7

The implementation using maps is quite easy compared to the above process using Data Structures.The approach basically involves to look on each individual cell that contains a plant and the no. of fences required around that cell to secure that plant.

Imagine a 3*3 matrix…and the cell [2,2] containing a plant…we would just have to look whether the adjacent cells of [2,2] i.e [2,1] , [1,2] , [2,3] , [3,2] contains a plant or not…if an adjacent cell contains a plant we don’t need to draw up a fence on that side…if it doesn’t then we sure as hell need to draw up a fence.

We can insert every cell that contains a plant in map …and then for every cell that contains a plant we could look out whether its adjacent cell is in the map or not…for every [x,y] we need to look for [x-1,y] , [x+1,y] , [x,y-1] , [x,y+1] , we would increment the no. of fences needed by ‘1’ for each of the non existent cell in the map among these four.We will do the above for every cell that contains the plant in the input.(For any cell at the edge in the matrix of course we need atleast one fence at the border and the look for its remaining adjacent cells 2(if a corner cell) or 3(if an edge cell) in the map).

Here is my solution in C++ — CodeChef: Practical coding for everyone

2 Likes