My Solutions to Contest 2


  • 10
    C

    Update: New Solution added.

    I was outside today, so I didn't participate this contest, but after I arrived home, I found that I can make submissions so I tried all of them.

    IMHO, those are three easy problems or two easy plus one medium in turns of thinking process, but the last one is a little bit tricky to implement a acceptable solution, so OK, it could be a hard one, I used around 2 hours to solve all of them.

    First two are not worth to mention too much. I just paste my C++ code here:

    class Solution {
    public:
        char findTheDifference(string s, string t) {
            vector<int> cnts(26, 0), cntt(26, 0);
            for (auto x: s) cnts[x - 'a'] ++;
            for (auto x: t) cntt[x - 'a'] ++;
            for (int i = 0; i < 26; ++i)
                if (cntt[i] > cnts[i])
                    return i + 'a';
            return 'a';
        }
    };
    
    class Solution {
        int lastRemaining(int n, int d) {
            if (n == 1) return 1;
            int res = lastRemaining(n / 2, d ^ 1) * 2;
            if ((n & 1) || d)
                return res;
            return res - 1;
        }
    public:
        int lastRemaining(int n) {
            return lastRemaining(n, 1);
        }
    };
    

    I have three different solutions to the last problem, but unfortunately, only the last one is accepted due to the memory limited issue. My thinking process was actually following the order of those three solutions.

    For those who don't know a technique call discretize - it is actually a mapping from a bigger space to a smaller space so we could deal with large space. For example, we have an array {0, 1, 500,123000000, 50000} has only 5 elements, but the range of elements in this array is very large which is [0, 123000000]. If we want to use them as indices, we have to allocate a very large array which our computers can not afford. So we sort them first, then for every unique element, we assign the current smallest integer to it, in this example, we can use this mapping {0 => 0, 1 => 1, 500 => 2, 123000000 => 4, 50000 => 3}.

    In C++, there is an easy way to do this without using map.

    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    

    if we want the corresponding index, then

    int index = lower_bound(v.begin(), v.end(), x) - v.begin();
    

    note that x must be presented in v.

    Let the number of unique y coordinate be n, and the number of unique x coordinate be m, and the number of rectangles be r.

    We apply discretization to x and y coordinates first, so we actually only need to check n * m entries to see if all of them equal to 1.

    It is bad to initialize this 2D area by adding every entry of every rectangle, because it is O(rnm) time complexity.

    Note that for each rectangle [x1, y1, x2, y2], we actually only need to do this

    add 1 to (x2, y2)
    add 1 to (x1, y1)
    add -1 to (x1, y2)
    add -1 to (x2, y1)
    

    after we do this for each rectangle. In the 2D area, for each entry, the prefix sum of (i, j) (the sum of the rectangle from (0, 0) to (i, j)) means how many times (i, j) was occupied by those rectangles. (Think about why.)

    Then we check if every entry equals to 1.

    Since this involves prefix sum, binary indexed tree came to my mind first,

    • First solution, 2D Binary Indexed Tree, time complexity O(r * log(n) * log(m) + nmlog(nm)), space complexity O(r + nm).

    But actually BIT is not necessary, so

    • Second solution, 2D array, time complexity O(r + nm), space complexity O(r + nm)

    And this is still Memory Limit Exceeded, hmm, OK, I will do sweeping line anyway,

    • Third solution, sweeping line, time complexity O(rlogr + nr), space complexity O(r + n)
    int c[5510];
    class Solution {
        int maxn, maxm;
        bool check() {
            int sum = 0;
            for (int i = 1; i < maxn; ++i) {
                sum += c[i];
                if (sum != 1) return false;
            }
            return true;
        }
    public:
        bool isRectangleCover(vector<vector<int>>& rectangles) {
            vector<int> x, y;
            for (auto& v: rectangles)
                for (int i = 0; i < v.size(); ++i)
                    if (i & 1) y.push_back(v[i]);
                    else x.push_back(v[i]);
            sort(x.begin(), x.end());
            sort(y.begin(), y.end());
            x.resize(unique(x.begin(), x.end()) - x.begin());
            y.resize(unique(y.begin(), y.end()) - y.begin());
            
            maxn = y.size(), maxm = x.size();
            memset(c, 0, sizeof c);
            vector<vector<int>> edges;
            for (auto& v: rectangles) {
                int nv[4] = {0, 0, 0, 0};
                for (int i = 0; i < v.size(); ++i) {
                    if (i & 1)
                        nv[i] = lower_bound(y.begin(), y.end(), v[i]) - y.begin() + 1;
                    else
                        nv[i] = lower_bound(x.begin(), x.end(), v[i]) - x.begin() + 1;
                }
                vector<int> l({nv[0], -1, nv[1], nv[3]}), r({nv[2],  1, nv[1], nv[3]});
                edges.push_back(l);
                edges.push_back(r);
            }
            sort(edges.begin(), edges.end());
            for (int i = 0, cur = 1; i < edges.size(); ++i) {
                vector<int>& edge = edges[i];
                if (cur != edge[0]) {
                    if (!check()) return false;
                    cur = edge[0];
                }
                c[edge[2]] -= edge[1];
                c[edge[3]] += edge[1];
            }
            return true;
        }
    };
    

    After discussed with my friend, I realized that using only sweep line is enough, we don't need to think too much of the entry by entry check, but only to calculate the area of covered region. The time complexity is O(r log r), which is a huge improvement of my previous solutions. Here is the code, if you want more detailed explanation, please leave reply.:

    struct node {
        int len, cover;
    }tree[1 << 15];
    int y[21110];
    class Solution {
        int ylen;
        void pushup(int rt, int l, int r) {
            if (tree[rt].cover)
                tree[rt].len = y[r + 1] - y[l];
            else if (l == r)
                tree[rt].len = 0;
            else
                tree[rt].len = tree[rt << 1].len + tree[rt << 1 | 1].len;
        }
        void update(int L, int R, int l, int r, int v, int rt) {
            if (l <= L && R <= r) {
                tree[rt].cover += v;
                pushup(rt, L, R);
                return;
            }
            int mid = (L + R) >> 1;
            if (l <= mid) update(L, mid, l, r, v, rt << 1);
            if (mid < r) update(mid + 1, R, l, r, v, rt << 1 | 1);
            pushup(rt, L, R);
        }
    public:
        bool isRectangleCover(vector<vector<int>>& rectangles) {
            int cor[4] = {INT_MAX, INT_MAX, 0, 0}, totalArea = 0, real = 0;
            vector<vector<int>> edges;
            ylen = 0;
            for (auto& v: rectangles) {
                y[ylen++] = v[1];
                y[ylen++] = v[3];
            }
            sort(y, y + ylen);
            ylen = unique(y, y + ylen) - y;
            memset(tree, 0, sizeof tree);
            for (auto& v: rectangles) {
                cor[0] = min(cor[0], v[0]), cor[1] = min(cor[1], v[1]);
                cor[2] = max(cor[2], v[2]), cor[3] = max(cor[3], v[3]);
                int y1 = lower_bound(y, y + ylen, v[1]) - y;
                int y2 = lower_bound(y, y + ylen, v[3]) - y - 1;
                edges.push_back({v[0], -1, y1, y2});
                edges.push_back({v[2],  1, y1, y2});
                real += (v[2] - v[0]) * (v[3] - v[1]);
            }
            if (real != (cor[2] - cor[0]) * (cor[3] - cor[1]))
                return false;
            
            sort(edges.begin(), edges.end());
            for (int i = 0, cur = cor[0]; i < edges.size(); ++i) {
                vector<int>& e = edges[i];
                if (cur != e[0]) {
                    totalArea += tree[1].len * (e[0] - cur);
                    cur = e[0];
                }
                update(0, ylen - 1, e[2], e[3], -e[1], 1);
            }
            return totalArea == (cor[2] - cor[0]) * (cor[3] - cor[1]);
        }
    };
    

    Thanks for reading.


  • 0
    S

    I agree with your last point here: I also wasted some submissions (TLE) during the contest because I didn't know the limits of the test cases. It would be nice to know the constraints (including the time and memory limits), at least for contest problems. These changes would improve this site a lot.


  • 0
    E

    Ding mishen. Wo de virgin reply in LeetCode.


  • 4

    This is the most comprehensive solution report I have ever seen in LC.

    Genius solution!!! Holy High (hao li hai)!!!


  • 0
    F

    This is nice solution!!
    It would be great if you offer Java solution as well.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.