Tutorial•3 gün öncə

Educational Round #7 — Editorial

Read the number of judges $n$ and the number of athletes $m$ .

scanf("%d %d", &n, &m);

Process the data for each skater sequentially.

for (i = 0; i < m; i++)
{
  scanf("%d", &mas[0]);

Find the smallest $min$ and largest $ma x$ scores for the current $i$ -th skater.

  min = max = mas[0];
  for (j = 1; j < n; j++)
  {
    scanf("%d", &mas[j]);
    if (mas[j] > max) max = mas[j];
    if (mas[j] < min) min = mas[j];
  }

Compute:

The sum of the remaining scores in the variable $s u m$ .
The count of the remaining scores in the variable $c n t$ .

  sum = cnt = 0;
  for (j = 0; j < n; j++)

The smallest and largest scores are excluded from the computations.

    if ((mas[j] != min) && (mas[j] != max))
    {
      sum += mas[j];
      cnt++;
    }

Compute and print the average score for the $i$ -th skater.

  res = 1.0 * sum / cnt;
  printf("%.2lf ", res);
}
printf("\n");

Several seasons of hot summers and cold winters have significantly damaged Farmer John's fence for $n$ cows, which are lined up in a row and consecutively numbered from $1$ to $n$ . Each cow belongs to one of three breeds: $1$ — Holsteins, $2$ — Guernseys, $3$ — Jerseys. Farmer John asks you to count the number of cows of each breed within a given range.

Input. The first line contains two integers $n$ and $q (1 \leq n, q \leq 1 0^{5})$ .

Each of the next $n$ lines contains one integer, $1, 2$ , or $3$ , which is the breed identifier of the corresponding cow.

The following $q$ lines describe the queries, each consisting of two integers $a$ and $b (a \leq b)$ .

Output. For each of the $q$ queries $(a, b)$ , print a line containing three integers — the number of cows of each breed in the interval from $a$ to $b$ , inclusive.

Open problem

You are given two positive integers $n$ and $x$ .

You are required to choose $x$ distinct integers from $1$ to $n$ inclusive. The selection is made uniformly at random; that is, each possible $x$ -element subset of the set ${1, 2, \dots, n}$ is chosen with equal probability.

Let $S$ be the smallest integer among the selected $x$ numbers. Find the expected value of $2^{S}$ . In other words, determine the average value of $2$ raised to the power $S$ , where the average is taken over all possible selections of $x$ distinct integers.

Input. Two positive integers $n (1 \leq n \leq 50)$ and $x (1 \leq x \leq n)$ .

Output. Print the expected value of $2^{S}$ , rounded to $4$ digits after the decimal point.

Examples. In the first test case, there is only one possible selection: ${1, 2, 3, 4}$ . The minimum element is $1$ , so the required value is $2^{1} = 2$ .

In the second test case, there are three equally likely selections: ${1, 2}$ , ${1, 3}$ , and ${2, 3}$ . The corresponding values of $S$ are $1$ , $1$ , and $2$ . Therefore, the average value of $2^{S}$ is

(2^{1} + 2^{1} + 2^{2}) /3 = 8/3 = 2.6666666

Open problem

There are $C_{n}^{x}$ ways to choose $x$ distinct integers from $n$ .

Let us consider how many subsets of $x$ numbers have the minimum element equal to $i$ . For this, the subset must include the number $i$ , and additionally choose $x - 1$ numbers, each of which is strictly greater than $i$ . There are $n - i$ numbers greater than $i$ , and the number of ways to choose $x - 1$ numbers from them is $C_{n - i}^{x - 1}$ .

Note that the inequality $i + x - 1 \leq n$ must hold; otherwise, it is impossible to choose $x - 1$ numbers greater than $i$ . This leads to the constraint $i \leq n - x + 1$ .

To compute the expected value of the $2^{S}$ , we need to find the weighted average of this value over all possible subsets:

\frac{\sum _{i = 1}^{n} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}} = \frac{\sum _{i = 1}^{n - x + 1} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}}

If $i > n - x + 1$ , then the number of corresponding subsets is considered to be zero.

Example

In the first test case, there is only one possible selection: ${1, 2, 3, 4}$ . The minimum element is $1$ , so the required value is $2^{1} = 2$ .

In the second test case, there are three equally likely selections: ${1, 2}$ , ${1, 3}$ and ${2, 3}$ . The corresponding values of $S$ are $1$ , $1$ and $2$ . Therefore, the average value of the $2^{S}$ is

(2^{1} + 2^{1} + 2^{2}) /3 = 8/3 = 2.6666666

Now compute the required answer using the formula:

\frac{\sum _{i = 1}^{n} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}} = \frac{2 ^{1} \cdot C _{2}^{1} + 2 ^{2} \cdot C _{1}^{1}}{C _{3}^{2}} = \frac{2 \cdot 2 + 4 \cdot 1}{3} = \frac{8}{3}

Declare the constant infinity.

#define INF 0x3F3F3F3F

Declare the array of shortest distances $d i s t$ and the adjacency list of the graph $g$ . For each edge, store its weight ( $0$ or $1$ ) along with the adjacent vertex.

vector<int> dist;
vector<vector<pair<int, int> > > g;

The bfs function implements breadth-first search from the vertex $s t a r t$ .

void bfs(int start)
{
  dist = vector<int>(n + 1, INF);
  dist[start] = 0;

  deque<int> q;
  q.push_back(start);

  while (!q.empty())
  {
    int v = q.front(); q.pop_front();
    for (auto edge : g[v])
    {
      int to = edge.first;
      int w = edge.second;
      if (dist[to] > dist[v] + w)
      {
        dist[to] = dist[v] + w;

Depending on the weight of the edge $w$ , add vertex $t o$ to the end or the front of the queue.

        if (w == 1)
          q.push_back(to);
        else
          q.push_front(to);
      }
    }
  }
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &m);
g.resize(n + 1);
for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);

Assign a weight of $0$ to a directed edge $a \to b$ , and a weight of $1$ to the reverse edge.

  g[a].push_back({ b, 0 });
  g[b].push_back({ a, 1 });
}

Start the breadth-first search from the vertex $1$ .

bfs(1);

Print the answer — the shortest distance to vertex $n$ .

if (dist[n] == INF)
  printf("-1\n");
else
  printf("%d\n", dist[n]);

The transportation system of the city of Baku consists of $n$ intersections and $m$ bidirectional roads connecting them. Each road connects exactly two intersections, and there can be at most one road between any pair of intersections. Moreover, it is possible to travel between any two intersections using the existing roads.

The distance between two intersections is defined as the minimum number of roads among all possible paths connecting them.

The city mayor has decided to improve the transportation system and has instructed the director of the transportation department to build a new road. However, the mayor recently bought a new car and enjoys driving from home to work and back every day. He does not want the distance between intersection $s$ , where his home is located, and intersection $t$ , where his workplace is located, to decrease after the new road is built.

Help the director of the transportation department determine how many pairs of unconnected intersections exist such that if a road is built between them, the distance between $s$ and $t$ will not decrease.

Input. The first line contains four integers:

$n (1 \leq n \leq 1 0^{3})$ — the number of intersections,
$m (1 \leq m \leq 1 0^{5})$ — the number of roads,
$s$ — the intersection where the mayor's home is located,
$t (1 \leq s, t \leq n, s \neq = t)$ — the intersection where the mayor's workplace is located.

The next $m$ lines each contain two integers $u_{i}$ and $v_{i} (1 \leq u_{i}, v_{i} \leq n, u_{i} \neq = v_{i})$ , indicating that there is a bidirectional road between intersections $u_{i}$ and $v_{i}$ .

Output. Print the number of pairs of unconnected intersections such that adding a road between them will not decrease the distance between intersections $s$ and $t$ .

Open problem

Let's run a breadth-first search starting from the source vertex $s$ and the destination vertex $f$ . Store the shortest distances from $s$ in the array $d i s tS$ and from $f$ in the array $d i s tF$ .

Let $o pt D i s t an ce$ denote the shortest distance between $s$ and $f$ in the original graph.

Now, let's consider the possibility of building a new road between vertices $i$ and $j$ .

When adding a road $(i, j)$ to the graph, new paths are created:

s \to i \to j \to f w i t h l e n g t h d i s tS [i] + 1 + d i s tF [j], s \to j \to i \to f w i t h l e n g t h d i s tS [j] + 1 + d i s tF [i]

If at least one of these distances is smaller than $o pt D i s t an ce$ , then adding the road $(i, j)$ will decrease the shortest distance between $s$ and $f$ , and thus it is not suitable.

We now need to check all possible pairs $(i, j)$ and verify if adding a new road will decrease the shortest distance between $s$ and $f$ .

Example

The graph from the first test is shown on the left. The shortest distance from vertex $1$ to vertex $5$ is $4$ . No matter which new road we add, this distance will decrease. Therefore, none of the required roads exist.

The graph from the second test is shown on the right. The shortest distance from vertex $3$ to vertex $5$ is $2$ . The possible new roads are marked with bold lines. Regardless of which of these roads we build, the distance between $3$ and $5$ will not decrease.

Define the constant $M A X$ — the maximum possible number of vertices in the graph.

#define MAX 1001

Declare the adjacency matrix $g$ and the arrays for the shortest distances.

int g[MAX][MAX], distS[MAX], distF[MAX];

The function bfs performs a breadth-first search from the vertex $s t a r t$ . It takes the array $d i s t$ as input, where the shortest distances will be stored.

void bfs(int start, int *dist)
{

Initialize the array of shortest distances $d i s t$ .

  for (int i = 0; i <= n; i++) dist[i] = -1;
  dist[start] = 0;

Declare a queue $q$ and add the starting vertex $s t a r t$ to it.

  queue<int> q;
  q.push(start);

While the queue is not empty, dequeue the vertex $v$ .

  while (!q.empty())
  {

    int v = q.front(); q.pop();

Iterate through all vertices $t o$ adjacent to $v$ . If vertex $t o$ is not visited yet, compute the shortest distance $d i s t [t o]$ and add it to the queue.

    for (int to = 1; to <= n; to++)
      if (g[v][to] && dist[to] == -1)
      {
        q.push(to);
        dist[to] = dist[v] + 1;
      }
  }
}

The main part of the program. Read the input data.

scanf("%d %d %d %d", &n, &m, &s, &f);
memset(g, 0, sizeof(g));

Read the undirected graph.

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = g[b][a] = 1;
}

Run a breadth-first search from vertices $s$ and $f$ . The shortest distances are stored in the arrays $d i s tS$ and $d i s tF$ , respectively.

bfs(s, distS);
bfs(f, distF);

Let $o pt D i s t an ce$ denote the shortest distance between $s$ and $f$ in the original graph.

optDistance = distS[f];

Iterate through all pairs of vertices $i$ and $j$ and consider the possibility of building a new road between them. The variable $res$ keeps track of the number of such valid roads.

res = 0;
for (i = 1; i <= n; i++)
for (j = i + 1; j <= n; j++)

If there is no road between vertices $i$ and $j$ , compute the lengths of the shortest paths: $s \to i \to j \to f$ and $s \to j \to i \to f$ . If both of these distances are not less than $o pt D i s t an ce$ , then building such a road is allowed.

  if (g[i][j] == 0)
  {
     if ((distS[i] + distF[j] + 1 >= optDistance) &&
         (distS[j] + distF[i] + 1 >= optDistance))
       res++;
  }

Print the answer.

printf("%d\n", res);

Declare a structure for the graph edge (a pair of vertices and the edge weight). Declare a vector of edges $e$ .

struct Edge
{
  int u, v, dist;
};

vector<Edge> e;

Declare an array $p a re n t$ , that will be used in the disjoint-set data structure.

vector<int> parent;

The function Repr finds the representative of the set that contains vertex $n$ .

int Repr(int n)
{
  while (n != parent[n]) n = parent[n];
  return n;
}

The function Union unites the sets containing elements $x$ and $y$ .

int Union(int x, int y)
{
  x = Repr(x); y = Repr(y);
  if (x == y) return 0;
  parent[y] = x;
  return 1;
}

The function lt is a comparator for sorting the edges.

int lt(Edge a, Edge b)
{
  return (a.dist < b.dist);
}

The main part of the program. Initialize the $p a re n t$ array.

scanf("%d %d",&n,&m);
parent.resize(n + 1);
for (i = 1; i <= n; i++) parent[i] = i;

Read the edges of the graph.

e.resize(m);
for (i = 0; i < m; i++)
  scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].dist);

Sort the edges of the graph in increasing order of weights.

sort(e.begin(), e.end(), lt);

Run Kruskal's algorithm to construct the minimum spanning tree.

res = 0;
for(i = 0; i < m; i++)
  if (Union(e[i].u,e[i].v)) res += e[i].dist;

Print the weight of the minimum spanning tree.

printf("%d\n",res);

You need to cut a wooden stick into pieces. The most affordable company, The Analog Cutting Machinery, Inc. (ACM), charges money based on the length of the stick being cut. The procedure requires making only one cut at a time.

It is easy to see that different choices of the cutting order lead to different costs. For example, consider a stick of length $10$ meters that needs to be cut at $2$ , $4$ , and $7$ meters from one end. Consider a few options:

You could cut first at $2$ meters, then at $4$ meters, and finally at $7$ meters. This would result in a cost of $10 + 8 + 6 = 24$ , because the first piece was $10$ meters, the second $8$ meters, and the third $6$ meters.
In another option, if you first cut at $4$ meters, then at $2$ meters, and finally at $7$ meters, the cost would be $10 + 4 + 6 = 20$ , which is the better price.

Your boss trusts your computing skills to determine the minimal cost of cutting the given stick.

Input. The input consists of several test cases. The first line of each test case contains the length of the stick $l$ $(l < 1000)$ that needs to be cut. The next line contains the number of cuts $n$ $(n < 50)$ to be made.

The following line contains $n$ positive integers $c_{i}$ $(0 < c_{i} < l)$ , representing the positions for the cuts, given in strictly increasing order. A line with $l = 0$ denotes the end of the input data.

Output. Print the minimal cost of cutting the stick in the exact format given in the example.

Open problem

Let the array $m$ contain the cutting points: $m_{1}, ..., m_{n}$ . Add the start and end points: $m_{0} = 0$ and $m_{n + 1} = l$ .

Let the function $f (a, b)$ return the minimal cost of cutting a stick from $m_{a}$ to $m_{b}$ considering the necessary cutting points within the segment. There are no cutting points within the segment $[m_{a}; m_{a + 1}]$ , so $f (a, a + 1) = 0$ . The solution to the problem will be the value of $f (0, n + 1)$ . Store the computed values of $f (a, b)$ in the cells of the array $d p [a] [b]$ .

Let the segment of the stick $[m_{a}, m_{b}]$ be cut into several pieces. If the first cut is made at point $m_{i} (a < i < b)$ , the cost of the cut itself will be $m_{b} - m_{a}$ . Then, the remaining pieces need to be cut at the costs $f (a, i)$ and $f (i, b)$ , respectively. Choose $i$ to minimize the total cost:

f (a, b) = a < i < b min (f (a, i) + f (i, b)) + m_{b} - m_{a}

Example

Consider the second test case. Here is one possible way to cut a stick of length $10$ with a cost of $10 + 7 + 3 + 3 = 23$ :

Now, consider the optimal way to cut the stick, which has a cost of $10 + 6 + 3 + 3 = 22$ :

Declare constants and arrays.

#define MAX 55
#define INF 0x3F3F3F3F
int dp[MAX][MAX];
int m[MAX];

The function $f (a, b)$ returns the minimum cost of cutting a piece of stick on the segment $[a; b]$ at the cutting points located inside the segment.

int f(int a, int b)
{

If $a + 1 = b$ , then there are no cutting points within the segment $[a; b]$ . Return $0$ .

  if (b - a == 1) return 0;

If the value of $f (a, b)$ is already computed, return it.

  if (dp[a][b] != INF) return dp[a][b];

Make a cut at the point $i (a < i < b)$ . Compute the cost as follows:

f (a, b) = a < i < b min (f (a, i) + f (i, b)) + m_{b} - m_{a}

  for (int i = a + 1; i < b; i++)
    dp[a][b] = min(dp[a][b], m[b] - m[a] + f(a, i) + f(i, b));

Return the result $f (a, b) = d p [a] [b]$ .

  return dp[a][b];
}

The main part of the program. Read the input data for each test case.

while(scanf("%d",&l),l)
{
  scanf("%d",&n);

Add the start and end cutting points: $m_{0} = 0, m_{n + 1} = l$ .

  m[0] = 0; m[n+1] = l;
  for(i = 1; i <= n; i++)
    scanf("%d",&m[i]);

Initialize the $d p$ array.

  memset(dp,0x3F,sizeof(dp));

Find and print the answer.

  printf("The minimum cutting is %d.\n",f(0,n+1));
}

Near Pemberley Villa, located in the southern district of Byteland, there is a large pasture. Mrs. Darcy is concerned about her delicate plants, which could be trampled by strangers. Therefore, she decided to enclose certain areas of the pasture with triangular fences.

In Mrs. Darcy's basement, there are several fences. She forms each triangular area using exactly three fences, so that each side of the triangle corresponds to one fence. The fences are sturdy and beautiful, so she will not combine multiple fences to form a single side, nor will she cut a fence into shorter pieces. Mrs. Darcy's goal is to enclose the largest possible total area of the pasture.

Input. Each line contains a separate test case. The first number in the line is the number of fences $n (n \leq 16)$ that Mrs. Darcy has. The next $n$ integers, each between $1$ and $100$ , are the lengths of these fences.

Output. For each test case, print in a separate line the maximum area that can be enclosed using the available fences. The answer must be printed with $4$ decimal digits.

Examples. In the first test case, it is optimal to construct triangles with sides $(4, 5, 6)$ and $(7, 8, 9)$ . The total enclosed area in this case is $36.7544$ .

In the second test case, the answer is $0$ , since it is impossible to form any triangle.

In the third test case, a triangle with sides $(4, 4, 4)$ should be built. Note that fence lengths can repeat.

Open problem

The area of a triangle with sides $a, b$ and $c$ is computed in the function area using Heron's formula:

S = (p (p - a) (p - b) (p - c)), где p = (a + b + c) /2

Let $P$ be some subset of the available fence pieces. The function FindSol( $ma s k$ ) finds the maximum area that can be enclosed using triangles formed from the pieces in this subset.

The variable $ma s k$ represents a subset mask: it is a $16$ -bit number whose $i$ -th bit is equal to $1$ if the subset $P$ contains the piece $f e n ces [i]$ , and $0$ otherwise.

The answer to the problem is the value FindSol( $2^{n} - 1)$ , where $n$ is the number of elements in the array $f e n ces$ .

The values of all possible masks $ma s k$ lie in the range from $0$ to $2^{16} - 1$ (since, according to the constraints, there are no more than $16$ fence pieces). The array entry $b es t [ma s k]$ stores the maximum area that can be enclosed by the subset of fence pieces corresponding to the mask $ma s k$ .

To compute FindSol( $ma s k$ ) all possible triples of fence pieces $i, j, k$ that are present in $ma s k$ should be enumerated. For each triple, the triangle inequality is checked to ensure that a triangle can be formed from these pieces. If a triangle is possible, the following sum is computed:

a re a (f e n ces [i], f e n ces [j], f e n ces [k]) + F in d S o l (ma s k i, j, k)

Next, all such triples $(i, j, k)$ are considered, and the one for which this sum is maximal is selected. This maximum value is assigned to $b es t [ma s k]$ :

F in d S o l (ma s k) = (i, j, k) \in ma s k 0 \leq i < j < k < n max (a re a (f e n ces [i], f e n ces [j], f e n ces [k]) + F in d S o l (ma s k ∖ {i, j, k}))

If the lengths of the fence pieces are initially sorted, then when checking the triangle inequality (for a triangle with sides $f e n ces [i], f e n ces [j], f e n ces [k]$ ), it is sufficient to check only one condition:

f e n ces [i] + f e n ces [j] > f e n ces [k]

Since after sorting we have

f e n ces [i] \leq f e n ces [j] \leq f e n ces [k],

it always follows that

f e n ces [i] + f e n ces [k] > f e n ces [j] и f e n ces [j] + f e n ces [k] > f e n ces [i] .

Example

In the first test, the optimal triangles to construct have sides $(4, 5, 6)$ and $(7, 8, 9)$ . The total enclosed area in this case is $36.7544$ .

In the second test, the answer is $0$ , since no triangle can be formed from the available fences.

In the third test, a triangle with sides $(4, 4, 4)$ should be constructed. Note that fence lengths can be repeated.

Declare the global variables.

#define MAX 16
double best[1<<MAX];
int f[MAX+1];

The function area computes the area of a triangle using Heron's formula.

double area(int a, int b, int c)
{
  double p = (a + b + c) / 2.0;
  return sqrt(p * (p - a) * (p - b) * (p - c));
}

The function FindSol returns the maximum area that can be enclosed using triangles formed from the fences included in the mask $ma s k$ .

double FindSol(int mask)
{

If the value in the array $b es t [ma s k]$ is greater than or equal to zero, it has already been computed, and the function returns this value. This avoids redundant computations and speeds up the algorithm.

  if (best[mask] >= 0.0) return best[mask];

Initialize $b es t [ma s k] = 0$ .

  best[mask] = 0;

Iterate over all possible triples of indices $(i, j, k)$ such that the corresponding fences are included in $ma s k$ .

  for (int i = 0; i < n - 2; i++)     if (mask & (1 << i))
  for (int j = i + 1; j < n - 1; j++) if (mask & (1 << j))
  for (int k = j + 1; k < n; k++)     if (mask & (1 << k))

Check the triangle existence condition. Since the fences are initially sorted, this condition is sufficient to ensure that a triangle can be formed.

    if (f[i] + f[j] > f[k])

If the triangle exists, compute the sum:

the area of the current triangle $a re a (f [i], f [j], f [k])$ ;
plus the maximum area that can be enclosed with the remaining fences, excluding those used in this triple:

F in d S o l (ma s k^(1 << i)^(1 << j)^(1 << k))

      best[mask] = max(best[mask], area(f[i],f[j],f[k]) + 
          FindSol(mask ^ (1 << i) ^ (1 << j) ^ (1 << k)));
  return best[mask];
}

The main part of the program. Read the number of fences $n$ .

while (scanf("%d",&n) == 1)
{
  memset(f,0,sizeof(f));

Read the lengths of the fences and sort them in non-decreasing order.

  for (i = 0; i < n; i++) scanf("%d",&f[i]);
  sort(f,f + n);

Initialize the array $b es t$ .

  for (i = 0; i < (1 << MAX); i++) best[i] = -1.0;

Compute and print the answer.

  printf("%.4lf\n",FindSol((1 << n) - 1));
}

Vasya received a rectangular matrix of size $n \times m$ as a gift from his mother. Each cell of the matrix contains an integer. At first, Vasya enthusiastically played various mathematical games with the matrix: sometimes he would swiftly compute its determinant, and sometimes he would easily raise it to different powers.

However, he eventually got bored of such games and came up with a new pastime: Vasya chooses an integer $k$ and tries to find a submatrix of maximum area such that the sum of all its elements does not exceed $k$ . A submatrix is defined as a rectangular fragment of the original matrix.

Input. The first line contains three integers: $n$ , $m$ , and $k (1 \leq n, m \leq 300, 1 \leq k \leq 1 0^{9})$ .

The next $n$ lines each contain $m$ non-negative integers, each of which does not exceed $1000$ .

Output. Print a single integer — the area of the largest submatrix whose sum of elements does not exceed $k$ .

Open problem

Let $a$ be the input rectangular matrix. Create a two-dimensional array $d p$ of the same size, where $d p [i] [j]$ represents the sum of elements in the submatrix with opposite corners at points $(1, 1)$ and $(i, j)$ . The values in this array can be computed using the following formula:

d p [i] [j] = d p [i - 1] [j] + d p [i] [j - 1] - d p [i - 1] [j - 1] + a [i] [j]

Now consider a submatrix of array $a$ of size $w \times h$ . Let its opposite corners be located at coordinates $(i, j)$ and $(i + w - 1, j + h - 1)$ .

Then the sum of all elements in the submatrix is calculated using the formula:

d p [i + w - 1] [j + h - 1] - d p [i + w - 1] [j - 1] - d p [i - 1] [j + h - 1] + d p [i - 1] [j - 1]

Let's solve the problem using brute-force search. Iterate over all possible submatrix sizes $w \times h$ , as well as all valid coordinates of the top-left corner $(i, j)$ of the submatrix. Using the $d p$ array, compute the sum of elements inside the current submatrix in constant time. If this sum does not exceed $k$ , we keep track of the maximum area among all such submatrices.

However, this brute-force approach has a time complexity of $O (n^{4})$ , which is too slow. We can speed it up to $O (n^{3} l o g n)$ by applying binary search on the width $h$ of the submatrix.

Fix the top-left corner $(i, j)$ . Let $g (w, h)$ denote the sum of elements in the submatrix with corners at $(i, j)$ and $(i + w - 1, j + h - 1)$ . If we fix the height $w$ and treat the width $h$ as a variable, then $g (w, h)$ becomes a non-decreasing function with respect to $h$ , since the original matrix $a$ contains non-negative integers. This allows us to use binary search to find the maximum value of $h$ for which $g (w, h) \leq k$ .

Example

For example, the sum of the numbers in the submatrix with corners at points $(2, 2)$ and $(3, 3)$ is

48 - 19 - 19 + 7 = 17

The input matrix is stored in the array $a$ .

#define MAX 210
int a[MAX][MAX], dp[MAX][MAX];

The function $f (w, h)$ returns $1$ if there exists a submatrix of size $w \times h$ such that the sum of its elements does not exceed $k$ . To check this, all possible coordinates of the top-left corner $(i, j)$ are iterated over, and the sum of elements in the rectangle with corners at $(i, j)$ and $(i + w - 1, j + h - 1)$ is computed in constant time using the $d p$ array.

int f(int w, int h)
{
  for (int i = 1; i + w - 1 <= n; i ++)
  for (int j = 1; j + h - 1 <= m; j ++)
    if (dp[i + w - 1][j + h - 1] - dp[i + w - 1][j - 1] –
        dp[i - 1][j + h - 1] + dp[i - 1][j - 1] <= k) return 1;
  return 0;
};

The main part of the program. Read the input matrix.

scanf("%d %d %d",&n,&m,&k);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
  scanf("%d",&a[i][j]);

Based on the input matrix $a$ , compute the auxiliary matrix $d p$ .

for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
  dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j];

Iterate over the possible values of the submatrix width $w$ .

answer = 0;
for (w = 1; w <= n; w++)
{

The length of the submatrix is determined using binary search over the range $[l; r]$ .

  l = 1; r = m;
  while (l < r)
  {
    mid = (l + r) / 2;

For a submatrix of size $w \times mi d$ , iterate over all possible positions of its top-left corner $(i, j)$ . If there exists at least one position where the sum of elements in the submatrix does not exceed $k$ , update the value of the resulting area $an s w er$ .

    if (f(w,mid))
    {
      answer = max(answer, w * mid);
      l = mid + 1;
    } 
    else r = mid;
  }

  mid = (l + r) / 2;
  if (f(w,mid))
    answer = max(answer, w * mid);
};

Print the area of the largest submatrix found.

printf("%d\n",answer);

Şərhlər

Hələ də heç nə

Söhbəti başladan ilk siz olun!

Daxil ol

Yüklənir

Bir an, serverdən məlumat alınır