RAILCTER - Editorial

editorial
,
1

Problem Link - Railway Caterers

Problem Statement

The government of Siruseri has just commissioned one of the longest and most modern railway routes in the world. This route runs the entire length of Siruseri and passes through many of the big cities and a large number of small towns and villages in Siruseri.

The railway stations along this route have all been constructed keeping in mind the comfort of the travellers. Every station has big parking lots, comfortable waiting rooms and plenty of space for eateries. The railway authorities would like to contract out the catering services of these eateries.

Unfortunately, catering contractors are not philanthropists and would like to maximise their profits. The Siruseri Economic Survey has done a through feasibility study of the different stations and documented the expected profits (or losses) for the eateries in all the railway stations on this route. Every contractor would like to run the catering service only in the profitable stations and stay away from the loss making ones.

On the other hand the authorities would like to ensure that every station was catered to. Towards this end, authorities offered to contract out stations in groups. They would fix a minimum size K and a contractor was only allowed to bid for any contiguous sequence of
K or more stations.

Approach

To solve this problem, we identify the contiguous group of K or more stations with the highest profit. Start by calculating the profit for the first K stations, which serves as the initial sum. As we move along the array, adjust the current sum by removing the station that moves out of the window and adding the one that enters. This ensures efficient tracking of the K- sized group without recalculating the entire sum. For groups larger than K, extend the current group by adding the next station’s profit while updating the maximum profit encountered. This dynamic approach maintains and updates the maximum profit for each group efficiently.

Time Complexity

The algorithm processes the list of stations in O(N), where N is the total number of stations, as we iterate through the array once.

Space Complexity

The space complexity is O(1) since only a fixed amount of extra space is used for variables.

2 
#include <algorithm>
#include <cassert>
#include <iostream>

static auto testcase(int N, int K, int *p, long sumK) {
	auto maxendshere = sumK;
	auto maxsofar = sumK;
	for(int i = K; i != N; ++i) {
		sumK += p[i] - p[i - K];
		maxendshere = std::max(sumK, maxendshere + p[i]);
		maxsofar = std::max(maxsofar, maxendshere);
	}
	return maxsofar;
}

 void processTestCase() {
    int N, K;
    std::cin >> N >> K;
    static constexpr int MAX_STATIONS = 1000000;
    assert(0 < N && N <= MAX_STATIONS);
    assert(0 < K && K <= N);

    static int profits[MAX_STATIONS];
    long initialSum = 0;
	static int p[D];
	long sumK = 0;
	{
		int i = 0;
		for(; i != K; ++i) {
			std::cin >> p[i];
			sumK += p[i];
		}
		for(; i != N; ++i)
			std::cin >> p[i];
	}
	std::cout << testcase(N, K, p, sumK) << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin.exceptions(std::ios::failbit | std::ios::badbit);
	testcase();
}