CCC '22 J5 - Square Pool - Olympiads Online Judge

CCC '22 J5 - Square Pool

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$ $N$ -by- $N$ $N$ yard, but his yard contains $T$ $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$ $N$ with $N \ge 2$ $N \geq 2$ . The second line will be the positive integer $T$ $T$ where $T < N^2$ $T < N^{2}$ . The remaining input will be $T$ $T$ lines, each representing the location of a single tree. The location is given by two positive integers, $R$ $R$ and then $C$ $C$ , separated by a single space. Each tree is located at row $R$ $R$ and column $C$ $C$ where rows are numbered from top to bottom from $1$ $1$ to $N$ $N$ and columns are numbered from left to right from $1$ $1$ to $N$ $N$ . No two trees are at the same location.

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

Marks Awarded	Length/Width of Yard	Number of Trees
$3$ $3$ marks	$N \le 50$ $N \leq 50$	$T = 1$ $T = 1$
$5$ $5$ marks	$N \le 50$ $N \leq 50$	$T \le 10$ $T \leq 10$
$4$ $4$ marks	$N \le 500\,000$ $N \leq 500 000$	$T \le 10$ $T \leq 10$
$3$ $3$ marks	$N \le 500\,000$ $N \leq 500 000$	$T \le 100$ $T \leq 100$

Output Specification

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

Sample Input 1

Copy

5
1
2 4

Output for Sample Input 1

Copy

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$ $3$ -by- $3$ $3$ squares that do not contain the tree is highlighted. All larger squares contain a tree.

Sample Input 2

Copy

Output for Sample Input 2

Copy

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$ $7$ -by- $7$ $7$ squares that do not contain a tree is highlighted. All larger squares contain a tree.

Comments

-5

Abyss_123 commented 93 days ago

solved in 5 min and got 5.3/10 due to memory limit ... i cant figure it out anymore

This comment is hidden due to too much negative feedback. Show it anyway.

1

epicgamergirl999 commented on Feb. 21, 2024, 5:24 p.m. ← edited →

J5, 10 points....

4

Alex_Tsvik commented on Feb. 13, 2024, 4:28 p.m. ← edited →

Omg, $500\,000^2$ $500 000^{2}$ cells in grid of Ron's yard. This is what brute force really is.

1

noahzho commented on Feb. 15, 2024, 12:49 a.m. ← edited →

ignore comment i'm not thinking straight today

9

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...

6

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

I have no idea why it always tell me index error