Alex Stone Alex Stone - 1 year ago 38
C++ Question

Cyclical vector - Finding the least possible 'cost' (From CodeChef)

This is a question from Codechef but please bear with me.

The contest is for the preparation of the Zonal Computing Olympiad held in India, so its not a competitive contest from which I'd earn something as such. Just need a little help to see what is wrong with my code, because I have a feeling I've overlooked something big and stupid. :P

The problem basically states:

Imagine there is a vector or array such that the last element is
linked to the first one. Find the lowest possible sum from adding at
least one of each adjacent pairs of elements. (refer to link please)
So answer for {1,2,1,2,2} output would be 4 by adding 1+1+2.

Here is my solution:

Basically what it does is that it iterates backwards, from the end of the vector to the beginning, and stores the lowest possible sum that can be achieved from that vector onwards, in vector M. Done using dynamic programming, basically.

The first two elements of M are the possible answers. Then I do some checks to see which is possible. If M[1] is less than M[0] then the last element of the array/vector should have been included in the sum calculated in M[1].

#include <algorithm>
#include <iostream>
#include <vector>

#define print(arr) for(auto pos = arr.begin(); pos != arr.end(); ++pos) cout << *pos << " "; cout << endl;
typedef long long int ll;
using namespace std;

int main() {

int N;
ll x;
cin >> N;
vector <ll> A;
vector <ll> M(N+2);
for (int i = 0; i < N; i++) {
cin >> x;


for (int i = N-1; i >= 0; i--) {
M[i] = A[i]+*min_element(M.begin()+i+1, M.begin()+i+3);

if (M[0] <= M[1]) cout << M[0] << endl;
else if (M[1] < M[0]) {
if (M[N-1] <= (M[N-2])) cout << M[1] << endl;
else cout << M[0] << endl;


However, I could not pass 2 of the test cases in subtask 2. I think the last part of my code is incorrect. Any idea what I could be doing wrong? Either that, or I have misunderstood the question. The term "adjacent pairs" is sort of ambiguous. So if there are 4 numbers 3,4,5,6 does adjacent pairs mean adjacent pairs to be {(3,4) (4,5) (5,6) (6,3)} or {either (3,4) and (5,6) or (4,5) and (6,3)}? My code considers the former.

Answer Source

The idea in your M[i] array is "the minimum cost for a solution, assuming the index i is included in it".

The condition if (M[0] <= M[1]) means "if including index 0 is better than not including it, done".

If this condition doesn't hold, then, first of all, the check if (M[1] < M[0]) is superfluous - remove it. It won't fix any bugs, but will at least reduce confusion.

If the condition is false, you should output M[1], but only if it corresponds to a valid solution. That is, since index 0 is not chosen, the last index should be chosen. However, with your data structure it's impossible to know whether M[1] corresponds to a solution that chose last index - this information is lost.

To fix this, consider building two arrays - add e.g. an array L whose meaning is "the minimum cost for a solution, assuming the index i is included in it, and also index N-1 is included in it".

Then, at the end of your program, output the minimum of M[0] and L[1].