CCC '22 J5 - Square Pool

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem types
Canadian Computing Competition: 2022 Stage 1, Junior #5

Ron wants to build a square pool in his square N-by-N yard, but his yard contains T trees. Your job is to determine the side length of the largest square pool he can build.

Input Specification

The first line of input will be an integer N with N \ge 2. The second line will be the positive integer T where T < N^2. The remaining input will be T lines, each representing the location of a single tree. The location is given by two positive integers, R and then C, separated by a single space. Each tree is located at row R and column C where rows are numbered from top to bottom from 1 to N and columns are numbered from left to right from 1 to N. No two trees are at the same location.

The following table shows how the available 15 marks are distributed.

Marks AwardedLength/Width of YardNumber of Trees
3 marksN \le 50T = 1
5 marksN \le 50T \le 10
4 marksN \le 500\,000T \le 10
3 marksN \le 500\,000T \le 100

Output Specification

Output one line containing M which is the largest positive integer such that some M-by-M square contained entirely in Ron's yard does not contain any of the T trees.

Sample Input 1

5
1
2 4

Output for Sample Input 1

3

Explanation of Output for Sample Input 1

A picture of the yard is below. The location of the tree is marked by and one of several 3-by-3 squares that do not contain the tree is highlighted. All larger squares contain a tree.

Sample Input 2

15
8
4 7
4 1
14 11
10 6
13 4
4 10
10 3
9 14

Output for Sample Input 2

7

Explanation of Output for Sample Input 2

A picture of the yard is below. The location of each tree is marked by and one of several 7-by-7 squares that do not contain a tree is highlighted. All larger squares contain a tree.


Comments


  • 0
    epicgamergirl999  commented on Feb. 21, 2024, 5:24 p.m.

    J5, 10 points....


  • -1
    Alex_Tsvik  commented on Feb. 13, 2024, 4:28 p.m.

    Omg, 500000^2 cells in grid of Ron's yard. This is what brute force really is.


    • 0
      noahzho  commented on Feb. 15, 2024, 12:49 a.m.

      ignore comment i'm not thinking straight today


  • 6
    Archeiid  commented on Feb. 15, 2023, 11:38 a.m. edited

    I've been writting a functional method to find the maximum space available,for the whole afternoon.Yet nothing came out.This is a hard one...


  • 4
    Ethereal_Liu1029  commented on Oct. 22, 2022, 6:27 p.m.

    I have no idea why it always tell me index error