Блог пользователя Lance_HAOH

HackerRank Problem: Max Score — Why do we not consider all permutations of a set?
Автор Lance_HAOH, история, 7 лет назад, По-английски

Hi. I am having problem trying to upsolve the "Max Score" problem which was used in HackerRank's Rookie Rank 3.

Here is the link to the problem.

After reading the editorial, I am puzzled why the recurrence does not consider all permutations of elements in subset(S,i) because the order in which we choose the elements in the subset also affects the overall sum.

For easier reference, I have reproduced the puzzling part of the editorial here. Credits to HackerRank for the editorial.

I tried asking in the problem's forum but I have not received any reply for more than 3 weeks. Could someone please advise me why we do not need to consider all permutations of elements?

Thanks in advance.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The Editorial is right and it's recursively going all permutations! The recursion call is a little tricky here. Look at the loop 

for (int i = 0; i < n; ++i) {
        if (bits & (1 << i)) {
            solve(bits ^ (1 << i));
            dp[bits] = max(dp[bits], (dp[bits ^ (1 << i)]) + (sum - a[i]) % a[i]);
        }
    }

for every a[i] removed last from this sub-sequence(bit) it is calculating its optimal result. If a[i] is removed last then the runningSum should be all sub-sequence sum — a[i]. The main point is when a[i] is removed last the result would be this -> solve(bits ^ (1 << i)) + (sum — a[i]) % a[i]). I think you can get it now.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hmm. If I understood the editorial correctly, the algorithm will obtain the optimal value for a particular subset by trying all possible valid subsets with 1 missing element. But that way of calculating isn't specific enough. Before we add the last element to each valid subset, we have to consider the ordering of the elements before the last element is added to the subset. So I was thinking that we must consider all possible permutations of the elements in a valid subset that is missing one element before adding the last element.

    However, the code that you have presented shows that the algorithm does not consider different orderings of elements because it sees the same set "bits" as the same state which shouldn't be the case right?

    Please advise.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      sorry for my late response ( I have just seen your post notification in my gmail ).

      editorial's code of solve function

      void solve(int bits) {
    if (dp[bits] != -1) return;

    ll sum = 0;
    for (int i = 0; i < n; ++i) {
        if (bits & (1 << i)) {
            sum += a[i];
        }
    }
    for (int i = 0; i < n; ++i) {
        if (bits & (1 << i)) {
            solve(bits ^ (1 << i));
            dp[bits] = max(dp[bits], (dp[bits ^ (1 << i)]) + (sum - a[i]) % a[i]);
        }
    }
}

      Let's find an easy explanation. If we simplify the code given in the editorial and remove the memoization part and replace bit with array just for simplicity then the solve() function's pseudo code would be like..

      void solve( int arr[] )
{
    if(arr.length==0) return;
    for(int i = 0; i<arr.length; i++)
        solve( arr but without arr[i] );    // one element reduces
}

      we can simplify it more like..

      void solve( int n )
{
    if(n==0) return;
    for(int i = 0; i<n; i++)
        solve( n - 1 );
}

      You see, the complexity of the above code is O(n!) isn't it? !!!!! Here comes the all permutations. Memoization part just reduces the complexity to n * 2^n; The Traveling Salesman Problem is an NP — complete problem with complexity n! also. But memoization reduces it to n * 2^n :)

      Happy_Coding :)

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Thank you so much for your help! I managed to understand and solve this problem. I was formulating the DP problem the wrong way, causing me to be unable to understand the solution.

        At first, I thought that we need to memoize some ordering of the elements. But apparently, that is not possible as the number of permutations grow very quickly and there are no overlapping subproblems if I try to view the problem as choosing some optimal ordering of elements.

        I changed my problem statement to finding the optimal value for some subset of the original array. Clearly, we need to find the optimal value for the biggest subset (which is the whole array). But the optimal value of the bigger subset depends upon smaller subsets. Equal subsets will have the same optimal value. Hence, we now have overlapping subproblems. In order to calculate the optimal value for each of the subsets, we calculate the optimal value of a subset A as MAX{ S | S is a subset with 1 missing element from A}. At each step, all we need to do is to remove 1 bit from the subset and recurse. But the recursion is exactly searching all possible permutations! Hence, the answer will be correct.

        → Ответить