LeetCode174-Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2(K) -3 3
-5 -10 1
10 30 -5(P)

Notes:

  • The knight’s health has no upper bound.
  • Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

分析

骑士只能向下或向右移动,每个方格如果是正数表示加血,如果是负数表示扣血。血量等于或低于0时骑士死亡。求骑士从左上角出发并顺利到达右下角条件下的最小初始血量。

初步分析本题采用动态规划。分别从正向反向考虑。

正向

按正向考虑,dp[i][j]表示从起点出发到(i, j)点所需的最小初始血量。但发现计算dp[i][j]时不能单纯地取dp[i-1][j]dp[i][j-1]的较小值。原因在于,当前到达(i, j)位置时的剩余血量会对后面的结果产生影响。

简单地说,比如A=dp[i-1][j]B=dp[i][j-1]remainAremainB分别对应A和B的剩余血量。当A>B同时remainA>remainB时,如果我们选择B,在后续路径中如果有较大的负值出现,那么B较小的优势并不能传递,此时剩余血量反而更重要。

但引入剩余血量对路径的选择又会使算法变的复杂。所以从反向考虑。

反向

按反向考虑,dp[i][j]表示从(i, j)点出发到达右下角点所需的踏入(i, j)点前的最小剩余血量。那么,状态转移方程如下:

1
dp[i][j]=max{ min{ dp[i+1][j], dp[i][j+1] } - dungeon[i][j], 0 }

在边界上的情况需要做简单的处理。

由于反向时考虑了从当前点到终点的路径,因此dp[0][0]就是踏入(0,0)点前的最小剩余血量,即最小初始血量。这里可以发现,正向考虑时纠结的剩余血量,在这里就是求的dp[i][j]。反向求解过程非常自然,最重要的就是正确选择了dp的目标

AC代码

1
class Solution {
2
public:
3
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
4
        int row = dungeon.size();
5
        int col = dungeon[0].size();
6
        for (int i = row - 1; i >= 0; --i) {
7
            for (int j = col - 1; j >= 0; --j) {
8
                solveCurrentMinValue(dungeon, row, col, i, j);
9
            }
10
        }
11
        return dungeon[0][0] + 1;
12
    }
13
14
    void solveCurrentMinValue(vector<vector<int>>& dungeon, int row, int col, int i, int j) {
15
        pair<int, int> rightPoint(make_pair(i, j + 1)), lowerPoint(make_pair(i + 1, j));
16
        int lower, right, min, MAX_INT;
17
        bool hasLower, hasRight;
18
        lower = right = 0;
19
        hasLower = hasRight = true;
20
        MAX_INT = 999999999;
21
22
        if (rightPoint.first < row && rightPoint.second < col) {
23
            right = dungeon[rightPoint.first][rightPoint.second];
24
        } else {
25
            hasRight = false;
26
        }
27
        if (lowerPoint.first < row && lowerPoint.second < col) {
28
            lower = dungeon[lowerPoint.first][lowerPoint.second];
29
        } else {
30
            hasLower = false;
31
        }
32
33
        if (!hasLower && !hasRight) {
34
            min = 0;
35
        } else {
36
            min = minValue(hasLower ? lower : MAX_INT, hasRight ? right : MAX_INT);
37
        }
38
39
        int current = min - dungeon[i][j];
40
        dungeon[i][j] = current >= 0 ? current : 0;
41
    }
42
43
    int minValue(int x, int y) {
44
        return x < y ? x : y;
45
    }
46
};

LeetCode187-Repeated DNA Sequences

思路

  • 由于碱基无非ACGT四种类型,可以使用00 01 10 11四个状态代替ACGT四种碱基,比如AAGCT就是00 00 10 01 11,对任意一个长度为10的子串都可以转化使用20个位的int值hint。这样就可将unordered_set<string> repeated转变为unordered_set<int> repeated, 一定程度上减少了所需的存储空间。
  • 对于如何去重, 其一可以先收集所有答案,再sort,unique去重,当然这样很慢也很麻烦。其二,可以再构造一个unordered_set check,用于存储已经存入answer中的重复子串对应的hint值;
  • 值得一提的是,每次从s[i]->s[i+9]变为s[i+1]->s[i+10],使用了这样一个方法:
    1
    hint = ((hint & eraser) << 2) + ati[s[i]];
    其中eraser是一个宏定义, 值为0x3ffff, 二进制是00111111111111111111, 用于擦除hint中的最高2位s[i]碱基对应的值, 再左移2, 最后加上s[i+10]的碱基对应的值。
1
class Solution {
2
public:
3
    #define eraser 0x3ffff
4
    vector<string> findRepeatedDnaSequences(string s) {
5
        vector<string> answer;
6
        int hint = 0;//存储长度为10的子串翻译后的int值
7
        if (s.size() < 10)
8
            return answer;
9
        unordered_set<unsigned int> repeated, check;//repeated存储已出现的子串, check用于防止重复答案
10
        unordered_map<char, unsigned int> ati{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};//此处ati是存储各碱基对应的值00 01 10 11(c++11新语法)
11
        for (int i = 0; i != 10; ++i) {
12
            hint = (hint << 2) + ati[s[i]];//用s的前10个碱基构造初始hint值
13
        }
14
        repeated.insert(hint);
15
        for (int i = 10; i != s.size(); ++i) {
16
            hint = ((hint & eraser) << 2) + ati[s[i]]; //子串变化对应hint值变化
17
            unordered_set<unsigned int>::iterator it = repeated.find(hint);
18
            if (it != repeated.end()) {
19
                it = check.find(hint);
20
                if (it == check.end()) {
21
                    answer.push_back(string(s, i - 9, 10));
22
                    check.insert(hint);
23
                }
24
            }
25
            else
26
                repeated.insert(hint);
27
        }
28
        return answer;
29
    }
30
};

一开始由于忽略了移位与其他运算符的优先级关系, 一直出问题,郁闷:(

LeetCode 200-Number of Islands

分析

只需要对每一个陆地区域做一次dfs,每次dfs中将已经遍历的陆地网格“1”变为水域网格“0”(防止再次遍历导致重复)。对每次dfs计数,总共dfs的次数即为岛屿总数。应注意,grid为空的特殊情况应该排除。

1
class Solution {
2
public:
3
    int numIslands(vector<vector<char>> &grid) {
4
        int row = grid.size();
5
        if (!row) return 0;
6
        int col = grid[0].size();
7
        int count = 0;
8
9
        for (unsigned i = 0; i != row; ++i) {
10
            for (unsigned j = 0; j != col; ++j) {
11
                if (grid[i][j] == '1') {
12
                    dfs(grid, i, j); ++count;
13
                }
14
            }
15
        }
16
17
        return count;
18
    }
19
    void dfs(vector<vector<char>> &grid, unsigned i, unsigned j) {
20
        int dx[4] = {1, 0, -1, 0};
21
        int dy[4] = {0, 1, 0, -1};
22
        int row = grid.size(), col = grid[0].size();
23
        grid[i][j] = '0';
24
25
        for (int k = 0; k != 4; ++k) {
26
            int new_i = i + dx[k], new_j = j + dy[k];
27
            if (new_i >=0 && new_i < row && new_j >= 0 && new_j < col && grid[new_i][new_j] == '1')
28
                dfs(grid, new_i, new_j);
29
        }
30
    }
31
};

LeetCode 201-Bitwise AND of Numbers Range

分析

如果真的在范围[m, n]内按顺序逐个数字做&操作显然效率不高。那么我们可以先列出一些数字去寻找规律:

12 1100 110 11
13 1101 110 11
14 1110 111 11
15 1111 111 11

上表区间中在移位过程中,逐渐抹去最后一位,最终会在某一次移位后区间内所有数的值相同(1101->110->11),移位次数为2,该范围内所有数按位与操作以后结果为1100,即12。由此我们可以知道,低位部分在范围内按位与操作中会因为0的存在而消去为0,只有高位部分会得以保留。因此我们可以用一个count计数器记录移位次数(即低位0的个数),而最终移位结果均一致时(如例子中最终为二进制11),即为其高位部分。此时只需将高位部分复原即可,也就是11->110->1100,做2次向左移位复原。
当然在计算过程中我们并不需要对区间内所有数做这种操作,只需对区间最小值m和最大值n进行操作(因为区间首尾是区分度最大的两个数,对区间内所有数做右移时,最有可能不相同的肯定是m和n)。

注意

当较小的数移位后为0时,就应该停止循环。最终结果肯定也是0。

1
class Solution {
2
public:
3
    int rangeBitwiseAnd(int m, int n) {
4
        int count = 0;//初始化计数器
5
        while (m && m != n) {//m为0时或m == n时退出循环
6
            ++count;//统计低位0的个数
7
            m >>= 1; n >>= 1;//抹去低位
8
        }
9
        return m << count;//低位复原, 因为0 << count仍为0, 因此此处不做区分
10
    }
11
};

LeetCode202-Happy Number

分析

题目中已经给了提示,当能出现1时,即退出循环返回true;如出现了一个不为1的循环则返回false(如4, 16, 37, 58, 89, 145, 42, 20, 4, …)。对happy number的详细描述见wiki百科:Happy Number。wiki还对Happy primes和Harshad number做了一些解释。为了快速确定是否发生非1的重复,使用unordered_set来记录已经出现过的数(我们并不关心数字的顺序,因此用hash效率更高)。

1
class Solution {
2
public:
3
    bool isHappy(int n) {
4
        int sum;
5
        unordered_set<int> check;
6
        check.insert(n);
7
        while (n != 1) {
8
            sum = 0;
9
            while (n) {
10
                int t = n % 10;
11
                n /= 10;
12
                sum += t * t;
13
            }
14
            if (check.find(sum) != check.end())
15
                return false;
16
            check.insert(sum);
17
            n = sum;
18
        }
19
        return true;
20
    }
21
};

LeetCode204-Count Primes

分析

这个题相当于求小于n的所有质数,曾在编程之美中看到过一个求一组质数的算法,叫厄拉多塞筛法,时间复杂度仅有O(nloglogn),这是一个相当好的算法(如果从1到n-1分别判断质数,时间复杂度为O(nsqrt(n)))。
厄拉多塞筛法的步骤:建立从2到n的集合G={2, 3, 4, …, n},每次从集合中取出最小的数A,这个数就是质数;然后将数A * times从集合中删除,其中1<=times<=n/A。得到一个新的集合G’,重复上述步骤直到集合为空,就取出了所有质数。
举例一个集合{2, 3, 4, …, 12}:
stp1:最小值为2,取出2并删除2,4,6,8,10,12,集合变为{3, 5, 7, 9, 11};
stp2:最小值为3,取出3并删除3,6,9,集合变为{5, 7, 11}

最后得到质数为2,3,5,7,11。

注意

  1. 一开始我用unordered_set来标记一个数是否被删除,后来内存使用超出要求。后来改用bool数组来记录就AC了。
  2. 注意是小于n,而非小于等于n。
1
class Solution {
2
public:
3
    int countPrimes(int n) {
4
        bool isDeleted[n];
5
        for (unsigned i = 0; i < n; ++i)
6
            isDeleted[i] = false;
7
8
        int count = 0;
9
        for (unsigned i = 2; i < n; ++i) {
10
            if (!isDeleted[i]) {
11
                ++count;
12
                for (unsigned times = 1; i * times <= n; ++times) {
13
                    isDeleted[i*times] = true;
14
                }
15
            }
16
        }
17
        return count;
18
    }
19
};

LeetCode 207-Course Schedule

分析

很显然,这是一个有向无环图的判断问题。只要所有课程中出现了环,就不可能修满所有课程。有向无环图的判断可采用dfs或bfs,至于生成图的形式可以是邻接矩阵,也可以是邻接表。为了减小时间复杂度,本题考虑采用邻接表的方法。

1
class Solution {
2
public:
3
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
4
        if (!prerequisites.size()) return true;
5
        vector<vector<int>> map(numCourses, vector<int>());
6
        for (int i = 0; i < prerequisites.size(); ++i) {
7
            map[prerequisites[i][0]].push_back(prerequisites[i][1]);
8
        }
9
        vector<bool> isVisited(numCourses, false);
10
        for (int i = 0; i < numCourses; ++i) {
11
            if (!isVisited[i]) {
12
                vector<bool> onStack(numCourses, false);
13
                if (hasCycle(map, i, isVisited, onStack))
14
                    return false;
15
            }
16
        }
17
        return true;
18
    }
19
    bool hasCycle(vector<vector<int>> &map, int i, vector<bool> &isVisited, vector<bool> &onStack) {
20
        isVisited[i] = true;
21
        onStack[i] = true;
22
        for (int k : map[i]) {
23
            if (onStack[k])
24
                return true;
25
            else
26
                if (hasCycle(map, k, isVisited, onStack))
27
                    return true;
28
        }
29
        onStack[i] = false;
30
        return false;
31
    }
32
};

LeetCode 208-Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.

题意

实现一个字典树,包含插入、查找和前缀查找功能。所有的输入都是小写字母a-z。

分析

就是一个正常的字典树实现,每个节点包含26个指向孩子节点的指针,和标识字典中单词结尾的isTail标识。初始化时26个指针child[i]NULLisTailfalse

注意

  • startsWith(prefix)方法不需要待检查的prefix是字典树中单词的结尾;
  • search(key)方法要求待检查key是字典树中单词的结尾;
  • 对指针数组的声明应该是TrieNode *child[26]

AC代码

1
class TrieNode {
2
public:
3
    // Initialize your data structure here.
4
    TrieNode() {
5
        for (int i = 0; i != 26; ++i) {
6
            child[i] = NULL;
7
            isTail = false;
8
        }
9
    }
10
    TrieNode *child[26];
11
    bool isTail;
12
};
13
14
class Trie {
15
public:
16
    Trie() {
17
        root = new TrieNode();
18
    }
19
20
    // Inserts a word into the trie.
21
    void insert(string s) {
22
        TrieNode *curr = root;
23
        for (int i = 0; i != s.size(); ++i) {
24
            int index = find(s[i]);
25
            if (!curr->child[index]) {
26
                curr->child[index] = new TrieNode();
27
            }
28
            curr = curr->child[index];
29
        }
30
        curr->isTail = true;
31
    }
32
33
    // Returns if the word is in the trie.
34
    bool search(string key) {
35
        TrieNode *curr = root;
36
        for (int i = 0; i != key.size(); ++i) {
37
            int index = find(key[i]);
38
            if (!curr->child[index]) return false;
39
            curr = curr->child[index];
40
        }
41
        if (!curr->isTail) return false;
42
        return true;
43
    }
44
45
    // Returns if there is any word in the trie
46
    // that starts with the given prefix.
47
    bool startsWith(string prefix) {
48
        TrieNode *curr = root;
49
        for (int i = 0; i != prefix.size(); ++i) {
50
            int index = find(prefix[i]);
51
            if (!curr->child[index]) return false;
52
            curr = curr->child[index];
53
        }
54
        return true;
55
    }
56
57
private:
58
    TrieNode* root;
59
    int find(char ch) { return ch - 'a'; }
60
};
61
62
// Your Trie object will be instantiated and called as such:
63
// Trie trie;
64
// trie.insert("somestring");
65
// trie.search("key");

LeetCode 209-Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

题意

给出一个包含n个正整数的数组和一个正整数s,找到长度最小的(连续)子数组使其和大于等于s。如果不存在这样的子数组,返回0。

比如数组为[2, 3, 1, 2, 4, 3],s = 7。子数组[4, 3]是长度最小的子数组,其和4+3≥7。

分析

使用一种在线处理的方法,类似“数组的最大子数组和”的O(n)解法。

步骤

  • 我们设置bottom和top控制子数组的头部和尾部。
  • 初始化bottom=0,top为-1,表示一个空的子数组
  • 子数组和sum=0,最小长度len=0。
  • 当sum < s时,在当前子数组的尾部增加一个元素bottom[++top]。
  • 当sum ≥ s时,去掉当前子数组的头部元素,并++bottom。
  • 退出循环的条件:top == nums.size() 或 bottom>top(此时已经存在最小len为1,不可能更小,可以退出)。

算法复杂度

由于top和bottom至多遍历一次数组nums,因此算法复杂度为O(n)。

更多练习

题目要求再给出一种O(nlogn)的解法。

简略分析

采用分治法的思想。每次将区间A一分为二,成为A1和A2。子问题是求两个子区间A1和A2中的各自的最小子数组长度len1和len2,以及区间A的最小子数组长度len中的最小值,即min{len1, len2, len}。

算法复杂度

主定理master定理)可知:T(n) = 2T(n/2) + n,故算法复杂度为*O(nlogn)**。

AC代码

O(n)及O(nlogn)算法

1
//O(n)
2
class Solution {
3
public:
4
    int minSubArrayLen(int s, vector<int>& nums) {
5
        if (!nums.size()) return 0;
6
        int bottom = 0, top = -1;
7
        int sum = 0, len = 0;
8
        while (true) {
9
            if (sum < s) {
10
                ++top;
11
                if (top != nums.size())
12
                    sum += nums[top];
13
                else
14
                    break;
15
            } else {
16
                sum -= nums[bottom]; ++bottom;
17
                if (bottom > top)
18
                    break;
19
            }
20
            if (sum >= s) {
21
                int new_len = top - bottom + 1;
22
                if (!len || len && new_len < len)
23
                    len = new_len;
24
            }
25
        }
26
        return len;
27
    }
28
};
29
30
//O(nlogn)
31
class Solution {
32
public:
33
    int MAX_INT = 999999999;
34
    int minSubArrayLen(int s, vector<int>& nums) {
35
        if (!nums.size()) return 0;
36
        return findMinLen(s, nums, 0, nums.size() - 1);
37
    }
38
    int findMinLen(int s, vector<int>& nums, int bottom, int top) {
39
        if (top == bottom) return nums[top] >= s ? 1 : 0;
40
        int mid = (bottom + top) / 2;
41
        int left = mid, right = mid + 1, sum = 0, len;
42
        while (sum < s && (right <= top || left >= bottom)) {
43
            if  (right > top) {
44
                sum += nums[left]; --left;
45
            }
46
            else if (left < bottom) {
47
                sum += nums[right]; ++right;
48
            }
49
            else if (nums[left] > nums[right]) {
50
                sum += nums[left]; --left;
51
            }
52
            else {
53
                sum += nums[right]; ++right;
54
            }
55
        }
56
        if (sum >= s) {
57
            len = right - left - 1;
58
            int leftLen = findMinLen(s, nums, bottom, mid);
59
            int rightLen = findMinLen(s, nums, mid + 1, top);
60
            return minValue(leftLen, rightLen, len);
61
        }
62
        else {
63
            return 0;
64
        }
65
    }
66
    int minValue(int x, int y, int z) {
67
        if (!x) x = MAX_INT;
68
        if (!y) y = MAX_INT;
69
        if (x <= y && x <= z) return x;
70
        if (y <= x && y <= z) return y;
71
        return z;
72
    }
73
};

LeetCode 210-Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

1
4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

题意

共有n节课程,课程编号从0至n-1。一些课程可能有先修要求,比如修0号课程前需要先修1号课程,表示为[0,1]。题目给出课程数和先后修课程对,要求返回完成所有课程的顺序。可能有很多正确的上课顺序,你只需返回其中一种。如果不可能完成,则返回空数组。

比如:

1
2, [[1,0]]

共有2节课程。选修1号课程前需要先修0号课程,故上课顺序为[0,1]

1
4, [[1,0],[2,0],[3,1],[3,2]]

共有4节课程。正确的上课顺序为[0,2,1,3]

提示:

输入的prerequisites是由边表示的图,而非邻接矩阵。

分析

此题是Leetcode207-Course Schedule的进阶版,前者只需得出能否完成所有课程即可,本题还需要给出上课顺序。实际上这是一个求拓扑排序的题(至于是拓扑全序还是拓扑偏序,是不一定的)。可以有2种求解方法。

  • 第一种:采用bfs。前处理时得到每个节点的入度。每次将入度为0的节点入队。出队时将出队节点的邻接节点的入度减1,并将出队节点编号计入answer数组中。循环该过程直到队列为空。如仍有节点未被访问,则说明课程关系图中出现了环,不可能完成所有课程。否则,answer中的编号顺序就是上课顺序。

  • 第二种:采用dfs。需要一个onStack数组纪录dfs的路径上的节点,用于判断环的存在。而isVisited数组责纪录dfs中访问过的节点。而其reversePostOrder就是上课顺序。具体可以google搜索reversePostOrder。这种方法比较难理解,但很有意思。最终给出的AC代码也是第二种方法。

注意

  • 值得注意的是,特殊情况输入numCourses = 1,prereqisities为空数组时,答案为[0],只有1个节点,并没有边的存在。

  • 第二种方法中onStack在每次结束本次递归时,需要变为false,表示这条路径上后面的节点在后面的判断环中,不会被认为是同一路径上的节点。(感觉好绕)

AC代码

1
class Solution {
2
public:
3
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
4
        vector<int> answer;
5
        if (numCourses == 1) {
6
            answer.push_back(0); return answer;
7
        }
8
        vector<vector<int>> map(numCourses, vector<int>());
9
        stack<int> reversePostOrder;
10
        for (int i = 0; i < prerequisites.size(); ++i) {
11
            map[prerequisites[i].second].push_back(prerequisites[i].first);
12
        }
13
        vector<bool> isVisited(numCourses, false);
14
        for (int i = 0; i < numCourses; ++i) {
15
            if (!isVisited[i]) {
16
                vector<bool> onStack(numCourses, false);
17
                if (hasCycle(map, i, isVisited, onStack, reversePostOrder))
18
                    return answer;
19
            }
20
        }
21
        while (!reversePostOrder.empty()) {
22
            int index = reversePostOrder.top(); reversePostOrder.pop();
23
            answer.push_back(index);
24
        }
25
        return answer;
26
    }
27
    bool hasCycle(vector<vector<int>> &map, int i, vector<bool> &isVisited, vector<bool> &onStack, stack<int> &reversePostOrder) {
28
        isVisited[i] = true;
29
        onStack[i] = true;
30
        for (int k : map[i]) {
31
            if (onStack[k])
32
                return true;
33
            else if (!isVisited[k])
34
                if (hasCycle(map, k, isVisited, onStack, reversePostOrder))
35
                    return true;
36
        }
37
        onStack[i] = false;
38
        reversePostOrder.push(i);
39
        return false;
40
    }
41
};
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×