Script to recover the old gmail favicon

Update: I've noticed this is getting many page views lately. Unfortunately, it no longer works. Google learned about leaving their old icon in the servers and changed it too. The only solution I can think of is hosting the old icon somewhere else and changing the url in the following script to use that hosted icon.

Yesterday gmail changed the favicon.

I don't like the new one. I wonder if the designer has ever witnessed the effects of lightning in a real life envelope. Shadows don't do that :).

This is serious business for me, because I am in front of a computer most of my life. And most of the time I am in front of a computer, it is looking at my browser window. And most of the time I am looking at my browser window, the gmail icon is the one in the first pinned app.

But I am a programmer, and I know how to workaround issues. I always have greasemonkey installed in firefox. It is an addon that allows me to specify some javascript scripts to run when visiting specific pages. All I had to do was to create a script that could change the favicon...

With some research, I found out that when google changed the icon, they didn't replace the old file. Instead they just created a new one. So all that the script needed was to change the address. A google search for "Change favicon with javascript" took me to a stackoverflow thread: http://stackoverflow.com/questions/260857/changing-website-favicon-dynamically/260876#260876

So here is the link to the userscripts.org entry: http://userscripts.org/scripts/show/169207. And here is the script itself:

// ==UserScript==
// @name        old favicon
// @namespace   nouglyenvelopeshadow
// @description Changes gmail's favicon back to the old one
// @include     http*://mail.google.com*
// @version     1
// @grant       none
// ==/UserScript==
(function() {
    var link = document.createElement('link');
    link.type = 'image/x-icon';
    link.rel = 'shortcut icon';
    link.href = '/mail/u/0/images/favicon.ico';
    document.getElementsByTagName('head')[0].appendChild(link);
}());

SRM 580 Editorial now published

It is "ready" (I am contractually obliqued to put "ready" between quotes). http://apps.topcoder.com/wiki/display/tc/SRM+580

I think I had some difficulty explaining the 600 points problem. It is really an abstract idea problem that seems sort of obvious once you get the correct idea. But it is not that easy to explain how to get that idea.

SRM 580 recap and WallGameDiv1 editorial preview

I intended to make a recap post of SRM 580 on Saturday. Then I got a blog writer's block.

This was a interesting match. I started with my risky strategy as usual, but this time, I opened the hard problem first. I liked it and it seemed like I could solve it. There was a time in which I doubted it and opened the medium problem... But I came back to the hard problem.

Eventually, I thought of a solution. I had plenty of doubts about it being correct. But I decided to give it a try. With a bit more than 10 minutes left for the match, I finished the code. But it was failing all example cases. I was supposed to open the easy problem when there were 10 minutes left, but I decided to gamble and use 2 more minutes trying to fix the bug. It turned out to be a simple bug - I forgot that the Rabbit has to pay the cost for the initial cell. Passed examples and rushed to open the easy problem.

The easy problem seemed approachable, but I had little time to do it. I quickly noticed that you only needed to worry about the end points. But for some reason I thought of a very wrong dynamic programming approach. I kept failing examples, and when there was little time left, I decided to submit a wrong solution for fun. felix-halim turned out to be the one to take advantage of this easy challenge.

I spent the intermission and challenge phase nervous and unconvinced I actually solved a hard problem. Then it turned out I passed system tests. That's about the time an actual formal proof for my approach appeared in my head. Great, I guess.

WallGameDiv1 editorial

Problem statement.

As usual, this is just the editorial preview. The official page will be updated better and have more fixes when it is finished.

From Eel's perspective

Let us see the game from Eel's perspective. Eel must decide both the time and location to place the walls.

Not giving away too much information

Consider an extreme case, Eel decides to place all the walls that it can just before the first turn. This sub-problem is basically the same as the division 2 version. After Eel places all the walls in this manner, there will still be a path that Rabbit can take. Since Rabbit already knows all the positions of the walls, Rabbit can take the direct, simplest path possible.

What happens is that when Eel places more walls than it needs to place in a step, it gives Rabbit more information than necessary. At any time, Eel should place only enough walls to force Rabbit into the worst path possible, but not more walls than that.

To place or not a wall directly bellow the Rabbit

Assume there is already a wall bellow the Token, Eel does not need to place any additional wall until the Rabbit moves the Token to a cell that has no walls bellow it. If Eel placed any wall before the Rabbit moves to one of those cells, Eel would be handling Rabbit information for free. Consider the following example, which is an extreme case:

If Eel places the remaining wall of the row too soon, Rabbit would know which side of the row is better to move to and will move directly to it. It is better for Eel to wait until the Rabbit takes the token to either extreme, making the Rabbit revisit many cells:

Eel should always wait until the token is placed on a cell that does not have a wall directly bellow it. Then Eel should decide between placing the wall in that location or not. In case all of the other cells in the row already have walls, Eel is unable to place a wall in that location (Because Eel cannot make the game completely impossible). The decision that Eel makes (place or not a wall bellow the current cell) will be the one that will require the largest cost.

From Rabbit's perspective

Rabbit wants to minimize the cost. Assume Rabbit placed the Token above a cell that does not have a wall directly bellow to it. There are two possibilities: a) Eel will place a wall bellow that cell or b) Eel will not place a wall bellow the cell.

In case the Eel didn't place the wall. The rabbit has the option to move to the row bellow it. This decision seems like a very good choice - The lower we move the closer we are to the bottom-most row. It is actually possible to show that this is always the optimal move.

Proof: The current cell position is (x, y). After the Rabbit placed the token on this cell, Eel didn't put a wall bellow it, allowing Rabbit to move to cell (x, y+1). By contradiction: Assume there is a cell (x2, y+1) better than (x, y+1) as a starting point in row y+1. If there is no wall above (x2, y+1), then the Rabbit might try to move to (x2, y). Eel will now have a choice to place a wall bellow (x2, y+1), because we know that the wall space between (x,y) and (x,y+1) is empty, thus it will be a valid move to place a wall between (x2, y) and (x2, y+1). If Eel places this wall, then Rabbit will be forced to move back to (x,y), this time forced to move to (x,y+1), the path cost starting at (x,y+1) is still the same, but Rabbit spent cost units by unnecessarily attempting to move to (x2,y).

Whenever the path to the cell bellow the token is empty, Rabbit must always move down.

The other case is when the Token is already above a wall. Eel will wait until the Rabbit moves above an empty wall space. It makes sense to make the Rabbit take the straight path, either to the left space or the right space. Rabbit must pick the choice that minimizes the overall result (including the cost to move to the empty space).

Dynamic programming

Once the token is in row y, we can ignore any walls in previous rows. The only walls that matter are those that were placed between row y and y+1.

When the token enters the row for the first time, the walls between y and y+1.

form an empty set. If Eel decides to place a wall bellow (x, y) the set of walls will contain only x. Rabbit can choose to move to x+1 or x-1, where Eel will once again have the choice to add a new wall. The new set of walls will be {x-1,x} or {x,x+1}. Let us assume Rabbit move to x-1, Rabbit once again has the choice to move to another cell that is not above a wall. The choices are x-2 or x+1. Note how the set of walls is always an interval of positions.. This is great because there are only O(w*w) possible intervals which we can represent by two variables, x0,x1 such that the interval is [x0,x1). There are only four choices for x, because x will either be outside the interval and be equal to x0-1 or x1 or it can also be at either of the extremes of the interval (equal to x0 or x1-1). The values for y are O(h). All in all, the state of the game can be described by tuple (y, x, x0,x1) and there are O(h*w*w) such tuples.

Define two functions: playEel(y, x, x0,x1) and playRabbit(y, x, x0,x1), that represent the decisions taken by each animal. playEel() returns the maximum possible cost Eel can accomplish after Rabbit moved the Token to a cell that does not have a wall directly bellow it. playRabbit() finds the minimum possible cost assuming that Eel has already decided whether or not to place a wall bellow (x,y).

• playEel(h-1, x, empty interval) is a base case, the Rabbit has managed to move the token to the last row. The Eel knows that the remaining cost is 0.
• playEel(y, x, x0,x1), as a precondition we know that (x,y) is not above a wall. The interval of walls [x0,x1) is either to the left or right of (x). Eel must decide between placing a wall or not. If Eel does not place a wall, it is Rabbit's turn without a wall bellow the token: ( playRabbit(y, x, x0,x1) ). If Eel places a wall, the interval [x0,x1) must be extended to include x, the result is equal to playRabbit(y,x, extended interval). If all the cells of the row (other than x) already contain walls, it is not possible for Eel to place a wall.
• playRabbit(y, x, interval that does not contain x), is the case where Eel decided not to place a wall bellow (y,x), Rabbit must move to the bellow row. After this move, Eel has a chance to decide for the new position. The result is: cost(y+1, x) + playEel(y+1,x, empty interval).
• playRabbit(y, x, interval that contains x), gives the rabbit two choices: Move to the empty cell to the right or left of the interval. This move involves visiting (and paying costs) for a wide number of cells. For example, if Rabbit moves the token to x0-1 , the total cost is: (Cost to move from (x,y) to (x0-1,y) ) + playEel(y,x, x0-1,x1).

These mutually recursive recurrence relations are still acyclic and we should be able to implement them with dynamic programming or memoization.

Code

int w, h;
vector <string> costs;
int dpRabbit[50][50][51][51];
int dpEel   [50][50][51][51];

// Sum of costs between (y,x0) and (y,x1-1):
int sum(int y, int x0, int x1)
{
    int s = 0;
    for (int i=x0; i<x1; i++) {
        s += costs[y][i] - '0';
    }
    return s;
}

int playRabbit(int y, int x,  int x0, int x1)
{
    // Token is currently at point (x,y). There are walls between each
    // (y, i) and (y+1,i) for each x0 <= i < x1 :
    // What should Rabbit do?

    int res = dpRabbit[y][x][x0][x1]; //O(n^3) states because x = x0-1, x0, x1-1 or x1
    if (res == -1) {
        if ( !(x0 <= x && x < x1) ) {
            // no wall bellow the Token. Best to move bellow:
            // It is convenient to use [x,x) as the empty interval. This way the
            // Eel function can easily extend it to include x:
            res = (costs[y+1][x] - '0') + playEel(y+1,x, x,x);
        } else {

            res = INF;
            // Rabbit decides to move to x0 - 1
            if (x0 > 0) {
                // sum(y,x0-1,x) = Cost to move from (x,y) to (x0-1,y).
                // playEel(y,x0-1, x0,x1) = Cost after Eel decides to place
                //                            a wall or not.
                //
                res = sum(y, x0-1, x) + playEel(y,x0-1, x0,x1);
            }
            
            // Rabbit decides to move to x1:
            if (x1 < w) {
                // sum(y, x+1, x1+1) = Cost to move from (x,y) to (x1,y).
                // playEel(y,x1, x0,x1 ) = Cost after Eel decides to place
                //                         a wall or not.
                //
                int tem = sum(y, x+1, x1+1) + playEel(y,x1, x0,x1 );

                // Rabbit wants the smaller cost:
                res = std::min(res, tem);
            }
        }
        dpRabbit[y][x][x0][x1] = res; // memoize the case.
    }
    return res;
}

int playEel(int y, int x,  int x0, int x1)
{
    // Token is currently at point (x,y). There are walls between each
    // (y, i) and (y+1,i) for each x0 <= i < x1 :
    // What should Eel do?
    
    int res = dpEel[y][x][x0][x1]; //Also O(n^3) because x = x0-1 or x1
    if (res == -1) {
        if (y == h - 1) {
            //The token is in the last row. Eel cannot do much about it.
            res = 0;
        } else {
            //What if Eel decides not to place a wall?
            res = playRabbit(y,x, x0,x1); //let the Rabbit do its move
            
            //What if Eel decides to place a wall?
            if( x1 - x0 < w - 1) { //Cannot fill the whole row with walls
                int tem = playRabbit(y,x, std::min(x0,x), std::max(x1,x+1) );
                // extend the interval that contains the wall
                
                // Eel wants the maximum cost:
                res = std::max(res, tem); 
            }
        }
        dpEel[y][x][x0][x1] = res; // memoize the case.
    }
    return res;
}



int play(vector <string> costs)
{
    // Save some variables for use by the functions:
    this->costs = costs;
    h = costs.size(), w = costs[0].size();
    // Initialize dpRabbit and dpEel with -1s.
    memset(dpRabbit, -1, sizeof(dpRabbit));
    memset(dpEel   , -1, sizeof(dpEel));

    // Rabbit picks a starting cell in the top row:
    int best = INF;
    for (int i=0; i<w; i++) {
        // Rabbit wants the choice that costs the least:
        best = std::min(best, (costs[0][i]-'0') + playEel(0,i, i,i) );
    }
    return best;

}

SRM 580, WallGameDiv2, editorial preview

Here is a preview of 579's editorial. Begin with division 2 hard. The editorial page contains this explanation and once the rest of the editorial is finished it might contain an updated/fixed version. This page is just the preview.

I intended to write this one even since Saturday . But I had difficulty coming up with an explanation that doesn't just jump to "calculate the worst path, duh!".

WallGameDiv2

Link to the problem statement. There is a board with digits (as costs) in some cells and letter x in the remaining cells. In the first turn, Eel can build some walls (possibly none) between any two vertically-adjacent cells. In the second turn, Rabbit places a token in the top-left (0,0) cell, then Rabbit gets to move the cell down, left or right to any existent cell that does not contain a X, the cost to do the move is equal to the digit written in the cell. The game finishes when Rabbit takes the token to the bottom row. Eel cannot place the walls in such a way that it is not possible for Rabbit to find an exit. Rabbit wants to spend as little as possible and Eel wants Rabbit to spend as much as possible. Return the total cost Rabbit pays if both Rabbit and Eel play optimally.

Eel's control of the game

Let us play from Eel's perspective. Rabbit starts at top left cell and may be able to move to many cells in the top row until a blocked cell or the border of the board:

In an example with three reachable cells in the top row, the Rabbit can move to any of them and them move to the cell bellow it. Ad Eel we can place walls to vertically sperate cells from each other. With the help of walls we can actually force the Rabbit to move to a specific one of them:

With the help of walls we can assume that the Rabbit will have to move the token to the position in the second row that we wanted. There are once again three locations in the lower row that are reachable. One of the other location is blocked with an 'x'. The remaining locations (in red) are not valid, because if we made the Rabbit move there, the Rabbit would be unable to reach the bottom row (The paths from each of the squares in that area to the bottom row are blocked). Although we have many valid locations where we can force the Rabbit to move, we should place walls in a way that maximize the cost. We must leave at least one of them open for the Rabbit, though:

Then we face other three choices where to put the wall gap. The image to the right shows the whole path the Rabbit took to reach the bottom row.

The path the Rabbit takes at the end is a simple path, the Rabbit never visits the same square twice. There is no reason to, because the Rabbit already knows the positions of all the walls and can take a direct route. The simple path will finish at any of the cells in the bottom row.

Although the previous logic to consider sub-problems with the starting cell in each row in mind allows a dynamic programming solution. If you instead notice that Eel can force Rabbit to take any simple path to the bottom row that Eel prefers we can have a simpler one. For example, consider the following simple path:

It is possible to decide walls that force Rabbit to take any valid simple path we want. Eel wants Rabbit to spend the maximum cost possible. The path Eel forces Rabbit to take should be the one that has the largest possible sum of cell values, the worst simple path (It must be valid though, it must finish at one of the cells in the bottom row.).

Worst valid path from (0,0) to the bottom

A path is a sequence of cells. A simple path is a sequence of cells that does not visit the same cell twice. We can try a backtracking logic: The fist cell in the path is (0,0). When the current cell is (x,y), there are up to three choices for the next cell in the path:

• (x,y+1) : Move down
• (x - 1,y) : Move left.
• (x + 1,y) : Move right.

In many cases some of these moves are invalid. The new cell could have a 'x' and be blocked. It is also possible that no valid path is possible if you move to that cell. Or maybe the cell does not exist (you are at one of the borders and can only move in one horizontal direction). Or maybe the cell was already visited by the path, which would not be good because the path must be simple. Because we can't move up, the only way to visit a cell that was already visited is to move backwards - Move left after a move to the right or vice versa. Thanks to this we only need to remember three variables: (x,y) the current cell and d, the previous direction. For example d is 1 if the previous move was to the left, 2 if the previous move was right and 0 otherwise. The result is a recurrence relation f(x,y,d) that returns the worst path starting at (x, y) such that the new direction is consistent with d:

• f(x,h - 1,d) = (cost(x, h-1)) (If h is the height of the board, then all cells at row (h - 1) are in the bottom. The path has finished.
• f(x, y, d) = -INF (A very small negative number) in case there are no valid paths starting at (x,y) such that the next direction is consistent with d. If (x, y) is "x" assume also that the result is -INF. We use -INF to mark this state as invalid, because the latter steps maximize the result, so any valid result will be greater than the invalid result.
• f(x, y, 0) = cost(x, y) + (The worst path out of f(x, y+1, 0), f(x-1, y, 1), f(x+1, y, 2) ). (E.g: If we decide to move right, the new value of d is 2, and the next starting cell is (x+1, y).
• f(x, y, 1) = cost(x, y) + (The worst path out of f(x, y+1, 0) or f(x-1, y, 1) ). (The previous move was to the left, it is not valid to move right).
• f(x, y, 2) = cost(x, y) + (The worst path out of f(x, y+1, 0) or f(x+1, y, 2) ). (The previous move was to the right, it is not valid to move left).

This recurrence relation is a cyclic and has a limit number of state combinations O(w*h) (There are at most three values of d for each cell). We can use memoization to implement it in polynomial time.

vector<string> costs;
int w, h;
int dp[50][50][3];
int worstPath(int y, int x, int d)
{
    const int INF = 1000000000;
    int res = dp[y][x][d];
    if (res == -1) {
        int c = costs[y][x]-'0';
        if ( costs[y][x] == 'x') {
            // Invalid
            res = -INF;
        } else if (y == h-1) {
            // Base case, the bottom is the end of the road:
            res = c;
        } else {
            // Move down:
            res = c + worstPath(y+1, x, 0);

            // Move left (as long as the previous move was not right)
            if ( (d != 2) && (x > 0) ) {
                res = std::max(res, c + worstPath(y, x-1, 1) );
            }
            // Move right (as long as the previous move was not left)
            if ( (d != 1) && (x < w-1) ) {
                res = std::max(res, c + worstPath(y, x+1, 2) );
            }
        }
        // memoize the result:
        dp[y][x][d] = res;
    }
    return res;
}
int play(vector <string> costs)
{
    //Save some variables for use by the worstPath function:
    this->costs = costs;
    w = costs[0].size();
    h = costs.size();
    // initialize the whole dp[][][] array with -1:
    memset(dp, -1, sizeof(dp));
    // Solution: x=0, y=0, d=0
    return worstPath(0,0, 0);
}

SRM 579 Editorial preview: TravellingPurchasingMan and MarblePositioning

The hardest and most annoying problems for me to explain are those I actually wrote. Specially these ones that are actually easy problems. The more obvious a problem seems to me the harder it is to explain something.

Marble positioning

Problem statement. Given a list of at most 8 circle radiuses, find the minimum horizontal distance between the leftmost and rightmost circles if you can place them in any order as long as no two circles overlap.

All permutations

The solution can be split in two parts: First we can decide the order in which we place the circles. The second part is to decide the minimum distance between the leftmost and rightmost circle, without overlap.

For the first part, the images in the examples should tell us that there seems not to be a simple logic that can tell easily us what the best order is. But the number of circles will be small. There are at most 8! = 40320 different permutations of circles to try. We can generate all these permutations and find, for each of them, the minimum distance between the left-most and right-most circle. In order to generate all the permutations we can use backtracking. Although it is also possible to generate all permutations iteratively and C++ even has a next_permutation function.

Minimum width

For a fixed order of circles, find the minimum distance. Place the left-most circle in position 0. Start considering the version with only two circles: We need to place circle 1 in such a position greater than 0 and in such a way that circle 1 and 0 do not overlap. In addition making the distance between their points as small as possible.

We put the circles so close to each other that the exact distance between their centers is now (r0+r1). We can actually tell that circle 0's center is (p0, r0) part of circle 1's center is unknown (p1, r1). We can try an equation to find (p1-p0) using Euclidean distance as a starting point:

 r0 + r1    = sqrt( (p1 - p0)^2 + (r1 - r0)^2 )
(r0 + r1)^2 =       (p1 - p0)^2 + (r1 - r0)^2
(p1 - p0)^2 =      (r0 + r1)^2       -    (r1 - r0)^2
(p1 - p0)^2 =  r0^2 + 2*r0*r1 + r1^2 - r0^2 + 2*r0*r1 - r1^2
(p1 - p0)^2 =             4 * r0 * r1
 p1 - p0)   =           2 * sqrt( r0 * r1 )

The minimum distance between the two circles is 2 * sqrt(r0 * r1).

When there are 3 circles. We can assume that we first found the minimum distance between the first two circles. There are two cases:

In this case, the new circle touches circle 1.

In this one, the new circle touches circle 0. It may also be possible that the new circle touches both circle 0 and 1. In any case, there should be at least one circle that touches the new circle. We can generalize: For each of the circles with a smaller index, we can find the minimum distance to place the new circle without overlaps. The maximum of these distances will be the result.

Code

int n = 0;
double[] radius;

// Given the radiuses in a fixed order, find the minimum
// p[n-1] - p[0]:
double minWidth()
{
    double[] p = new double[n];
    // Place the first marble on point 0.0:
    p[0] = 0.0;
    for (int i=1; i<n; i++) {
        // Decide where to place marble i:
        p[i] = 0;
        for (int j=0; j<i; j++) {
            double dis = p[j] + 2 * Math.sqrt(radius[i] * radius[j]);
            // Dis is the minimum distance where we can place i
            // without overlaping with j.
            p[i] = Math.max(p[i], dis );
            // The maximum of all the distances is the best place
            // for p[i]
        }
    }
    return p[n-1] - p[0];
}

// Use backtracking to generate each of the permutations of
// the original radius array:
void rec(int p)
{
    if (p == n) {
        // Remember the permutation with the best result:
        best = Math.min(best, minWidth());
    } else {
        // Decide the radius for position p.
        // We have already decided the smaller positions,
        // so we need to pick a radius from indices >= p:
        double radp = radius[p];
        for (int i=p; i<n; i++) {
            // Swap radius[p] and radius[i]
            radius[p] = radius[i];
            radius[i] = radp;
            
            // Step in the recursion:
            rec(p + 1);
            
            // Restore radius[i]
            radius[i] = radius[p];
        }
        radius[p] = radp
    }
}

public double totalWidth(int[] radius)
{
    n = radius.length;
    this.radius = new double[i];
    for (int i = 0; i < n; i++) {
        this.radius = (double)radius[i];
    }
    // Start backtracking:
    rec(0);
    return best;
}

TravellingPurchasingMan

Problem statement it is too long to explain in a single paragraph.

Travelling salesman

Let us go with a similar problem (so similar, even the name of the problem is quite close). In this version of the problem, the stores are always open. In this version, it is always possible to buy all the products (assuming all stores are reachable) so let us try the minimum time before buying all products. This is quite close to the Travelling salesman problem.

The main differences is that we need to only visit some stores in which buying a product also takes time. We can simplify the problem by reducing it to a problem that has only store N-1 and the interesting stores. The travel distance between two interesting stores can be calculated as the minimum travel distance (direct or indirect) between the stores from the original problem. To calculate these distances we can use any shortest paths algorithm. We will use Floyd-Warshall because the constraints are low and it can be implemented in few lines. After this change, there is no reason to move from a store to another if you do not plan to buy a product from that store.

Describe the state as (x, mask): x is the current store position and mask is a bitmask representing the set of stores from which you already made a purchase. You are at score x, if you decide to move to store y, it would be because you plan to buy the product at y. Moving between x and y takes as many time as the travel time between the stores. Once you reach store y, you make the purchase taking DURATION time. In total, there is a cost to move from (x, mask) to (y, mask | (1<<y).

The result is the minimum time needed to move from (N-1, 0) to (z, 1111..1), for any z. This makes the problem exactly like travelling salesman.

Closed stores

Let us now include the closing time into the problem. Assume all stores are open at time 0, but each store has a closing time. It may no longer be possible to buy from all reachable stores, because time spent in reaching a store and buying a product may make you unable to buy in other stores.

This makes the time at which you arrive to node (x, mask) important. If the current time is t, and moving to store y makes the time increase to a value higher than the store's closing time, we will not be able to buy the product anymore. If it is so late that it is impossible to buy y's product, it is better not to even go there, we can make it so there is no edge between (x, mask) and (y, mask | (1<<y) ) depending on the current time.

Let t be the minimum time needed to reach state (x, mask), if at this time it is impossible to move from (x, mask) to (y, mask | (1<<y) ), it will never be possible. Thanks to this we only need to know the minimum time to reach state (x, mask) and it determines the edges to other states. As long as we find the minimum time of the closest states, the rest is still about finding the minimum paths. The other difference is with maximizing the number of purchases. We need to find a state (y, mask2) such that there is a path between (x, mask) and a (y, mask2) and mask2 has as many elements as possible.

Open time

Once we add the open time we have a different issue. The time at which you arrive to a store may be too early and we cannot make the purchase before it opens. However, we can just wait some time until the opening time and then make the purchase, thus we can just consider this as an addition to the purchase duration. We arrive to (x, mask) at time t and the distance between x and y was w seconds. If t + w is less than or equal to the closing time, then it is possible to make the purchase. However, if t + w is less than the opening time, we need to wait up until that time. The minimum time to arrive (y, mask|(1<<y)) will be max(t + w, OPEN_TIME ) + DURATION.

A fast enough solution

Although we have successfully reduced the problem to shortest paths, we need to be careful about the time. There are at most 16 interesting stores, this means there are 2¹⁶ different values for mask and at most 17 values for x (N-1 could be a store that is not interesting). This yields an upper bound for the number of vertices equal to 17*2¹⁶. The number of edges is smaller, for each vertex, there are at most 16 choices for other stores to visit. 16*17*2¹⁶ edges may be too large for some Dijkstra implementations, the good news is that we can use a dynamic programming logic instead.

We will move iteratively in increasing order of the mask. We know that the first state is (N-2, 0). From it we can find the minimum costs of all states that have exactly one purchased product. Then for each (i, mask), we can find new costs for some states (j, mask | (1<<j) ) that will have a larger bit mask.

final int INF = 1000000000;
int [] distance;
public int maxStores(int n, String[] interestingStores, String[] roads) {
    // Initial distance between any two stores (relevant or not):
    int[][] dist = new int[n][n];
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            dist[i][j] = INF;
        }
        dist[i][i] = 0;
    }
    // Use the roads to fill that distance array:
    for (int i = 0; i < roads.length; i++) {
        String[] s = roads[i].split(" ");
        int u = Integer.parseInt(s[0]);
        int v = Integer.parseInt(s[1]);
        int d = Integer.parseInt(s[2]);
        dist[u][v] = dist[v][u] = Math.min(dist[v][u], d);
    }
    //Floyd-Warshall:
    for (int k=0; k < n; k++) {
        for (int i=0; i < n; i++) {
            for (int j=0; j < n; j++) {
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    // Let us make the new problem that only contains the interesting stores
    // and store N-1 (May or may not be interesting):
    int m = interestingStores.length;
    int[] open     = new int[m + 1];
    int[] close    = new int[m + 1];
    int[] duration = new int[m + 1];
    int[] storeId  = new int[m + 1];
    int[] store = new int[n];
    Arrays.fill(store,0,n,-1);
    for (int i=0; i<m; i++) {
        String[] x = interestingStores[i].split(" ");
        int s =  i;
        store[ s ] = i;
        open[i] = Integer.parseInt(x[0]);
        close[i] = Integer.parseInt(x[1]);
        duration[i] = Integer.parseInt(x[2]);
        storeId[i] = s;
    }
    int maskLimit = (1<<m);
    // Add store n-1 in case it was not interesting. Let us make it a interesting
    // store that is permanently closed.
    if (store[n-1] == -1) {
        storeId[m] =n-1;
        store[n-1] = m;
        open[m] = -2;
        close[m] = -1;
        duration[m] = 0;
        m++;
    }
    //distance[mask * m + x] holds the minimum time needed to reach state (x,mask)
    distance = new int[maskLimit*m];
    Arrays.fill(distance,0, m*maskLimit, INF);
    // At time 0, we start at store (n-1) and no purchases were made.
    distance[0*m + store[n-1] ] = 0;

    // update the distance array in increasing order of masks:        
    for (int mask = 0; mask < maskLimit; mask++) {
        for (int x=0; x < m; x++) {
            if (distance[mask*m + s] < INF) {
                int t = distance[mask*m + x];
                // We decide to move to store nx:
                for (int nx = 0; nx < m; nx ++) {
                    // If we move to store nx, it is because we want to make
                    // the purchase. 
                    // Time necessary to move:
                    int nt = t + dist[ storeId[x] ][ storeId[nx] ];
                    if (nt <= close[nx])  { //If the store would not be closed:
                        // After arriving, we may need to wait until the store
                        // opens. Then we need duration[nx] time to make the purchase:
                        nt = Math.max(nt, open[nx] ) + duration[nx];
                        int nmask = mask | (1<<nx);
                        int nnode = nmask * m + nx;
                        // Update the distance:
                        if (distance[nnode] > nt ) {
                            distance[nnode] = nt;
                        }
                    }
                }
            }
        }
    }
    // Find the mask that has the best number of purchases and is reachable:
    int res = 0;
    for (int j=0; j<maskLimit; j++) {
        // Count the number of bits:
        int c = 0;
        for (int i=0; i<m; i++) {
            if( (j&(1<<i)) != 0 ) {
                c ++;
            }
        }
        for (int i=0; i<m; i++) {
            if ( distance[j*m + i] != INF ) {
                res = Math.max(res, c);
            }
        }
    }
    return res;

    
}