time limit exceeding

[oyehoye6906]

There is a field with plants — a grid with N rows (numbered 1 through N) and M columns (numbered 1 through M); out of its NM cells, K cells contain plants, while the rest contain weeds. Two cells are adjacent if they have a common side.

You want to build fences in the field in such a way that the following conditions hold for each cell that contains a plant:

it is possible to move from this cell to each adjacent cell containing a plant without crossing any fences
it is impossible to move from this cell to any cell containing weeds or to leave the grid without crossing any fences
The fences can only be built between cells or on the boundary of the grid, i.e. on the sides of cells. The total length of the built fences is the number of pairs of side-adjacent cells such that there is a fence built on their common side plus the number of sides of cells on the boundary of the grid which have fences built on them. Find the minimum required total length of fences that need to be built.

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains three space-separated integers N, M and K.
K lines follow. Each of these lines contains two space-separated integers r and c denoting that the cell in row r and column c contains a plant.
Output
For each test case, print a single line containing one integer — the minimum required length of fences.

Constraints
1≤T≤10
1≤N,M≤109
1≤K≤105
1≤r≤N
1≤c≤M
the cells containing plants are pairwise distinct

https://www.codechef.com/APRIL19B/problems/FENCE

firstly Im sorting the vector of pairs by first then second.(1,2 1,3 2,1 2,2)
then Im sorting vector of pairs by second then first.(2,1 1,2 2,2 1,3)
then Im checking if following pairs are having plants in their adjacent cells or not by checking if adjacent pairs are present in vector of pairs.
its taking O(nlogn) time then also Im getting tle.
Someone please explain me why Im getting tle.

[Duthomhas]

tl;dr: I did not look at your code.

Typically, competition stuff like this is designed to fail if you use a standard brute-force solution.

The trick is to see if there is a way to solve the problem using a different method. I can think of a (possible) solution right now that has an O(2n) complexity. It might help to draw yourself an example of the grid.

Hope this helps.

[oyehoye6906]

@duthomhas I can not draw grid for large test case because grid will be of (10**9)*(10**9).

[Duthomhas]

WTH? You can draw a 5 by 5 grid.

[dhayden]

Someone please explain me why Im getting tle.

Take the worst case where K=10⁵ and T=10. Sorting 10⁵ Takes 10⁵*log₂(10⁵) ~ 1.66 million comparisons. With T=10 that's 16.6 million. if we conservatively estimate an average of 10 instructions for each comaprison (and the occasional swap), that's 166 million instructions for sorting. You sort twice so we're up to 332 million. You have to to through the sorted data (twice) and process it, but even at 100 instructions per item, that's 10⁵*2*100 = 20 million instructions. So we're at around 352 million instructions. On a 4GHz processor that's pretty quick. Even at 10 ticks per instruction it's 0.88 seconds.

So it sounds to me like your method, though not ideal, should work within the allotted time if you code it efficiently. The key to this problem is quickly determining if a plant has neighbors. As Duthomhas says, there are probably faster ways than what you're using.

[Duthomhas]

For a 110 by 106 element array, just statically allocate it.

Then when you read in your data, put the elements in the array.

Then make two passes over the array. One for the left-right/west-east fences, and another for the up-down/north-south fences.

O O O P P → 2 fences
O O O P O → 2 fences
O P P O P → 4 fences
O O O O O → 0 fences
↓ ↓ ↓ ↓ ↓
0 2 2 2 4 fences

sum is 18 fences.

The question boils down to: how many times do you cross a boundary?

O O O P O
     ↑ ↑
	 boundary crossings

With some careful structure design, you might be able to do it even faster with some unordered maps or something.

Hope this helps.

[dhayden]

Duthomhas, the OP messed up with cut & paste. The dimensions of the array M&N can be

1≤N,M≤10⁹ so allocating a static array is out of the question.