SHOPTRIP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Kamil Debowski
Primary Tester: Marek Sokołowski
Secondary Tester: Praveen Dhinwa
Editorialist: Praveen Dhinwa

DIFFICULTY:

easy

PREREQUISITES:

dp, bitmask

PROBLEM:

There are n shops, i-th of which is located at the coordinates (x_i, y_i) . There are k ingredients numbered from 1 to k. Each shop contains some of these ingredients, which is given by a binary string s_i of k characters. If s[i][j] = 1, then it means that j-th ingredient is present in i-th shop. You want to collect all the k ingredients by visiting some shops starting from coordinates (0, 0) and finishing your journey by coming at (0, 0) again. You want to travel the least possible distance in this journey. Find out the least distance of your journey to collect all the ingredients. If it is not possible to collect all the ingredients, output -1.

The relationship with traveling salesman problem.

This problem have quite a few similarities with a very famous problem, traveling salesman problem, also called TSP.
TSP is about finding an minimum distance route for a salesman that starts from a city and wants to visit all the cities and come back at the starting city.
There can be many possible orders of visiting the cities. Suppose that there were only k cities with each ingredient being present in one of the cities only.
In that case, our problem is same as solving the TSP problem.

The easy -1 case.

Let us first check the answer being -1 case, i.e. it is impossible to collect all the ingredients even by visiting all the shops. This will happen only when there is some ingredient which is not present in any of the shops.

Start with brute force solution

The bruteforce solution will be try all subset of the shops to visit and trying all possible orders of the shops in the subset to visit. It will take \mathcal{O}(\sum_{i=1}^{n} 2^i * i!), which has no remote chance of passing in time for n = 36 and k = 12.

Think of a dp solution

Let us think of our journey. We simulate our journey and we must remember the important information of our journey till now as a state of dp. We started from (0, 0) and suppose we have visited some set of shops, and we also know the set of ingredients collected, now we try to take the next shop to visit to continue our journey. We also need to know the last shop on which we were, so that after we decide to visit some shop, we are able to find the distance from the last shop to this shop to compute the distance of the journey. When we have collected all the ingredients, we will finally go to coordinate (0, 0) and finish our journey.

We will try to write the above observations as a dp solution. Our dp state will be the set of shops visited, set of ingredients visited and the last shop that we visited in the journey.

dp(shopSet, ingredientSet, lastShop):
    if (ingredientSet has size k):
        return distance(lastShop, (0, 0))
    else:
        ans = infinity;
        for i = 1 to n:
            if (i not in shopSet):
                let d = distance between lastShop and shop i.
                Let newShopSet be shopSet + shop i added in it.
                Let newIngredientSet be ingredientSet + ingredients at shop i added in it.
                ans = min(ans, d + dp(newShopSet, newIngredientSet, i));
        return ans;

Space complexity of this approach is \mathcal{O}(2^n \cdot 2^k \cdot n) and the time complexity will be \mathcal{O}(2^n \cdot 2^k \cdot n^2). This is still too much to pass in time.

Optimizing the dp solution by removing the redundant state parameters

Do you really need to maintain ingredientSet when you are already maintaining shopSet? The set of ingredients can be easily found if you know the set of shops. So, maintaining ingredientSet when you are maintaining shopSet is redundant. We can remove it from our state. The updated solution becomes.

dp(shopSet, lastShop):
    ingredientSet = {};
    for each shop s: ingredientSet:
        add the ingredients in s to ingredientSet
    if (ingredientSet has size k):
        return distance(lastShop, (0, 0))
    else:
        ans = infinity;
        for i = 1 to n:
            if (i not in shopSet):
                let d = distance between lastShop and shop i.
                Let newShopSet be shopSet + shop i added in it.
                ans = min(ans, d + dp(newShopSet, i));
        return ans;

Space complexity of this approach is \mathcal{O}(2^n \cdot n) and the time complexity will be \mathcal{O}(2^n \cdot n \cdot n \cdot k). Still too much to pass in time :(.

Further optimizing the dp solution

Do you really need to maintain shopSet, can you just do away with just maintaining ingredientSet? Suppose we maintain ingredientSet and lastShop in our dp state. From the last shop, we will try each possible shop as the next shop to visited and will try to visit that and update the ingredientSet correspondingly. Note that it might happen that we might visit some shop more than once in this, but that’s allowed in the problem, so we don’t have any issue whatsoever. Our solution becomes:

dp(ingredientSet, lastShop):
    if (ingredientSet has size k):
        return distance(lastShop, (0, 0))
    else:
        ans = infinity;
        for i = 1 to n:
            if (i != lastShop):
                let d = distance between lastShop and shop i.
                Let newIngredientSet be ingredientSet + ingredients of shop i added in it.
                ans = min(ans, d + dp(newIngredientSet, i));
        return ans;

Now, there is a little caveat in this solution. The dp states are cyclic. Assume your current ingredientSet is I and the last shop is s. Suppose that you choose some next shop i, and this shop doesn’t contain any new ingredient that’s not present in I, i.e. the newIngredientSet is also same as the ingredientSet I. So, from (I, s) state, we go to (I, i) state and we can possibly again go from state (I, i), we can again to (I, s) state. This introduces cycles in our dp state which we should avoid somehow.

Handling the cycles in the dp states

What if we skip consider a shop as the next shop if it is not adding anything new in the ingredientSet? Are we losing something by doing it? Assume our lastShop was s, we were trying to visit shop t, but shop t is not adding anything in ingredientSet, so instead we decided to visit some other shop w which is adding something in ingredientSet. You can see that distance visited in the second case is less than or equal to the first case, i.e. distance(s, w) <= distance(s, t) + distance(t, w). This is due to triangle inequality for euclidean distances. Therefore, we won’t be visiting a shop if it doesn’t add anything to our currently collected set of ingredients, thus resolving the cycles issue in our dp solution.

dp(ingredientSet, lastShop):
    if (ingredientSet has size k):
        return distance(lastShop, (0, 0))
    else:
        ans = infinity;
        for i = 1 to n:
            if (i != lastShop):
                let d = distance between lastShop and shop i.
                Let newIngredientSet be ingredientSet + ingredients of shop i added in it.
                // If shop i is adding something in newIngredientSet.
                if (newIngredientSet != ingredientSet)
                    ans = min(ans, d + dp(newIngredientSet, i));
        return ans;

Finally the answer of our problem will be the minimum of dp(ingredientsSet at shop i, i) for each i from 1 to n.

Estimating the final space and time complexity

Let us estimate the time taken in the transitions of the dp. We iterate over each shop i, such that i \neq lastShop and find the newIngredientSet and update the dp. If you iterate over all the ingredients of shop i to get the newIngredientSet, you will take \mathcal{O}(k) time. Instead if you maintain a bitmask of ingredients at each shop, and maintain the ingredientSet as a bitmask too, then you just have take a bitwise OR of the ingredientSet bitmask and the bitmask of ingredients at shop i to get the newIngredientSet. This will be an \mathcal{O}(1) operation. So, the transition per dp state will take \mathcal{O}(n) time.

Number of states in the dp is \mathcal{O}(2^k \cdot n). Therefore, the space complexity of this approach is \mathcal{O}(2^k \cdot n), whereas the time complexity will be \mathcal{O}(2^k \cdot n \cdot n) = \mathcal{O}(2^k \cdot n^2), which will be around 2^{12} \cdot 36^2 = 5308416 around 6 * 10^6. There are around 10 test cases, so around 6 * 10^7 operations overall. Note that the actual number of operations can differ from this by a constant factor depending on implementations.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester1
Tester2

10 Likes
2

Could we do this with dijktra ? that is there are 2^k states and and n vertices/

3

I have tried to implement this as the editorial. But I am getting TLE. Can anyone please help me out? shop_travel() is the function where I am calculating distance.

Here is my code. https://www.codechef.com/viewsolution/13383999

4

i was wondering if it can be done through dijkstra …

1 Like
5

Setter and Tester2’s solutions are not visible. Please check @admin !

6

I have tried same approach as in the editorial . Still I am getting TLE . Can someone please help me to optimize it or tell me where I should improve it . Thanks in advance

Here is my code link :https://www.codechef.com/viewsolution/13384516

7

This editorial must be triple starred if can be done. Very elegant introduction to ‘thinking in dp’.

8

very nice editorial . get a good idea regarding dp with bitmasking

1 Like
9

Hello! May someone please explain more on the proof of the time complexity? I’m little confused on 2^k factor. How are we getting it?
Thanks

10

access denied to setter’s and tester2’s solution. @admin @dpraveen plz fix it

11

Can someone please explain me the recurrence equation to come up with the time complexity O(2^k⋅n⋅n)= O(2^k⋅n^2) of the solution?

12

Can you please fix the access to the solutions (setter and tester)?

13

Can you please watch this code ?? Its not working for last testcase… infinite loop case i think

#include <bits/stdc++.h>
using namespace std;

vector< pair<int, int> > pos;
vector ing;
vector unio(vector a, string s){
for(int i = 1;i < a.size(); i++){
a[i] = a[i] | (s[i-1] - ‘0’);
}
return a;
}

double dist(pair<int, int> a, pair<int, int> b){
return(sqrt((a.first-b.first)(a.first-b.first) + (a.second-b.second)(a.second-b.second)));
}

double min(double a, double b){
if(a > b)
return b;
return a;
}

double dp(vector a, pair<int, int> last, int size){
cout << size << " " << a.size()-1 << endl;
if(size == a.size()-1){
return(dist(last, make_pair(0, 0)));
}

double ans = DBL_MAX;
for(int i = 0;i < pos.size();i++){
	if(pos[i] != last){
		vector<int> a1 = unio(a, ing[i]);
		int l1 = 0;
		for(int j = 1; j < a1.size(); j++){
			l1 += a1[j];
		}
		if(a1 != a){
			double d = dist(last, pos[i]);
			ans = min(ans, d + dp(a1, pos[i], l1));
		}
	}
}

return ans;

}

int main(){
int t;
cin >> t;
int x,y;
for(int i = 0;i < t;i++){
int n,k;
cin >> n >> k;
pos.resize(n);
ing.resize(n);
vector a(k);
for(int j = 0;j < n;j++){
cin >> x >> y;
pos[j].first = x;
pos[j].second = y;
}
for(int j = 0;j < n; j++){
string s;
cin >> s;
ing[j] = s;
for(int l = 0;l < k;l++)
a[l] = a[l] | (s[l]-‘0’);
}
int j;
for(j = 0;j < k; j++){
if(a[j] == 0){
cout << -1 << endl;
break;
}
}
vector b(k+1);
if(j == k)
cout << dp(b, make_pair(0, 0), 0) << endl;

}

}

14

Nice editorial (Y)

15

@sumanbhai @shuklacoder55 @ankdas1996 I was in same shoes as you guys. What we guys were doing was that we did not do memozize the ans . If we create array dp[1<<12][36] which dp[mask][node] holds ans TLE wil go.