[C++] Some thoughts of this special BFS
Problem Statement\nLet\'s first try to understand this problem:\n1. There is an array A of size n, which has only one 1 and all other elements are 0s. Initially
# Problem Statement\nLet\'s first try to understand this problem:\n1. There is an array ```A``` of size ```n```, which has only one ```1``` and all other elements are ```0```s. Initially this ```1``` is located at index ```p```\n2. An operation is allowed: finding a subarray of ```A``` whose size is ```k```, and reverse this subarray, **this means we can move the only ```1``` around in this way**. This operation can be performed numerously\n3. When performing the operation above, the only ```1``` of ```A``` can\'t be moved to banned positions, denoted as an array ```banned```\n4. This problem requires an output of an array ```ans``` whose size is also ```n```, and ```ans[i]``` means the minimum number of operations to move the only ```1``` to index ```i``` from initial index ```p```\n\n# Preparation\n\nSay the only ```1``` is located at index ```p```, what positions can it be moved to if we perform the operation for once?\n\nIt depends on ```p,n,k```. Intuitively, we can pick subarray ```[p-k+1 ... p]```, and reverse it to make the only ```1``` move to index ```p-k+1```, the leftmost index it can be moved to. However, if ```p-k+1<0```, the subarray is out of the range and it shouldn\'t be picked, so we need to put some constraints considering the array size ```n```.\n\nAssume the subarray we pick in operation is ```[l ... r]```, where ```r = l+k-1```. On the one hand, this subarray must contain the only ```1```, so ```l >= p-k+1, r <= p+k-1```; On the other hand, this subarray can\'t reside out of the range, so ```l >= 0, r < n```. These are all the constraints we need: ```max(0,p-k+1) <= l <= min(n-1,p+k-1)-(k-1)```.\n\nUnder the assumptions above, we move the only ```1``` to index ```p\'```. We know that ```p``` and ```p\'``` should be symmetric in the subarray ```[l...r]```, that is ```p-l=r-p\'```, which means ```p\'=2l+(k-1)-p```\n\nIt reveals that from an index ```p```, **we can move the only ```1``` to a series of indexes with the same parity, and these indexes are continuous odd or even numbers**\n\nHere is the function to get all these indexes given the only ```1```\'s initial position ```x```, subarray size ```k``` and array size ```n```:\n\n```\npair<int, int> getRange(int x, int n, int k)\n{\n    int l = max(x - k + 1, 0), r = min(x, n - k);\n    int L = 2 * l + k - 1 - x, R = 2 * r + k - 1 - x;\n    return {L, R};\n}\n```\n\n# Intuition\n\nPreparation done, now we know how to move the only ```1``` from one index to next ones. It follows naturally that this problem can be modeled as ```finding the minimum path length in a graph```, and **BFS** (Breadth First Search) can be employed immediately:\n\n(TLE version of BFS)\n```\nvector<int> minReverseOperations(int n, int p, vector<int>& banned, int k)\n{\n    unordered_set<int> B(banned.begin(), banned.end());\n    vector<int> ans(n, -1);\n    queue<int> q;\n    q.push(p);\n    ans[p] = 0;\n    while(!q.empty())\n    {\n        int x = q.front(); q.pop();\n        pair<int, int> R = getRange(x, n, k);\n        for(int y = R.first; y <= R.second; y += 2)\n        {\n            if(ans[y] != -1 || B.count(y)) continue;\n            ans[y] = ans[x] + 1;\n            q.push(y);\n        }\n    }\n    return ans;\n}\n```\nHere ```ans``` serves both as the result and the usual ```visited``` array in BFS to denote whether this index has been visited. The array ```banned``` is transformed in to an **unordered_set** to quickly check if we move the ```1``` to banned positions. Everything seems to be ok, except this solution causes **TLE (Time Limit Exceed)**!\n\n# Approach\n\nLet\'s revisit the solution above: we are solving a problem of ```finding the minimum path length in a graph```. By using BFS, the time complexity is ```O(N+E)```, where ```N``` and ```E``` denotes the number of nodes and edges of this graph. Here we have ```n``` nodes, but the number of edges can be as large as ```O(n^2)```!  Considering ```n``` can be as large as ```1e5```, a solution of ```O(n^2)``` time can probably cause TLE.\n\nThe key idea to reduce the number of edges is to make use of an important observation mentioned above: **we can move the only ```1``` to a series of indexes with the same parity, and these indexes are continuous odd or even numbers**.\n\nThis observation shows that the edges of a node follows a strict rule, not as random as some casual graphs. Each time we wish to visit the neighbors of a node, we are certain that **the indexes of these neighbors resides in a range with the same parity**, so we can rule out useless edges just like the array  ```visited``` to rule out visited nodes.\n\nHence we maintain two **sets** by parity, one for odd numbers and another for even numbers. By using **set** we can access a certain range quickly (O(logn) time). After visiting a node, we erase it from the two sets, which means we also erase all the edges leading to this node. This is how we reduce the number of edges at the same time with traversing the graph.\n\n# Code\n```\n\nclass Solution {\npublic:\n    pair<int, int> getRange(int x, int n, int k)\n    {\n        int l = max(x - k + 1, 0), r = min(x, n - k);\n        int L = 2 * l + k - 1 - x, R = 2 * r + k - 1 - x;\n        return {L, R};\n    }\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k)\n    {\n        set<int> E[2];\n        for(int i = 0; i < n; i++) E[i & 1].insert(i);\n        int B = (int)banned.size();\n        for(int i = 0; i < B; i++) E[banned[i] & 1].erase(banned[i]);\n        vector<int> ans(n, -1);\n        queue<int> q;\n        q.push(p);\n        ans[p] = 0;\n        E[p & 1].erase(p);\n        while(!q.empty())\n        {\n            int x = q.front(); q.pop();\n            pair<int, int> R = getRange(x, n, k);\n            set<int>& cur = E[R.first & 1];\n            auto it = cur.lower_bound(R.first);\n            while(it != cur.end() && *it <= R.second)\n            {\n                ans[*it] = ans[x] + 1;\n                q.push(*it);\n                it = cur.erase(it);\n            }\n        }\n        return ans;\n    }\n};\n```\n\n# Complexity\n- Time complexity:\nO(nlog(n))\n\n- Space complexity:\nO(n)\n\n# Some Thoughts\n\nWhy can we reduce the number of edges in this problem, but generaly we can\'t in classic BFS problems?\n\nIn classic BFS problem, we usually create adjacency list **explicitly**,  therefore all the edges exist in the memory. This problem however, the adjacency list exists **implicitly**\uFF0Cand actually we make use of a function ```getRange``` to produce adjacency list on the fly, which gives us chance to reduce the number of edges involved since they don\'t exist beforehand.
['C++']