# FENCING Editorial - Unofficial

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

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

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

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

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

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