JETHIA-Editorial

editorial
1

Problem Link
https://www.codechef.com/MEQI2021/problems/JETHIA

Author and Editorialist: Akash Anand
Tester: Aman Gupta

Difficulty
Easy

Prerequisites
Basic Programming, Mathematics

Explanation
The problem requires us to find the minimum and maximum area of the cake after cutting it into several pieces. We are also required to calculate the total number of pieces formed.
We know from the problem statement that cuts can only be made either parallel to the Y-axis (along the line X = A) or parallel to the X-axis (along the line Y = B).

Let’s consider two sets, X and Y, with the definition as follows -

  • Set X contains all the unique values of A in non-decreasing order, including 1 and N
  • Set Y contains all the unique values of B in non-decreasing order, including 1 and M
    Note that we would also include their respective boundary values to each set if it is not already included in the cuts.

Let’s first calculate the number of pieces -

Calculating number of pieces
Let’s define S(a), for any set a, to be the size of set a.
It can be easily observed that the number of vertical pieces is S(X)-1
And for each vertical piece, we are going to have S(Y)-1 total pieces.
Hence, for S(X)-1 vertical pieces, we have (S(X)-1)*(S(Y)-1) total pieces.

Therefore the total number of pieces are = (S(X)-1)*(S(Y)-1)

Calculating size of minimum and maximum piece
For calculating the size of min and max pieces, we can independently find the vertical and horizontal strips from which we are going to take the pieces. This can be done as follows-

  • Minimum piece
    Find the minimum distance between two consecutive values from the set X (This would give us the width of the rectangle of minimum area), let’s call it b_min.
    Find the minimum distance between two consecutive values from the set Y (This would give us the length of the rectangle of minimum area), let’s call it l_min.
    The size of the rectangular piece of the minimum area is l_min*b_min.

  • Maximum piece
    Find the maximum distance between two consecutive values from the set X (This would give us the width of the rectangle of maximum area), let’s call it b_max.
    Find the maximum distance between two consecutive values from the set Y (This would give us the length of the rectangle of maimum area), let’s call it l_max.
    The size of the rectangular piece of the maximum area is l_max*b_max.

Setter’s Code

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define fo(i,a,b) for(ll i = a; i < b ; i ++)
#define fs first
#define sc second
#define pb push_back

void prereq() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}

int main() {
  prereq();

  ll t;
  cin >> t;
  while (t--) {
    ll n, m, q;
    cin >> n >> m >> q;
    set <ll> x, y;
    fo(i, 0, q) {
      ll a, b;
      cin >> a >> b;
      x.insert(a);
      y.insert(b);
    }
    ll minx = INT_MAX, maxx = INT_MIN;
    ll miny = INT_MAX, maxy = INT_MIN;
    x.insert(n), y.insert(m), y.insert(1), x.insert(1);
    for (auto it = x.begin(); it != x.end(); ) {
      auto tempit = it;
      it++;
      if (it == x.end())break;
      if (*it - *tempit < minx)minx = *it - *tempit;
      if (*it - *tempit > maxx)maxx = *it - *tempit;
    }
    for (auto it = y.begin(); ; ) {
      auto tempit = it;
      it++;
      if (it == y.end())break;
      if (*it - *tempit < miny)miny = *it - *tempit;
      if (*it - *tempit > maxy)maxy = *it - *tempit;
    }
    cout << (x.size() - 1)*(y.size() - 1) << " " << minx*miny << " " << maxx*maxy << endl;

  }
}
1 Like