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

×

REIGN2 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Kanstantsin Sokal
Tester: Jingbo Shang
Editorialist: Lalit Kundu

DIFFICULTY:

Easy-Medium

PREREQUISITES:

dynamic programming, greedy

PROBLEM:

There are $N$ castles that can be conquered by George. He has decided to conquer exactly $K$ castles during the next $K$ days, an aim he plans to achieve by conquering one castle every day for the next $K$ days.
As reported by King George's spies, $A_i + (j - 1) * B_i$ enemy knights will be protecting the $i^{th}$ castle during the $j^{th}$ day. When attacking a castle, if the King sends as many knights as those defending it, it's sufficient to be conquer that castle. Another requirement is that one knight cannot be sent to conquer two different castles.

As you are the king's trusted advisor, you can choose a set of $K$ castles, that the king should conquer. After you provide a set of castles, George will choose the order in which he will conquer them. You can assume that George always chooses the order which minimizes the total number of knights used during all the conquests.

Your task is to find the maximum possible total number of knights that can be used during the campaign and reached by delegating a set of $K$ castles to conquer. Also, you are not sure about the value of $K$, so you should find the optimal answer for each $K = 1, 2, ... , N$.

QUICK EXPLANATION:

======================
First sort arrays $A$ and $B$ in decreasing order of $B$ while preserving the mutual connectedness of $A_i$ and $B_i$. After that, we define $f(i, j)$ as maximum number of knights required for king to conquer a subset of $j$ castles from first $i$ castles. We can easily define recurrence relation and base cases of this DP solution.

EXPLANATION:

================
First of all let's observe the strategy of king. He is given a set of $K$ castles and two arrays $A_1, A_2, ..., A_K$ and $B_1, B_2, ..., B_K$ are given. For conquering castle $i$ on day $j$ he has to send $A_i + (j - 1)*B_i$ knights. His aim is to decide such an ordering of conquering such that total number of knights required is minimised.

Now, he has to pay $A_i$ for each castle $i$ independent of which day he conqueres it on. So, the ordering depends only on $B_i$. If we think of a greedy approach we should first conquer those castles with highest $B_i$ since, as the day number increases $(j-1)*B_i$ will also increase. So, this is the the strategy of king: Conquer all $K$ castles in non-increasing order of $B_i$.

Now, moving onto solving the problem. Let's solve for a particular $K$. So, we have to choose $K$ castles out of $N$ such that using king's approach maximum number of knights are used. Now, a greedy approach which selects only of basis of $A_i$ or $B_i$ would be certainly wrong. We should, by now, be thinking on terms of dynamic programming.

Now, if you remember subset sum DP, we kept our states as $(i, j)$ denoting that we are solving for first $i$ elements and we need to form a sum $j$. If we try to think on similar terms here, we should keep our states as $(i, j)$ denoting that we are solving for first $i$ elements and we need to select $j$ castles to maximise knights required according to king's strategy. Now, we have to make a decision that either we select $i^{th}$ castle or not. If we select it, do we know what its going to contribute i.e. how many knights are going to be required? For that we should know on which day king will conquer this castle. Now, here is the interesting part: if we sort the initial arrays in decreasing order of $B_i$, then we'll be sure that according to king's strategy $i^{th}$ castle will be conquered on last day because all other castles that will be selected will have $B_j$ less than $B_i$.

So, we first sort arrays $A$ and $B$ in decreasing order of $B$ while preserving the mutual connectedness of $A_i$ and $B_i$. After that, we define $f(i, j)$ as maximum number of knights required for king to conquer a subset of $j$ castles from first $i$ castles.

Recurrences can be define easily as:

f(i, j) = max(
        \\don't select i'th castle
        f(i - 1, j)

        \\select i'th castle, add the cost
        f(i - 1, j - 1) + (A[i] + (j - 1)*B[i])     
    )

Realising base cases is very easy. So, we calculate $f(N-1, i)$ for all $i = 1, 2, ..., N$ and print them.

COMPLEXITY:

================
Since there are $N^2$ states and transition cost between states is constant time, total complexity is $O(N^2)$.

PROBLEMS TO SOLVE:

================
KGP14D
KGP14H
MCHEF
CARDLINE

AUTHOR'S, TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 19 Sep '15, 20:15

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 09 Feb '16, 18:05

admin's gravatar image

0★admin ♦♦
19.8k350498541


Links for the solution not working. Please check.

link

answered 22 Sep '15, 18:25

codedog29's gravatar image

3★codedog29
556
accept rate: 0%

Can you please explain the first sample case ?

link

answered 21 Sep '15, 00:30

shank_punk's gravatar image

3★shank_punk
11
accept rate: 0%

For K = 1 Its optimal to choose the 4th castle as the king has only 1 option to send 5 knights. Any other castle will require less knights For K = 2 If we choose the 1st and 5th knight , the king will send 5 + 3 + 1 * 4 = 12 knights , any other pair of castle will result in less knights being sent For K = 3 If we choose the 1st , 2nd and 4th knight , the king will spend 5 * 0 + 1 + 4 * 1 + 3 + 5 + 4 * 2 = 21 knights For K = 4 We have no choice but to choose all the castles , so the king will spend (1 + 5 * 0) + (3 + 4 * 1) + (5 + 4 * 2) + (1 + 3 * 3) = 31 knights

(21 Sep '15, 15:02) rajat16037★

Cant view the tester and setters solution, please fix it.

link

answered 21 Sep '15, 15:07

theweblover007's gravatar image

2★theweblover007
10116
accept rate: 0%

For the second case :
for k = {1, 2} the knights in castles are :

K = 1 : 4, 6, 4, 4 3
K = 2 : 13, 12, 11, 13, 11

So for K = 2, how can answer be 17. I think the answer is 19 because in day 1, select 2nd castle and in day 2, select 1st castle .So 6 + 13 = 19).

Can any one explain this.

link

answered 22 Sep '15, 17:40

achaitanyasai's gravatar image

5★achaitanyasai
2.2k61748
accept rate: 10%

edited 22 Sep '15, 17:40

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:

×15,680
×2,172
×1,672
×1,000
×52
×2

question asked: 19 Sep '15, 20:15

question was seen: 3,169 times

last updated: 09 Feb '16, 18:05