The Bookshelves Problem

general
1

Can someone tell me where i am doing wrong for this problem i am currently trying for K = 1.

My Code for Bookshelves Problem

2

I know that its from an ongoing contest but i feel its fine asking me this question because we have ZCO tomorrow and its an unrated contest.

3

I guess the problem is in the swap of the tallest books. Consider this input:
N=5,K=1, Shelf_1 = 14 1 1 1 1, Shelf_2 = = 7 4 5 3 2. Your code gives an output of 19 whereas the right answer is 16. Yous code is going to swap 7 from Shelf_1 and 1 from Shelf_2 rather if you swap 2 from Shelf_1 and 14 from shelf_2 you will get the right answer. I guess this is where you are going wrong. I hope this was helpful.(And yeah please upvote as I require them for asking questions)

1 Like
4

So here is how I solved it,

  • Sort both the shelfs after taking input
  • let the shelves be S1 and S2
  • So we will take S1 as the higher shelf and S2 as lower (higher in the sense it has more max elements)
  • Now we will swap the higher element of S2 with lowest possible value of S1 cause if we had unlimited number of swaps the final look of shelves will be in descending order or ascending order depending on how you sort it
  • then there is recursion if there is multiple number of swaps

Hope the code is self explanatory,

#include <iostream>
#include <vector>
#include <algorithm>

int swap(std::vector<int>highshelf,std::vector<int>lowshelf,int n,int swaps){
    int skew = highshelf[0]+lowshelf[0]; //the current skew
    if(swaps == 0){ //if no more swaps allowed then return the skew
        return skew;
    }
    int s = swaps;
    for(int i=n-1;i>=0;i--){
        //std::cout << i << " ";
        if(lowshelf[0] > highshelf[i]){ //comparing the maximum of a shelf to the elements of other from the end
            int temp =lowshelf[0];
            lowshelf[0] = highshelf[i];
            highshelf[i] = temp;
            swaps--; // the element is swapped , need to sort that again
            sort(highshelf.begin(),highshelf.end(),std::greater<int>());
            sort(lowshelf.begin(),lowshelf.end(),std::greater<int>());
            //std::cout << i << std::endl;
            break;
        }
    }
    // if it has achieved minimum skew otherwise go on
    if(s == swaps){
        swaps--;
    }
    return swap(highshelf,lowshelf,n,swaps);
}

int main(){
    int n,k;
    std::cin >> n >> k;

    std::vector<int>firstShelf(n);
    std::vector<int>secShelf(n);

    for(int i=0;i<n;i++){   
        std::cin >> firstShelf[i];
    }

    for(int i=0;i<n;i++){   
        std::cin >> secShelf[i];
    }

    //Sorting for easy swapping
    sort(firstShelf.begin(),firstShelf.end(),std::greater<int>());
    sort(secShelf.begin(),secShelf.end(),std::greater<int>());

    //Calculating by taking both as high as well as low
    int max1 = swap(firstShelf,secShelf,n,k);
    int max2 = swap(secShelf,firstShelf,n,k);

    if(max1 > max2){
        std::cout << max2 << std::endl;
    }else{
        std::cout << max1 << std::endl;
    }

    return 0;
}

Since we probably cant determine the which one is the lowest or which one is the highest shelf , we have do this twice.

5

Hi-Five I am also participating tomorrow.