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

×

# Editorial to bribe the prisoner(Previous codejam problem)?

 0 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 1★arpit728 683●19●68 accept rate: 10%

 0 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 answered 25 May '16, 20:06 208●6 accept rate: 20%
 0 Brute force -  #include 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 > cells[i]; cout << "Case #" << t << ": " << findSum(prisoners, cells, 0) << endl; } return 0; }  answered 10 Jan, 21:18 1●1●1●2 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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