I actually really enjoyed this weekly contest, shame that it got unrated due to server issues. This is my first time doing a short editorial so here goes:
Q1: You can simply check each time if you've visited the cell before or not. I used a map that maps pairs to a boolean since it's faster for me to code, but a more efficient way would be to use an array and start at the coordinate (1000, 1000).
Q2: Obtain the modulo k for each number. First check that the number of numbers equal to 0 mod k are even, and the number of numbers equal to k / 2 (if k is even), is also even. This is because numbers 0 and k/2 mod k can only be paired with themselves.
Then we check that each pair of modulos that add up to k: count(i) == count(k - i). This is the solution I coded up during the contest.
An even better solution however will be to make the observation that since the array length is even, the final sum must be equal to 0 mod k. Thus all we have to check is if the sum of all numbers in the array is divisible by k, that's it!
Q3: Notice how you can sort the array and choose elements and the elements you've chosen will still be a subsequence of the original array. Say you fix a number x, then all numbers after x in the array will be greater than x. Find the last number after x such that the number is less than or equal to target - x using binary search. You can thus choose any subset between x and the number you found.
Q4: Let's fix the second point (x_j, y_j), and we want to find (x_i, y_i) such thati < j and x_j - x_i <= k, that maximizes our equation. Notice we can rewrite the equation from (y_i + y_j) + |x_i - x_j| to (x_j + y_j) + (y_i - x_i). Now i and j are independent of each other. We can keep a sliding window that ensures x_j - x_i <= k and keep a sorted structure of the values (y_i - x_i). Then at each step j, our maximum we can obtain is (x_j + y_j) + max_{i in sorted structure}(y_i - x_i).
Q1 Code:
typedef pair<int, int> pii;
class Solution {
public:
map<pii, bool> vis;
bool isPathCrossing(string path) {
pii c = pii(0, 0);
vis[c] = 1;
for (int i = 0; i < path.size(); i++) {
if (path[i] == 'N') c.first++;
else if (path[i] == 'S') c.first--;
else if (path[i] == 'E') c.second++;
else c.second--;
if (vis[c]) return 1;
vis[c] = 1;
}
return 0;
}
};Q2 Code:
class Solution {
public:
bool canArrange(vector<int>& arr, int k) {
int n = arr.size();
vector<int> cnt(k + 5, 0);
for (int i = 0; i < n; i++) {
if (arr[i] < 0) arr[i] += k * abs((arr[i] - k) / k);
cnt[arr[i] % k]++;
}
if (cnt[0] % 2 == 1) return 0;
for (int i = 1; i <= k / 2; i++) {
if (i != k - i && cnt[i] != cnt[k - i]) return 0;
else if (i == k - i && cnt[i] % 2 == 1) return 0;
}
return 1;
}
};Q3 Code:
typedef long long LL;
const LL MOD = 1000000007;
class Solution {
public:
LL pow[100005];
int numSubseq(vector<int>& nums, int target) {
int n = nums.size();
pow[0] = 1LL;
for (int i = 1; i <= n; i++) pow[i] = (2LL * pow[i - 1]) % MOD;
sort(nums.begin(), nums.end());
LL ans = 0;
for (int i = 0; i < n; i++) {
int L = i, R = n - 1;
while (L < R) {
int mid = (L + R + 1) / 2;
if (nums[mid] > target - nums[i]) R = mid - 1;
else L = mid;
}
if (nums[i] + nums[L] > target) continue;
ans = (ans + pow[L - i]) % MOD;
}
return ans;
}
};Q4 Code:
class Solution {
public:
int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
multiset<int> ms;
int ans = -INT_MAX;
for (int i = 0, prv = 0; i < point.size(); i++) {
while (ms.size() && points[i][0] - points[prv][0] > k) {
ms.erase(ms.find(points[prv][1] - points[prv][0]));
prv++;
}
if (ms.size()) ans = max(ans, points[i][0] + points[i][1] + *(--ms.end()));
ms.insert(points[i][1] - points[i][0]);
}
return ans;
}
};