Editorial to bribe the prisoner(Previous codejam problem)?

general
, , , , ,
1

can anyone write editorial to the problem https://code.google.com/codejam/contest/189252/dashboard#s=p2

this is the problem from previous codejam. I tried to refer the eeditorial in contest analysis section, but it’s to vaguely written so I didn’t get it.

2

Let us first discuss a slightly inefficient approach which is more intuitive and then move to a optimized approach.

Let dp[i][j] be the number of gold coins to be used if prisoners in range [i,j] are considered.

So for every range [i,j], we iterate the number of prisoners in this range that need to be released.

For each such prisoner, we assume that this is the first prisoner to be released in the range,
and hence solve for further subproblems on either side of the removed prisoner.

Here is a bottom up implementation for the same : Solution

Complexity is

Time : O(P2Q),

Memory : O(P2)

The key observation to reduce both Time and memory complexity is that we do not need to save every state, only states with dp[i][j] where i and j are a prisoner or a it’s neighbour or the edge(0 or P-1) matter, and hence we can use a top down approach along with a map, as mentioned in the editorial there to get the code to run optimally : Optimized Solution

Complexity is

Time : O(Q3Log(Q3)),

Memory : O(Q2)

**Log is added due to map access

3

Brute force -

    #include <bits/stdc++.h>
using namespace std;
int P, Q;

bool allReleased(bool prisoners[], int cells[])
{
    for(int i = 0 ; i < Q ; ++i)
        if(!prisoners[cells[i]])
            return 0;
    return 1;
}

int countMedals(bool prisoners[], int cell)
{
    int ans = 0;
    for(int i = cell - 1 ; i >= 1 ; --i)
    {
        if(prisoners[i])
            break;
        ans++;
    }
    
    for(int i = cell + 1 ; i <= P ; ++i)
    {
        if(prisoners[i])
            break;
        ans++;
    }
    return ans;
}


int findSum(bool prisoners[], int cells[], int totalMedals)
{
    if(allReleased(prisoners, cells))
        return totalMedals;
    int ans = INT_MAX;
    for(int i = 0 ; i < Q ; ++i)
    {
        if(!prisoners[cells[i]])
        {
            prisoners[cells[i]] = true;
            ans = min(ans, findSum(prisoners, cells, totalMedals + countMedals(prisoners, cells[i])));
            prisoners[cells[i]] = false;
        }
    }
    return ans;
}
int main()
{
    //cout << "Hello World!" << endl;
    int T;
    cin >> T;
    for(int t = 1 ; t <= T ; ++t)
    {
        cin >> P >> Q;
        bool prisoners[P+1];
        int cells[Q];
        for(int i = 0 ; i <= P ; ++i)
            prisoners[i] = 0;
        
        for(int i = 0 ; i <Q ; ++i)
            cin >> cells[i];
        
        cout << "Case #" << t << ": " << findSum(prisoners, cells, 0) << endl;
    }
    return 0;
}