Solution of Weekly Contest 173

, , , ,

[Easy] [Fail] 1332. Remove Palindromic Subsequences

Given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.

A string is called palindrome if is one that reads the same backward as well as forward.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: s = "ababa"
Output: 1
Explanation: String is already palindrome

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "". 
Remove palindromic subsequence "a" then "bb".

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "". 
Remove palindromic subsequence "baab" then "b".

Input: s = ""
Output: 0

Solution

Be careful the meaning of subsequence, which means we don’t need to move string continuously. And, the stirng only contains a and b, the maximum remove would be two (one for a subsequence, one for b subsequence).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// time:O(n) space:O(n)
public int removePalindromeSub(String s) {
        if (s == null || s.length() == 0) return 0;
        if (isValid(s)) return 1;
        return 2;
    }

    public boolean isValid(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }

[Medium] [pass]1333. Filter Restaurants by Vegan-Friendly, Price and Distance

Given the array restaurants where restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]. You have to filter the restaurants using three filters.

The veganFriendly filter will be either true (meaning you should only include restaurants with veganFriendlyi set to true) or false (meaning you can include any restaurant). In addition, you have the filters maxPrice and maxDistance which are the maximum value for price and distance of restaurants you should consider respectively.

Return the array of restaurant IDs after filtering, ordered by rating from highest to lowest. For restaurants with the same rating, order them by id from highest to lowest. For simplicity veganFriendlyi and veganFriendly take value 1 when it is true, and 0 when it is false.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10
Output: [3,1,5] 
Explanation: 
The restaurants are:
Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
Restaurant 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
Restaurant 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1] 
After filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest). 

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10
Output: [4,3,2,1,5]
Explanation: The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.

Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, maxDistance = 3
Output: [4,5]

Solution

Customized sorting question. We just need to know what they are saying and solve it.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Restaurant implements Comparable<Restaurant>{
        int id;
        int rating;
        int veganFriendly;
        int price;
        int distance;

        public Restaurant(int i, int r, int v, int p, int d) {
            id = i;
            rating = r;
            veganFriendly = v;
            price = p;
            distance = d;
        }

        @Override
        public int compareTo(Restaurant o) {
            if (this.rating != o.rating) return o.rating - this.rating;
            return o.id - this.id;
        }
    }
// time:O(NlogN) space:O(n)
public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        if (restaurants == null || restaurants.length == 0 ||
                restaurants[0] == null || restaurants[0].length == 0)
            return new ArrayList<>();
        List<Restaurant> lists = new ArrayList<>();
        for (int[] row : restaurants) {
            if (row[3] <= maxPrice && row[4] <= maxDistance && (veganFriendly == 0 || row[2] == veganFriendly))
                lists.add(new Restaurant(row[0], row[1], row[2], row[3], row[4]));
        }
        Collections.sort(lists);
        List<Integer> res = new ArrayList<>();
        for (Restaurant list : lists) {
            res.add(list.id);
        }
        return res;
    }

[Medium] [TLE] 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold.

Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities i and j is equal to the sum of the edges’ weights along that path.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output: 0
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> [City 1] 
City 1 -> [City 0, City 4] 
City 2 -> [City 3, City 4] 
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.

Solution

During the contest, I spent a lot of time to solve this problem and then failed. After seeing post in the disscussion and found out that I shouldn’t use DFS because they can have shorest path, which contains more neighbors, so I just pass 40 / 52 test cases. For the shorest path problem, we can use Dijkstra and Floyd Warshall algorithms.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
public int findTheCity2(int n, int[][] edges, int distanceThreshold) {
        HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i, new HashMap<>());
        }
        for (int[] edge : edges) {
            map.get(edge[0]).put(edge[1], edge[2]);
            map.get(edge[1]).put(edge[0], edge[2]);
        }

        int min = n + 1;
        int res = -1;
        for (int i = 0; i < n; i++) {
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (b[1] - a[1]));
            pq.offer(new int[]{i, distanceThreshold});
            HashSet<Integer> visited = new HashSet<>();
            int count = 0;
            while (!pq.isEmpty()) {
                int[] city = pq.poll();
                if (!visited.contains(city[0])) {
                    visited.add(city[0]);
                    count++;
                } else continue;
                HashMap<Integer, Integer> adjAndCost = map.get(city[0]);
                for (int adj : adjAndCost.keySet()) {
                    if (!visited.contains(adj) && city[1] >= adjAndCost.get(adj)) {
                        pq.offer(new int[]{adj, city[1] - adjAndCost.get(adj)});
                    }
                }
            }
            if (count - 1 <= min) {
                min = count - 1;
                res = i;
            }
        }
        return res;
    }


    // Floyd–Warshall's Algorithm
    // time:O(V^3)
    public int findTheCity3(int n, int[][] edges, int distanceThreshold) {
        long[][] d = new long[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(d[i], Integer.MAX_VALUE);
            d[i][i] = 0;
        }
        for (int[] edge : edges) {
            d[edge[0]][edge[1]] = Math.min(d[edge[0]][edge[1]], edge[2]);
            d[edge[1]][edge[0]] = Math.min(d[edge[1]][edge[0]], edge[2]);
        }
        // Floyd warshall
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (d[i][j] > d[i][k] + d[k][j]) { // use long to prevent the overflow.
                        d[i][j] = d[i][k] + d[k][j];
                    }
                }
            }
        }
        int min = Integer.MAX_VALUE, res = -1;
        for (int i = 0; i < n; i++) {
            int reachable = 0;
            for (int j = 0; j < n; j++) {
                if (d[i][j] <= distanceThreshold) {
                    reachable++;
                }
            }
            if (reachable <= min) {
                min = reachable;
                res = i;
            }
        }
        return res;
    }

Rank: 2296 / 6103. Solved 1/4 in 1h 30min.