Like 0
Fork 0

Last active 1729868562

ProtyayMnd50 revised this gist 1729868561. Go to revision

1 file changed, 24 insertions

q2_last.cpp(file created)

@@ -0,0 +1,24 @@
1 + int findMinPairingCost(const vector<Segment>& segments) {
2 + int minCost = INT_MAX;
3 + int n = segments.size();
4 +
5 + if (n < 2) return -1;
6 +
7 + vector<Segment> sortedSegments = segments;
8 + sort(sortedSegments.begin(), sortedSegments.end(), [](const Segment& a, const Segment& b) {
9 + return a.R < b.R || (a.R == b.R && a.L < b.L);
10 + });
11 +
12 + int minSingleCost = INT_MAX;
13 +
14 + for (int i = 0; i < n; i++) {
15 + for (int j = 0; j < i; j++) {
16 + if (sortedSegments[j].R < sortedSegments[i].L) {
17 + int pairCost = sortedSegments[i].cost * sortedSegments[j].cost;
18 + minCost = min(minCost, pairCost);
19 + }
20 + }
21 + }
22 +
23 + return minCost == INT_MAX ? -1 : minCost;
24 + }

ProtyayMnd50 revised this gist 1729866866. Go to revision

1 file changed, 41 insertions, 44 deletions

q2.cpp

@@ -2,56 +2,53 @@
2 2 #include <vector>
3 3 #include <algorithm>
4 4 #include <climits>
5 - #include<bits/stdc++.h>
6 -
5 + #include <bits/stdc++.h>
7 6 using namespace std;
8 -
9 7 #define ll long long
10 -
11 - // Struct to represent a segment with L, R, and cost
12 - struct Segment {
13 - int L, R, cost;
14 - Segment(int left, int right, int c) : L(left), R(right), cost(c) {}
15 - };
16 -
17 - // Function to calculate the minimum product of valid non-overlapping segments
18 - long long findMinCostProduct(const vector<Segment> &segments) {
19 - int N = segments.size();
20 -
21 - // Sorting by left endpoint (L)
22 - vector<Segment> sortedByL = segments;
23 - sort(sortedByL.begin(), sortedByL.end(), [](Segment a, Segment b) {
24 - if (a.L != b.L) return a.L < b.L;
25 - return a.R < b.R;
26 - });
27 -
28 - // Sorting by right endpoint (R)
29 - vector<Segment> sortedByR = segments;
30 - sort(sortedByR.begin(), sortedByR.end(), [](Segment a, Segment b) {
31 - if (a.R != b.R) return a.R < b.R;
32 - return a.L < b.L;
33 - });
34 -
35 - long long minCostSeen = LLONG_MAX; // Store the minimum cost of valid non-overlapping segments
36 - long long minProduct = LLONG_MAX; // Store the minimum product of costs for valid pairs
37 -
38 - int rIndex = 0;
39 -
40 - // Iterate over sortedByL (by left endpoint)
41 - for (const Segment &current : sortedByL) {
42 - // Check for valid non-overlapping segments (sortedByR's R < current.L)
43 - while (rIndex < N && sortedByR[rIndex].R < current.L) {
44 - minCostSeen = min(minCostSeen, (long long)sortedByR[rIndex].cost);
45 - ++rIndex;
8 + # updated
9 + ll minCostProduct(const vector<vector<ll>> &seg)
10 + {
11 + int n = seg.size();
12 +
13 + // Sort by starting endpoint (L)
14 + vector<vector<ll>> sortedL = seg;
15 + sort(sortedL.begin(), sortedL.end(), [](const vector<ll> &a, const vector<ll> &b)
16 + {
17 + if (a[0] != b[0])
18 + return a[0] < b[0];
19 + return a[1] < b[1]; });
20 +
21 + // Sort by ending endpoint (R)
22 + vector<vector<ll>> sortedR = seg;
23 + sort(sortedR.begin(), sortedR.end(), [](const vector<ll> &a, const vector<ll> &b)
24 + {
25 + if (a[1] != b[1])
26 + return a[1] < b[1];
27 + return a[0] < b[0]; });
28 +
29 + ll minCost = LLONG_MAX; // Minimum cost of valid non-overlapping segments
30 + ll minProd = LLONG_MAX; // Minimum product of costs for valid pairs
31 +
32 + int r = 0;
33 +
34 + // Iterate over sortedL (by left endpoint)
35 + for (const auto &cur : sortedL)
36 + {
37 + // Check for valid non-overlapping segments (sortedR's R < cur.L)
38 + while (r < n && sortedR[r][1] < cur[0])
39 + {
40 + minCost = min(minCost, sortedR[r][2]); // sortedR[r][2] is the cost
41 + ++r;
46 42 }
47 43
48 - // If a valid segment is found, calculate the product of costs
49 - if (minCostSeen != LLONG_MAX) {
50 - long long product = minCostSeen * (long long)current.cost;
51 - minProduct = min(minProduct, product);
44 + // Calculate the product of costs if a valid segment is found
45 + if (minCost != LLONG_MAX)
46 + {
47 + ll prod = minCost * cur[2];
48 + minProd = min(minProd, prod);
52 49 }
53 50 }
54 51
55 52 // Return the result
56 - return (minProduct != LLONG_MAX) ? minProduct : -1; // Return -1 if no valid pair is found
53 + return (minProd != LLONG_MAX) ? minProd : -1; // Return -1 if no valid pair is found
57 54 }

ProtyayMnd50 revised this gist 1729866101. Go to revision

1 file changed, 57 insertions

q2.cpp(file created)

@@ -0,0 +1,57 @@
1 + #include <iostream>
2 + #include <vector>
3 + #include <algorithm>
4 + #include <climits>
5 + #include<bits/stdc++.h>
6 +
7 + using namespace std;
8 +
9 + #define ll long long
10 +
11 + // Struct to represent a segment with L, R, and cost
12 + struct Segment {
13 + int L, R, cost;
14 + Segment(int left, int right, int c) : L(left), R(right), cost(c) {}
15 + };
16 +
17 + // Function to calculate the minimum product of valid non-overlapping segments
18 + long long findMinCostProduct(const vector<Segment> &segments) {
19 + int N = segments.size();
20 +
21 + // Sorting by left endpoint (L)
22 + vector<Segment> sortedByL = segments;
23 + sort(sortedByL.begin(), sortedByL.end(), [](Segment a, Segment b) {
24 + if (a.L != b.L) return a.L < b.L;
25 + return a.R < b.R;
26 + });
27 +
28 + // Sorting by right endpoint (R)
29 + vector<Segment> sortedByR = segments;
30 + sort(sortedByR.begin(), sortedByR.end(), [](Segment a, Segment b) {
31 + if (a.R != b.R) return a.R < b.R;
32 + return a.L < b.L;
33 + });
34 +
35 + long long minCostSeen = LLONG_MAX; // Store the minimum cost of valid non-overlapping segments
36 + long long minProduct = LLONG_MAX; // Store the minimum product of costs for valid pairs
37 +
38 + int rIndex = 0;
39 +
40 + // Iterate over sortedByL (by left endpoint)
41 + for (const Segment &current : sortedByL) {
42 + // Check for valid non-overlapping segments (sortedByR's R < current.L)
43 + while (rIndex < N && sortedByR[rIndex].R < current.L) {
44 + minCostSeen = min(minCostSeen, (long long)sortedByR[rIndex].cost);
45 + ++rIndex;
46 + }
47 +
48 + // If a valid segment is found, calculate the product of costs
49 + if (minCostSeen != LLONG_MAX) {
50 + long long product = minCostSeen * (long long)current.cost;
51 + minProduct = min(minProduct, product);
52 + }
53 + }
54 +
55 + // Return the result
56 + return (minProduct != LLONG_MAX) ? minProduct : -1; // Return -1 if no valid pair is found
57 + }

ProtyayMnd50 revised this gist 1729865262. Go to revision

1 file changed, 6 insertions, 7 deletions

q3.cpp

@@ -1,19 +1,18 @@
1 1 int minMoves(vector<int>arr, int n, int k) {
2 - // Sort the array
2 +
3 3 sort(arr.begin(), arr.end());
4 4
5 5 int i = 0, j = n - 1;
6 6 int moves = 0;
7 -
8 - // Two pointers approach
7 +
9 8 while (i <= j) {
10 - // If the lightest and heaviest together are within the limit, move both
9 +
11 10 if (arr[i] + arr[j] <= k) {
12 - i++; // move the lighter object
11 + i++;
13 12 }
14 - // Move the heavier object (j--)
13 +
15 14 j--;
16 - // Count one move
15 +
17 16 moves++;
18 17 }
19 18

ProtyayMnd50 revised this gist 1729864987. Go to revision

2 files changed, 21 insertions, 2 deletions

hello.cpp (file deleted)

@@ -1,2 +0,0 @@
1 - #include <bits/stdc++/h>
2 - using namespace std;

q3.cpp(file created)

@@ -0,0 +1,21 @@
1 + int minMoves(vector<int>arr, int n, int k) {
2 + // Sort the array
3 + sort(arr.begin(), arr.end());
4 +
5 + int i = 0, j = n - 1;
6 + int moves = 0;
7 +
8 + // Two pointers approach
9 + while (i <= j) {
10 + // If the lightest and heaviest together are within the limit, move both
11 + if (arr[i] + arr[j] <= k) {
12 + i++; // move the lighter object
13 + }
14 + // Move the heavier object (j--)
15 + j--;
16 + // Count one move
17 + moves++;
18 + }
19 +
20 + return moves;
21 + }

ProtyayMnd50 revised this gist 1729863353. Go to revision

1 file changed, 2 insertions

hello.cpp(file created)

@@ -0,0 +1,2 @@
1 + #include <bits/stdc++/h>
2 + using namespace std;
Newer Older

Powered by Opengist ⋅ Load: 36ms⋅

English
⋅ Discord