REC_SAM - EDITORIAL

editorial
, , ,
1

Problem

Problem REC_SAM Problem - CodeChef

CODE RUSH 1.0 Contest Link:Contest Page | CodeChef

Author: Abhinav
Tester: Abhinav
Editorialist: Krish Murarka

DIFFICULTY:

Hard

PREREQUISITES:

Dynamic Programing.

PROBLEM:

the sum of the perimeters of all the samosa were as close as possible to PP centimetres(cm), without going over. Samosa wala Bhaiya can decide whether to leave it as is, or make a single straight cut to separate it into two (not necessarily rectangular) halves with equal area.

EXPLANATION:

A Samosa with width W and height H has a perimeter of 2 × (W + H). If we make a straight cut of length C that divides the Samosa in half, each piece will have one side of length C, and the remaining sides of the pieces will represent the perimeter of the original Samosa. So, after cutting, we will have a combined perimeter X = 2 × (W + H + C).

Clearly X is smallest when we leave the Samosa alone. However, if we want to minimize X given that we are making a cut, we must minimize C; no cut can be smaller than the smallest of W and H, so we should cut through the midpoints of the two larger sides, which gives the cut a size of the smaller of the two sides. Then X = 2 × (W + H + min(W, H)). On the other hand, if we want to make a cut that maximizes X, we must maximize C by cutting through two opposite corners of the Samosa. Then C = sqrt(W2 + H2), so X = 2 × (W + H + sqrt(W2 + H2)). If we start our cut somewhere between one of those larger-side midpoints and a corner, we will get a value of X somewhere between these two extremes; since we can cut anywhere we want in that interval, we can get any intermediate value of X that we want.

So, depending on what we do with our Samosa, its contribution to our overall perimeter sum will either be 2 × (W + H), or a value in the range 2 × (W + H) + [2 × min(W, H), 2 × sqrt(W2 + H2)]. From now on, we will abbreviate the extremes of that range as [L, R]. (We could divide all values in the problem by 2 as well, removing that factor, but we will retain it in this analysis for clarity.)

SOLUTION

Setters Solution

#include
#include
#include
#include
using namespace std;

void backtrack(int cur_idx, double current, double buffer, double &best, const int &P,
const vector<vector > &samosa, const int &N) {
if (best == P) return;
if (current > P) return;
if (current + buffer >= P && P >= current) {
best = P;
return;
}
if (current + buffer > best) best = current + buffer;
if (cur_idx == N) return;
double min_cut = min(samosa[cur_idx][0], samosa[cur_idx][1]);
double max_cut = sqrt(pow(samosa[cur_idx][0], 2) + pow(samosa[cur_idx][1], 2));
backtrack(cur_idx + 1, current + 2min_cut, buffer + 2(max_cut - min_cut), best, P, samosa, N);
backtrack(cur_idx + 1, current, buffer, best, P, samosa, N);
}

double solve(int N, int P) {
vector<vector > samosa(N, vector(2));
double best = 0;
double diagonals = 0;
for (int i = 0; i < N; ++i) {
cin >> samosa[i][0] >> samosa[i][1];
best += 2*(samosa[i][0] + samosa[i][1]);
diagonals += 2*sqrt(pow(samosa[i][0], 2) + pow(samosa[i][1], 2));
}
if (diagonals + best <= P) {
return diagonals + best;
}
backtrack(0, best, 0, best, P, samosa, N);
return best;
}

int main() {

int T, N, P;
cin >> T;
while(T--) {
    cin >> N >> P;
    cout << setprecision(6) << fixed << solve(N, P) << endl;
}

}