What is a good algorithm to protect the kingdom?

Question

I tried to solve the “Defense of the Kingdom Problem” and came up with an algorithm, but it exceeds the validity period of the problem.

I want to know a good algorithm to solve this over a period of time.

Problem:

Theodore implements a new strategic game, "Defense of the Kingdom." At each level, the player defends the Kingdom, which is represented by a rectangular grid of cells. The player builds crossbow towers in some mesh cells. The tower protects all cells in the same row and same column. There are no two towers separating a row or column.

Penalty per position is the number of cells in the largest unprotected rectangle. For example, the position shown in the picture has a penalty of 12.

Help Theodore write a program that calculates the penalty for a given position.

Enter

The first line of the input file contains the number of test cases.

Each test case consists of a line with three integers: w is the grid width, h is the grid height and n is the number of tower crossbows (1 ≤ w, h ≤ 40,000, 0 ≤ n ≤ min (w, h)).

Each of the next n lines contains two integers xi and yi - the coordinates of the cell occupied by the tower (1 ≤ xi ≤ w; 1 ≤ yi ≤ h).

Output

For each test case, print one integer - the number of cells in the largest rectangle that is not protected by towers.

Example

Input:
1
15 8 3
3 8
11 2
8 6

Output: 12

Answer 1

I would do it like this:

w, h , (x1,y1) .. (xN,yN), x1..xN, y1..yN, .

, . dx[] = { x1, x2-x1, ..., xN - xN-1, (w + 1) - xN }. y: dy[] = { y1, y2-y1, ..., yN - yN-1, (h + 1) - yN }. max(dx)-1 max(dy)-1, . , , , .

Answer 2

, - "" . , - .

, , , . , . , ( x, y) . .

. , , - ; . , , , {x _{+ 1} -x _i} {y _{+ 1} -y _i} . - , .

Answer 3

, ,

1 4 .

• let a:=0
• ,    .          . , .
• , , a           a.

Answer 4

9x6. 3 .

x, 9 . 3 . 9/3 = 3. 3 .

[ ]
[ ]
[x]
[ ]
[ ]
[x]
[ ]
[ ]
[x]

. , (6) (3). 6/3 = 2.

y. 6 . 3 . 6/3 = 2 :

[ ][x][ ][x][ ][x]

1 (3/3).

x y ( 0):

1,2
3,5
5,8

- 2x1 = 2.

[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][x][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][x][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][x]

99% , , x, y .

Answer 5

EDIT : - , ; , . , , , , . , , , .

. , , , , .

pieces.txt

1
15 8 3
3 8
11 2
8 6

DefenderBoard.h

#ifndef DEFENDER_BOARD_H
#define DEFENDER_BOARD_H

#include <fstream>
#include <vector>
#include <algorithm>

struct Coord {
    unsigned x;
    unsigned y;

    Coord() : x(0), y(0) {}
    Coord( unsigned xIn, unsigned yIn ) : x( xIn ), y( yIn ) {} 
}; 

class DefenderBoard {
private:
    std::string filename;
    unsigned testcase;
    unsigned gridsize_x;
    unsigned gridsize_y;
    unsigned numTowers;

    std::vector<unsigned> penalties;    
    std::vector<Coord> cells;

public:
    explicit DefenderBoard( const std::string& filenameIn );
    ~DefenderBoard();

    void getPenalties( std::vector<unsigned>& penalties ) const;

private:
    void getDataFromFile();
    void calculatePenalty();    
};

#endif // DEFENDER_BOARD_H

DefenderBoard.cpp

#include "DefenderBoard.h"

DefenderBoard::DefenderBoard( const std::string& filenameIn ) :
filename( filenameIn ),
gridsize_x( 0 ), gridsize_y( 0 ),
testcase( 0 ),
numTowers( 0 ),
penalty( 0 ) {
    getDataFromFile();
}

DefenderBoard::~DefenderBoard() {
}

void DefenderBoard::getPenalties( std::vector<unsigned>& penaltiesOut ) const {
    penaltiesOut = penalties;
}

void DefenderBoard::getDataFromFile() {
    std::ifstream file;
    file.open( filename );
    if ( !file.is_open() ) {
        // Note: This ExceptionHandler will not work for you.
        // You will need to supply your own error or exception handling.
        std::ostringstream strStream;
        strStream << __FUNCTION__ << " failed to read in file[" << filename << "]";
        throw ExceptionHandler( strStream );
    }

    file >> testcase;

    // Temps
    Coord towerCoord;
    // t -> testcase | c - tower coords
    for ( unsigned t = 0; t < testcase; ++t ) {
        file >> gridsize_x;
        file >> gridsize_y;
        file >> numTowers;


        for ( unsigned c = 0; c < numTowers; ++c ) {
            file >> towerCoord.x;
            file >> towerCoord.y;
            cells.push_back( towerCoord );          
        }
        calculatePenalty();
        // After Penalty is calculated this test case along with the penalty value 
        // can be stored into a struct containing both the penalty and a vector of cells
        // which would be done here and then that struct would be stored into another container to this class

        // If the above is choosen to be done then this needs to be called here instead of within the calculate function
        // Clear our cells so it can be reused for each test case found in this file. 
        cells.clear();
    }

    file.close();
}

bool compareCoordsX( const struct Coord& a, const struct Coord& b ) {
    return a.x > b.x;
}

bool compareCoordsY( const struct Coord& a, const struct Coord& b ) {
    return a.y > b.y;
}    

void DefenderBoard::calculatePenalty() {
    std::vector<unsigned> xValDiff;
    std::vector<unsigned> yValDiff;
    unsigned diff = 0;

    // First Sort By Largest X - Then Find The Differences
    std::stable_sort( cells.begin(), cells.end(), compareCoordsX );
    unsigned idx = 0;
    for ( ; idx < cells.size(); ++idx ) {
        // For First Iteration Only
        if ( idx == 0 ) {
            diff = gridsize_x - cells[idx].x;
            xValDiff.push_back( diff );
        } else {
            diff = cells[idx-1].x - cells[idx].x - 1; // Don't Forget to Subract 1
            xValDiff.push_back( diff );
        }
    }
    // Also push back the last value - 1
    xValDiff.push_back( cells.back().x - 1 );

    // Do Same Thing For Y
    std::stable_sort( cells.begin(), cells.end(), compareCoordsY );
    idx = 0;
    diff = 0;
    for ( ; idx < cells.size(); ++idx ) {
        // First Iteration Only
        if ( idx == 0 ) {
            diff = gridsize_y - cells[idx].y;
            yValDiff.push_back( diff );
        } else {
            diff = cells[idx-1].y - cells[idx].y - 1; // Don't Forget to Subtract 1
            yValDiff.push_back( diff );
        }
    }
    // Also push back the last value - 1
    yValDiff.push_back( cells.back().y - 1 );

    unsigned largestX = xValDiff[0];
    unsigned largestY = yValDiff[0];
    idx = 0;
    for ( ; idx < cells.size(); ++idx ) {   
        if ( xValDiff[idx] > largestX ) {
            largestX = xValDiff[idx];
        }    
        if ( yValDiff[idx] > largestY ) {
            largestY = yValDiff[idx];
        }
    }

    // Calculate Penalty And Store It
    // EDIT - I did update this code after I had originally posted it
    // and when I added the update I did forget to change this commented section
    // penalty = largestX * largestY;
    // It should be like this:
    penalties.push_back( largestX * largestY );

    // I did have this line of code here too but I moved it out of this function and into the getDataFromFile() method.
    // cells.clear();           
}

main.cpp

#include <iostream>
#include "DefenderBoard.h"

int main() {
    std::vector<unsigned> penalties;
    DefenderBoard board( "pieces.txt" );
    board.getPenalties( penalties );    

    unsigned idx = 0;
    for ( ; idx < penalties.size(); ++idx ) {
        std::cout << penalties[idx] << " ";
    }
    std::cout << std::endl;

    return 0;
}

12

- :

pieces.txt

2
15 8 3
3 8
11 2
8 6
12 10 4
2 2
9 7
3 9
8 5  

12 8

: , , MxN. , 8x8, , [12,2] [5,9], , . .

, . 1, , , , 1 . . . x, y. , , x y, .

, , , , , , - . . , . x y. , N. . - N, N + 1, - , N - . , - x y, .

:

, , ... , - "" "" OO... , -, , . , , , , , . , 1 2

, , , . , OO-, , . , .

• .
• .
• , , .
• , , :
  • .
  • .
  • .
  • .
  • .
  • .
  • .
• , , , - .

- -

• MxN.
• - , , , , ..
• .
• .
• .
• .

lisyarus OO.

#include <string>
#include <vector>
#include <algorithm>
#include <fstream>

struct TowerCoordinate {
    unsigned x;
    unsigned y;

    TowerCoordinate() : x(0), y(0) {}
    TowerCoordinate( unsigned xIn, unsigned yIn ) : x( xIn ), y( yIn ) {} 
}; 

struct GridSize {
    unsigned width;
    unsigned height;

    GridSize() : width( 0 ), height( 0 ) {}
    GridSize( unsigned widthIn, unsigned heightIn ) : width( widthIn ), height( heightIn ) {}
};

bool compareCoordsX( const struct TowerCoordinate& a, const struct TowerCoordinate& b ) {
    return a.x > b.x;
}

bool compareCoordsY( const struct TowerCoordinate& a, const struct TowerCoordinate& b ) {
    return a.y > b.y;
}

// Returns A Single Penalty
unsigned calculatePenalties( std::vector<TowerCoordinate>& towerLocations, GridSize& gridSize ) {
    std::vector<unsigned> xValDiff, yValDiff;
    unsigned diff = 0;
    unsigned idx  = 0;
    // First Sort By Largest X - Then Find All Differences
    std::stable_sort( towerLocations.begin(), towerLocations.end(), compareCoordsX );
    for ( ; idx < towerLocations.size(); ++idx ) {
        if ( idx == 0 ) {
            diff = gridSize.width - towerLocations[idx].x;
            xValDiff.push_back( diff );
        } else {
            diff = towerLocations[idx-1].x - towerLocations[idx].x - 1; // Don't Forget To Subtract 1
            xValDiff.push_back( diff );
        }
    }
    // Also Push Back (Last Value - 1)
    xValDiff.push_back( towerLocations.back().x - 1 );

    // Sort By Largest Y - Then Find All Differences
    // First Sort By Largest X - Then Find All Differences
    idx = 0;
    diff = 0;
    std::stable_sort( towerLocations.begin(), towerLocations.end(), compareCoordsY );
    for ( ; idx < towerLocations.size(); ++idx ) {
        if ( idx == 0 ) {
            diff = gridSize.height - towerLocations[idx].y;
            yValDiff.push_back( diff );
        } else {
            diff = towerLocations[idx-1].y - towerLocations[idx].y - 1; // Don't Forget To Subtract 1
            yValDiff.push_back( diff );
        }
    }
    // Also Push Back (Last Value - 1)
    yValDiff.push_back( towerLocations.back().y - 1 );

    unsigned largestX = xValDiff[0];
    unsigned largestY = yValDiff[0];
    idx = 0;
    for ( ; idx < towerLocations.size(); ++idx ) {  
        if ( xValDiff[idx] > largestX ) {
            largestX = xValDiff[idx];
        } 
        if ( yValDiff[idx] > largestY ) {
            largestY = yValDiff[idx];
        } 
    }    
    return (largestX * largestY);    
}

// Returns The Results Of All The Penalties For Each Case
std::vector<unsigned> getDefenderDataFromFile( const std::string& filename, unsigned& numTestCases, GridSize& gridSize, unsigned& numTowers, std::vector<TowerCoordinate>& towerLocations ) {
    std::ifstream file;
    file.open( filename );
    if ( !file.is_open() ) {
        // This ExceptionHandler will not work for you; you will need to supply your own error or exception handling.
        std::ostringstream strStream;
        strStream << __FUNCTION__ << " failed to read in file[" << filename << "]";
        throw ExceptionHandler( strStream );
    }

    file >> numTestCases;

    TowerCoordinate towerCoord;
    std::vector<unsigned> penalties;

    for ( unsigned t = 0; t < numTestCases; ++t ) {
        file >> gridSize.width;
        file >> gridSize.height;
        file >> numTowers;

        for ( unsigned c = 0; c < numTowers; ++c ) {
            file >> towerCoord.x;
            file >> towerCoord.y;
            towerLocations.push_back( towerCoord );
        }

        unsigned currentPenalty = calculatePenalties( towerLocations, gridSize );       
        penalties.push_back( currentPenalty );
        towerLocations.clear();         
    }
    file.close();    
    return penalties;
}

int main() {
    unsigned numTestCases = 0;
    unsigned numTowers    = 0;
    GridSize gridSize;
    std::vector<TowerCoordinate> towerLocations;
    std::vector<unsigned> penalties;

    penalties = getDefenderDataFromFile( "pieces.txt", numTestCases, gridSize, numTowers, towerLocations );

    unsigned idx = 0;
    for ( ; idx < penalties.size(); ++idx ) {
        std::cout << penalties[idx] << " ";
    }
    std::cout << std::endl;

    return 0;
}

The only thing that should be aware of this current implementation of this algorithm is that the tower location vector is cleared after each test case, so as soon as you get the final results of all penalties for the tower coordinate container for the current frame frame, it will consist only of the most recent set of positions and will not contain any previous iterations. And once again there are no boundaries for checking the coordinates of the tower relative to the size of the grid.