Alex Stone - 2 months ago 8

C++ Question

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

https://www.codechef.com/ZCOPRAC/problems/ZCO12004

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);

fill(M.begin(),M.end(),0);

for (int i = 0; i < N; i++) {

cin >> x;

A.push_back(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

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]`

.

Source (Stackoverflow)

Comments