You are not logged in. Please login at www.codechef.com to post your questions!

×

Editorial to bribe the prisoner(Previous codejam problem)?

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.

asked 22 Apr '16, 23:00

arpit728's gravatar image

1★arpit728
6831968
accept rate: 10%

edited 25 May '16, 16:14


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

link

answered 25 May '16, 20:06

s4shyam95's gravatar image

5★s4shyam95
2086
accept rate: 20%

edited 25 May '16, 20:22

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;
}
link

answered 10 Jan, 21:18

krishna_keshav's gravatar image

3★krishna_keshav
1112
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,214
×1,664
×1,409
×1,236
×1,191
×513

question asked: 22 Apr '16, 23:00

question was seen: 2,535 times

last updated: 10 Jan, 21:18