Mmedv8 months ago

Educational Round #7 — Editorial

Read the input data. Extract the bases and exponents for each number.

scanf("%d^%d %d^%d",&a,&b,&c,&d);

Compare the values of the logarithmized expressions $b \cdot l g a$ b \cdot lg a and $d \cdot l g c$ d \cdot lg c. Then print the answer.

if (b * log(1.0 * a) < d * log(1.0 * c)) printf("%d^%d\n",c,d);
else printf("%d^%d\n",a,b);

Open problem

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];
  }

C++

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");

Eolymp #11159. Breed Counting

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})$ q~(1 \le n, q \le 10^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)$ b~(a \le 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

Declare an array for storing prefix sums.

#define MAX 100001
int s[4][MAX];

Read the input data.

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

Compute the prefix sum arrays.

memset(s, 0, sizeof(s));
for (i = 1; i <= n; i++)
{
  scanf("%d", &x);
  for (j = 1; j <= 3; j++)
    s[j][i] = s[j][i - 1];
  s[x][i]++;
}

C++

Process the $q$ queries sequentially.

for (i = 0; i < q; i++)
{
   scanf("%d %d", &a, &b);
   printf("%d %d %d\n", s[1][b] - s[1][a - 1], s[2][b] - s[2][a - 1], 
                        s[3][b] - s[3][a - 1]);
}

Eolymp #11262. Expected Minimum Power

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}$ \{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}$ 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)$ n~(1 \le n \le 50) and $x (1 \leq x \leq n)$ x~(1 \le x \le n).

Output. Print the expected value of $2^{S}$ 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}$ \{1, 2, 3, 4\}. The minimum element is $1$ , so the required value is $2^{1} = 2$ 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}$ 2^S is

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

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

Open problem

The function Cnk computes the value of the binomial coefficient $C_{n}^{k}$ C_n^k. The values of the binomial coefficients will be stored in the cells of the array $d p$ .

long long dp[51][51];

long long Cnk(int n, int k)
{
  if (n == k) return 1;
  if (k == 0) return 1;
  if (dp[n][k] != -1) return dp[n][k];
  return dp[n][k] = Cnk(n - 1, k - 1) + Cnk(n - 1, k);
}

C++

The main part of the program.

scanf("%d %d", &n, &x);
memset(dp, -1, sizeof(dp));

Compute the answer: $\frac{\sum _{i = 1}^{n - x + 1} 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^x_n}.

a = 0;
for (i = 1; i <= n - x + 1; i++)
   a = a + Cnk(n - i, x - 1) * (1LL << i);
res = 1.0 * a / Cnk(n, x);

Print the answer.

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

Eolymp #10048. Reverse the graph

A directed graph with $n$ vertices and $m$ edges is given, with vertices numbered from $1$ to $n$ . Find the minimum number of edges that need to be reversed so that there exists at least one path from vertex $1$ to vertex $n$ .

Input. The first line contains two integers $n$ and $m (1 \leq n, m \leq 2 \cdot 1 0^{6})$ m~(1 \le n, m \le 2 \cdot 10^6) — the number of vertices and edges in the graph. Each of the following $m$ lines contains two integers $x_{i}$ x_i and $y_{i} (1 \leq x_{i}, y_{i} \leq n)$ y_i~(1 \le x_i, y_i \le n), indicating that the $i$ -th directed edge goes from vertex $x_{i}$ x_i to vertex $y_{i}$ y_i.

Output. Print the minimum number of edges that need to be reversed. If it is not possible to obtain a path from vertex $1$ to vertex $n$ , print $- 1$ .

Open problem

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;

C++

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);
      }
    }
  }
}

C++

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$ a → 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]);

Eolymp #9635. Transport system

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})$ n\ (1 \le n \le 10^3) — the number of intersections,
$m (1 \leq m \leq 1 0^{5})$ m\ (1 \le m \le 10^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)$ t\ (1 \le s, t \le n, s \ne t) — the intersection where the mayor's workplace is located.

The next $m$ lines each contain two integers $u_{i}$ u_i and $v_{i} (1 \leq u_{i}, v_{i} \leq n, u_{i} \neq = v_{i})$ v_i\ (1 \le u_i, v_i \le n, u_i \ne v_i), indicating that there is a bidirectional road between intersections $u_{i}$ u_i and $v_{i}$ 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

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]$ dist[to] 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;
      }
  }
}

C++

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$ optDistance 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 $r es$ 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$ s → i → j → f and $s \to j \to i \to f$ s → j → i → f. If both of these distances are not less than $o pt D i s t an ce$ optDistance, 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);

Eolymp #981. Minimum spanning tree

Find the weight of the minimum spanning tree for an undirected weighted connected graph.

Input. The first line contains the number of vertices $n$ and the number of edges $m$ ( $1 \leq n \leq 100$ 1 \leq n \leq 100, $1 \leq m \leq 6000$ 1 \leq m \leq 6000). Each of the following $m$ lines contains three integers $a$ , $b$ , $c$ , where $a$ and $b$ are the vertex numbers connected by an edge, and $c$ is the weight of the edge (a positive integer not exceeding $30000$ ).

Output. Print the weight of the minimum spanning tree.

Open problem

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 r e 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;
}

C++

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 r e 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);

Eolymp #11261. Cutting a stick

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$ 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$ 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)$ (l < 1000) that needs to be cut. The next line contains the number of cuts $n$ $(n < 50)$ (n < 50) to be made.

The following line contains $n$ positive integers $c_{i}$ c_i $(0 < c_{i} < l)$ (0 < c_i < l), representing the positions for the cuts, given in strictly increasing order. A line with $l = 0$ 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

Declare constants and arrays.

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

The function $f (a, b)$ 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$ 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)$ 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)$ 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}

f(a, b) = \min_{\substack{a<i<b}}(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]$ f(a, b) = dp[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.

  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));
}

Eolymp #1526. Grassland Fence

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)$ n~(n \le 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)$ (4, 5, 6) and $(7, 8, 9)$ (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)$ (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

S = \sqrt{(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]$ fences[i], and $0$ otherwise.

The answer to the problem is the value FindSol( $2^{n} - 1)$ 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$ 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]$ best[mask] 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$ 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 r e 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)

area(fences[i], fences[j], fences[k]) + FindSol(mask \ {i, j, k})

Next, all such triples $(i, j, k)$ (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]$ best[mask]:

F in d S o l (ma s k) = (i, j, k) \in ma s k 0 \leq i < j < k < n max (a r e 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}))

FindSol(mask) = \max_{\substack{(i,j,k) \in mask \\ 0 \le i < j < k < n}} (area(fences[i], fences[j],fences[k]) + FindSol(mask \setminus \{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]$ fences[i], fences[j], fences[k]), it is sufficient to check only one condition:

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

fences[i] + fences[j] > fences[k]

Since after sorting we have

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

fences[i] \le fences[j] \le fences[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] .

fences[i] + fences[k] > fences[j] и fences[j] + fences[k] > fences[i].

Example

In the first test, the optimal triangles to construct have sides $(4, 5, 6)$ (4, 5, 6) and $(7, 8, 9)$ (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)$ (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]$ best[mask] 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.

  best[mask] = 0;

Iterate over all possible triples of indices $(i, j, k)$ (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 r e a (f [i], f [j], f [k])$ area(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))

FindSol(mask~\hat{}~(1 << i)~\hat{}~(1 << j)~\hat{}~(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));
}

Eolymp #3535. Vasya and matrix

Vasya received a rectangular matrix of size $n \times m$ 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})$ k~(1 \le n, m \le 300,\ 1 \le k \le 10^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

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

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

The function $f (w, h)$ f(w, h) returns $1$ if there exists a submatrix of size $w \times h$ 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)$ (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;
};

C++

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; r].

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

For a submatrix of size $w \times mi d$ w \times mid, 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);
};

C++

Print the area of the largest submatrix found.

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

Educational Round #7 — Editorial

Comments