Tutorial
Tutorial is loading...
Code
#include <iostream>
using namespace std;
void solve() {
int t, a, b, x, y;
cin >> t >> a >> b >> x >> y;
auto solve = [&](int t, int a, int b, int x, int y) {
int cur = 0;
cur += max((t - a + x) / x, 0);
t -= max((t - a + x) / x, 0) * x;
cur += max((t - b + y) / y, 0);
return cur;
};
cout << max(solve(t, a, b, x, y), solve(t, b, a, y, x)) << endl;
}
signed main() {
int q = 1;
cin >> q;
while (q --> 0)
solve();
return 0;
}
Tutorial
Tutorial is loading...
Code
def solve():
w, h, a, b = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
if x1 == x2:
if abs(y1 - y2) % b == 0:
return "Yes"
else:
return "No"
if y1 == y2:
if abs(x1 - x2) % a == 0:
return "Yes"
else:
return "No"
if (x1 - x2) % a == 0 or (y1 - y2) % b == 0:
return "Yes"
return "No"
t = int(input())
for _ in range(t):
print(solve())
Tutorial
Tutorial is loading...
Code
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <unordered_map>
#include <random>
#include <chrono>
#include <cassert>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <queue>
#include <unordered_set>
#include <fstream>
#include <random>
using namespace std;
using ll = long long;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 500;
int sum[MAXN + 1][MAXN + 1];
int n, m, k;
int check(int i, int mx) {
return min(max(i, 0), mx);
}
int pref(int i, int j) {
return sum[check(i, n)][check(j, m)];
}
void solve() {
cin >> n >> m >> k; k--;
vector<string> mine(n);
int all_gold = 0;
for (int i = 0; i < n; i++) {
cin >> mine[i];
for (int j = 0; j < m; j++) {
all_gold += (mine[i][j] == 'g');
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + (mine[i][j] == 'g');
}
}
int ans = all_gold;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mine[i][j] == '.') {
int a = i - k, b = i + k + 1, c = j - k, d = j + k + 1;
ans = min(ans, pref(b, d) - pref(a, d) - pref(b, c) + pref(a, c));
}
}
}
cout << all_gold - ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Tutorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) ((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const char en = '\n';
const int INF = 1e9 + 7;
const ll INFLL = 1e18;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#ifdef LOCAL
#include "debug.h"
#define numtest(x) cerr << "Test #" << (x) << ": " << endl;
#else
#define debug(...) 42
#define numtest(x) 42
#endif
int merge(const vector<int> &a, const vector<int> &b) {
int n = sz(a);
int res = 0;
for (int c = 0, i = 0, j = 0; c < n; ++c) {
if (a[i] > b[j]) {
++res;
++i;
} else if (a[i] < b[j]) {
++j;
} else {
assert(0);
}
}
return res;
}
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
vector<int> pref_min(n), suf_max(n);
pref_min[0] = 0;
for (int i = 1; i < n; ++i) {
pref_min[i] = pref_min[i - 1];
if (a[i] < a[pref_min[i - 1]]) {
pref_min[i] = i;
}
}
suf_max[n - 1] = n - 1;
for (int i = n - 2; i >= 0; --i) {
suf_max[i] = suf_max[i + 1];
if (a[i] > a[suf_max[i + 1]]) {
suf_max[i] = i;
}
}
int cur = merge(a, b);
int l = cur, r = n;
while (r - l > 1) {
int m = l + (r - l) / 2;
swap(a[pref_min[m - 1]], a[suf_max[m]]);
if (merge(a, b) >= m) {
l = m;
} else {
r = m;
}
swap(a[pref_min[m - 1]], a[suf_max[m]]);
}
cout << l << en;
}
int32_t main() {
int tests = 1;
#ifdef LOCAL
freopen("input.txt", "r", stdin);
tests = 1;
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif
cin >> tests;
for (int testcase = 1; testcase <= tests; ++testcase) {
solve();
}
return 0;
}
Tutorial
Tutorial is loading...
Code
//#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
//#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
int Bit(int mask, int b) { return (mask >> b) & 1; }
template<class T>
bool ckmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<class T>
bool ckmax(T &a, const T &b) {
if (b > a) {
a = b;
return true;
}
return false;
}
// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
--l;
while (r - l > 1) {
T mid = l + (r - l) / 2;
if (predicat(mid)) {
r = mid;
} else {
l = mid;
}
}
return r;
}
template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
return FindFirstTrue(l, r, predicat) - 1;
}
const int INFi = 2e9;
const ll INF = 2e18;
void solve() {
int n, m, x, y; cin >> n >> m >> x >> y;
x--;
y--;
vvi g(n);
rep(_, n - 1) {
int u, v; cin >> u >> v;
u--;
v--;
g[u].push_back(v);
g[v].push_back(u);
}
vector<vi> block;
vi path;
auto dfs = [&] (auto &&self, int v, int p, int t) -> bool {
path.push_back(v);
if (v == t) return true;
for(auto &u : g[v]) {
if (u == p) continue;
if (self(self, u, v, t)) return true;
}
path.pop_back();
return false;
};
rep(i, m) {
int a, b; cin >> a >> b;
a--;
b--;
dfs(dfs, a, -1, b);
assert(!path.empty());
if (block.size() < path.size()) block.resize(path.size());
rep(j, path.size()) block[j].push_back(path[j]);
path.clear();
}
vector<bool> ok(n, false);
vi q;
q.push_back(x);
vector<bool> cur(n, false);
vi was(n, -1);
for(int t = 0;;++t) {
if (t < block.size()) for(auto &u : block[t]) cur[u] = true;
vi nxt;
for(auto &v : q) {
if (ok[v] || cur[v] || was[v] == t) continue;
was[v] = t;
bool nei = 0;
for(auto &u : g[v]) nei |= ok[u];
if (t && !nei) continue;
nxt.push_back(v);
}
q.clear();
if (t < block.size()) {
for(auto &u : block[t]) {
cur[u] = false;
if (ok[u]) {
ok[u] = false;
}
q.push_back(u);
}
}
for(auto &v : nxt) {
assert(!ok[v]);
ok[v] = true;
for(auto &u : g[v]) {
if (!ok[u]) {
q.push_back(u);
}
}
}
if (ok[y]) {
cout << t + 1 << '\n';
return;
}
if (t > (int)block.size() && q.empty()) {
cout << "-1\n";
return;
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout << setprecision(12) << fixed;
int t = 1;
cin >> t;
rep(_, t) {
solve();
}
return 0;
}
Tutorial
Tutorial is loading...
Code
#include "bits/stdc++.h"
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> b(n);
for (int i = 0; i < n; i++) {
cin >> b[i];
}
vector<int> want(n);
auto make = [&] (int i, int x, int y) {
if (!want[i]) {
if (a[i] != x) {
swap(a[i], b[i]);
}
want[i] = 1;
}
};
const int N = 2 * n + 22;
vector<vector<pair<int, int>>> g(N);
for (int i = 0; i < n; i++) {
g[a[i]].push_back({b[i], i});
g[b[i]].push_back({a[i], i});
}
vector<int> used(N);
auto dfs = [&] (auto&& dfs, int v, int h) -> void {
used[v] = h;
for (auto& [u, i] : g[v]) {
if (used[u] <= 0) {
make(i, v, u);
dfs(dfs, u, h + 1);
} else if (used[u] < used[v]) {
make(i, v, u);
}
}
};
for (int i = 0; i < N; i++) {
if (used[i] == 0 && int(g[i].size()) == 1) {
dfs(dfs, i, 1);
}
}
int rt;
auto find = [&] (auto&& find, int v, int pr) -> void {
used[v] = -1;
for (auto& [u, i] : g[v]) {
if (used[u] == 0) {
find(find, u, i);
} else if (i != pr) {
rt = u;
}
}
};
for (int i = 0; i < N; i++) {
if (used[i] == 0 && !g[i].empty()) {
rt = -1;
find(find, i, -1);
dfs(dfs, rt, 1);
}
}
cout << set<int>(a.begin(), a.end()).size() + set<int>(b.begin(), b.end()).size() << '\n';
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << '\n';
for (int i = 0; i < n; i++) {
cout << b[i] << " ";
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
}
IT WAS TOO HARD FOR ME :(
I love these fast editorials :D
I think that $$$A,B$$$ were a bit too tough. I liked the contest, though.
In problem B ,I think for this testcase (3) answer should be yes, please explain why answer is no testcase :10 9 3 2, 0 0 4 3
If you think answer is yes.. you can just draw a picture and share it...
because I think understanding
YESis visually quite easy... to understandNOT POSSIBLEwill take some case workhttps://drive.google.com/file/d/1Dr68sVjseu48SEjAl0bqr2IJnqPbPWqs/view?usp=sharing
i think here answer is possible, please correct me what i did mistake
thanks for making the image.. what I mean is try to draw a pattern of tiles which cover the remaining area ...
like u have yellow area which is already blocked... try to add some green tiles which cover the remaining area... like the image given in the question.
Thank you so much now i figure out
On paper draw and try placing tiles of 3x2, you'll realize there's a thin alley like area between tiles that keeps forming, which you can't fill with 3x2 tiles.
Thank you
I think the edge case could be a bit tricky but they were of right difficulty tbh,
As a newbie, I was cooked!!
As a specialist, I was cooked!
As a pupil, I was cooked!
As a pupil, I was cooked!
As a expert, I was cooked!
Me too ;-;
as a former pupil and current newbie, i was cooked
As a former expert and current specialist, I was cooked
as a former specialist and current specialist, I was cooked!
As a CM, I was cooked!
As a specialist, I was cooked!
How did you reach master this soon!!! Any tips on how should I practise?
Solve daily problems slightly above your level, focusing on algorithms you’re weak at. Upsolve every contest: analyze code of top performers to learn new techniques. Persistence and targeted review beat random practice.
I believe you can also become a master!
Thank You,Orzzz
As a Master, I was cooked!
guessforces -> got back to purple
You can use a component named carrot to predict your rating.
Thanks, I already use it tho! By guessforces I meant I guessed some solutions (B and D) and that led me back to purple.
And you really get back to CM,congratulations!
Thanks Morning__Stars! Keep practicing like you currently are and you will reach purple too in no time.
someone can explain me: i didn't understand the D question 3rd test case
5
8 6 3 10 1 7 9 5 2 4
why i as a player can't swap 10 to 8 instead of 10 to 3 which is explained in ts.
if i swap 10 to 8, i collect more than 3 points.
swapping the max element to first card win you more game no ?
Score: 2
the game always ends after N rounds, not after one player ran out of cards.
Completely stuck in C for so long, was trapped thinking that it involved some graphs. It was really a tough contest.
Had the ideas for D (BS on Ans, minimum on pr fix + max in suffix) independently. But couldn't even understand how to implement it all. Interesting contest nonetheless, a little hard after a while.
Please,can you explain why this strategy is the most optimal?I thought about this problem and explanation for hours and didn't understand much
Ok When we play n turns, what happens is us choosing x from a, and n-x from b. We can binary search on answer for x. Since every value in a after xth index (1-based) is unused for x selections from a, we can greedily select the max value amongst them and replace it.
Now since we want it to reach x, we want the smallest value before it to be replaced with this new large value. Greedy choice
As a non-participate, I wonder why E seems harder than F.
Is F classic?
seems like it. I didn't solve it though.
once you see the graph model, kind of
A more classic thing is to direct the edges in a way that the difference of indegrees and outdegrees differ by at most one, and that obviously achieves 'every node with degree at least 2 has at least one indegree and one outdegree'
I upvote for superfast editorial
I enjoyed the problems.
The ideas of A and B are not difficult, but they require a lot of case-by-case discussions, which makes writing them rather laborious. I don't particularly like encountering such problems on Codeforces. On the contrary, I enjoy problem D, as the thinking process accounts for the majority of the time, and the code implementation part is very simple.
Wait really? B was basically a one-liner for me; I don't think there was any casework. Just
cout << ((x1 != x2 && !((x1-x2) % a)) || (y1 != y2 && !((y1-y2) % b)) ? "YES" : "NO") << '\n';. Even if you want to split it into multiple lines so it's easier to read, it's still at most three lines. I think A was also more or less three lines.I agree with you that I enjoyed problem D, though.
You're right. There are indeed simple ways to write A and B.
pretty tough contest, D trapped me making me think i might get it, though couldn't think of anything except bruteforce in c.
much respect for having n ^ 3 solutions pass on C , 2d prefix sum with out of bound stuff is pain
also you should add spoilers to the editorial got E spoiled for me
how to do in
n^3??.. I think brute force can be
n^4and I think my prefix sum approach isn^2so not sure aboutn^3techniqueI guess, if you only do 1d prefix sums, then you have to sum up O(k) prefix sums for each empty cell, yielding O(kn^2).
OK understood and thank you,
I think we will have to take care of bounds in the direction of prefix sum ... I thought OP had some approach which doesn't care about bounds.
For me, it wasn't an issue.
I just used Min() and Max() functions appropriately.
Fast editorial, without spoiler. So what? trash mathforces + gridforces + guessingforces round.
Can someone explain the problem C more clearly
Use an TNT and slowly move your TNT automaton around the grid.
the 2k-1 * 2k-1 golds will gone and you can get all golds in other places. Use prefix sum on grid to speed up counting how many gold will gone.
yeah i got it, however how it can be proven that after one "operation" i can get all golds in other places
just move your detonation 1 tile after each time.
When you move 1 position in any direction after detonating at current position, the additional cells (and gold ores in them) that the new detonation covers have already been picked up during the previous detonation. Hope that helps.
thanks everyone here for explanation
It was really hard for me (-_-)
I can't believe D was binary search, I spent an hour during the contest trying to verify a greedy strategy.
Actually you don't need binary search if you calculate prefix min, prefix 2nd smallest, and suffix max
can you elaborate? (got it nvm, thanks anways for an alternate soln)
you don't need binary search. for all i from 1 to n just store the smallest and second smallest numbers in the subarray a1,a2,a3...ai. also store the maximums for the subarray ai,a(i+1),...an. and store the minimum for the subarray b1,b2,...bi. I think this much is enough.
basically you need to take the first i cards from a, the first n-i+1 cards from b, check if you can make one swap such that the lowest number on these n+1 cards is one of the cards in b. if it is, it means that you can win at least i points if you play optimally, if not then you can't.
I think this solution works, but I haven't coded it yet, so there is a possibility that I am wrong
Edit: Coded this and the code got accepted
Very good point!
Задачи, начиная с Cшки интересные, не спорю, но вторая — просто самое ужасное, что можно было ожидать. Писать Келдыша 5часов и поторатить на B 40мин +- норм, но на двухчасовой див потратить 40+- минут не очень
Can anyone explain why this submission: 324507382 is giving TLE? I think the time complexity is $$$O(nlogn)$$$.
My check function uses dyanmic programming as follows: $$$dp[i][0]$$$ represents the minimum index with which $$$a_i$$$ can match if I have done no swaps in the first $$$i$$$ indices, and $$$dp[i][1]$$$ represents the same thing but considering that I have done one swap in the first $$$i$$$ indices, and swapped it with the maximum value outside the range I'm checking for.
I'm sorry, can you please upload again in python? I am having trouble reading the C++.
would you cleanup your code before sharing...
"maybe" mid = (low+high)/2
or something inside your check function, I didn't use DP so not sure.
Can someone give me proof intution for D's correctness? I don't understand how the property mentioned in the first sentence of the solution helps.
Here is my thought process:
Suppose, you were able to get k points. That means that at least first k cards from your deck and at most first (n-k) cards from dealer's deck were removed. It is also necessary that there was some card in dealers' deck that "lost" to your minimal card that "won". Thus:
minimum of your first k cards must be at least minimum of first (n-k+1) cards in dealer's deck. (+1 because the first card in dealer's hand to be untouched should be counted too)
Two important points:
this condition is sufficient to score at least k points.
you can manipulate minimum of your first k cards by swapping two cards. in fact, the optimal way is to switch minimum of your first k cards with maximum of the rest.
Thus, you can just find by binary search largest k for which:
second minimum of $$$a_1,a_2,\ldots a_k, \max(a_{k+1},a_{k+2},\ldots a_n)$$$ is greater than minimum of $$$b_1,b_2,\ldots b_{n-k+1}$$$
I, personally, handled edge cases (k=0 and k=n) separately. You can also just find corresponding prefix/suffix mins and maxs beforehand instead of doing binary search.
Thanks! That helps.
That makes so much sense, I think your explanation should be the official editorial for D.
Let's say our goal is just to win at least $$$t$$$ turns (Ignore that we are allowed to swap for the moment).
Since we use a card only when we win a turn, only the top $$$t$$$ cards will ever be used, so we can discard the rest of our $$$n-t$$$ cards. Similarly, the dealer wants to win just $$$n-t+1$$$ turns here, so the dealer only brings their top $$$n-t+1$$$ cards.
Now the new rules are: there are 2 piles with $$$t$$$ and $$$n-t+1$$$ cards, we play the game until one of piles is empty, and the empty pile wins. The pile with the minimum card will lose, because that card cannot ever win a turn. So its enough to check if $$$\min(a_1,\ldots,a_{t})$$$ > $$$\min(b_1,\ldots,b_{n-t+1})$$$. .
If we are allowed to swap, the best move is to swap out our minimum card with the maximum from the rest of our discarded cards (if its better). Note that we don't really need to binary search here, as we can check this for each $$$t$$$ in $$$O(1)$$$ by maintaining prefix and suffix arrays for min, max, and 2nd min (or a std::set).
Thanks for the simplified explanation! Makes sense now.
I was struggling to understand D's solution but this greatly helps.
shashlik was not the only one who got cooked in this contest.
Someone please help me, my submissions for question-2 give error after error. Last submission[submission:324523587]
Why did D come up with the idea of binary search? Who can prove the continuity of the answer? I feel that I cannot understand the correctness of binary search.
Hi, I don't quite understand the thought process in D: How do we know the function is monotonous (and what function i.e. whats the argument)? Why is that obvious from the data given by the tutorial that we need to switch the minimum? Also, shouldn't the last index that is less than a_{k_{j}} be a_{k_{j+1}-1} and not a_{k_{j+1}} by its definition? Would appreciate the help.
I was already answered by one of the comments above. Thank you!
Just think this:
If $$$\min(a_1, a_2, ..., a_i)$$$ is larger than $$$b_j$$$, then you can win at least $$$i$$$ times in the first $$$i+j-1$$$ rounds.
This helps. Thank you!
IMO F should be before D and E
sounds like you read too many ad-hoc problem
Although the solutions are simple, they're still hard to think during the contest...
I think my solution for E is similar to the editorial's but I approached it with a slightly different thought-process. I think it makes my solution a bit smaller than others' – still not sure of its time-complexity.
I initialise a flood-fill from x and repeated the following 2 steps until the flood reaches vertex y (or the flood dies down completely).
We can also think of this as Marat constantly spawning his clones and moving into every vertex he can to simulate the process of survival through brute-force.
what? why can you get AC? I think it has a wrong time-complexity, Would appreciate the help.
I just revisited my solution and I think it is exactly the same as the editorial. My comment was unanticipated and I added nothing new. Must've been in a different state of mind.
The problems are challenging. Great :)
Thank You for div. But too many matrix problems
Why are problems like A and B accepted to be at those positions :sob: ? I had to guess the solution for B and when the example was correct i just submited and hoped for acception hahaha
C was cool tho
Shorter solution for problem B
You don't need the abs() in there.
Oh yeah 😂 I forgot it's python 🥲.
It's not needed in Java or C++ either.
While in those languages
x % ymay be negative ifxis negative,x % y == 0still holds if and only ifxis a multiple ofy, which is all you're checking here.(And without
abs(),t > 0should then bet != 0of course.)A different more complicated approach for D
Let's simulate the game on the original arrays
It is easy to observe that the only element of array A which could be swaped to improve the score is the last element of A which lost a game (Exercise for the reader). Let it's position be ls. So there are at most N-ls positions with which we could try swapping it with. (Actually there are even less because there is no need to swap it with an element that won in the original simulation)
Now the problem is how to calculate efficiently the score for every potential swap (There may be easier ways to do this, also I don't know if this is considered difficult to come up with and code or I just had skill issues during contest and debugging)
Let's split the obtainable score and cost (as in rounds of the game it takes to obtain it) to 3 parts
1) The score and cost till reaching position ls is the same for all swaps as it isn't affected by it and can be calculated during the original simulation
2) For every element i we swap with ls, until we find a smaller element after it in A the score and cost is only determined by how many extra rounds we needed to lose after ls to take i + the extra ammount of elements we take. We take as many as possible and if there are remaining rounds move to step 3
3) For the first remaining element we calculate the cost of taking it. Now for the remaining elements the added cost of taking each of them is irrelevant to the actual swap that happened and we can precalculate it if we simulate the game again after removing ls. We take the largest prefix we can
Time Complexity O(nlogn)
Sorry if my explanation isn't clear, you can find my ugly implementation here 324571068
Would be cm had I implemented this in contest (╥﹏╥)
Used a similar approach. Our logic is more to the point, but implementation is lengthy.
Don't you think the idea of taking a maximum from suffix of "Is"( "Is" here is reference to coder3000's reply above) is a bit unexplained in the tutorial, or it seems intutitve??
We can't swap from the previous segments or you can say prefix because it is always less than the previous minima(in "b" array), since it is less than the current minima(in "b" array")
Can someone help with my TLE in F 324590873 . I thought I am visiting every edge exactly once in my dfs and thus code should have a tc of O(n).
Edit : I found the issue.
I solved B in more then hour, but solved C in 20 minutes after contest ;( B was kind of easy, but for me it was so hard to find right formula.
324503370 in this submission I just check to swap minimum in starting position result, but with all others maybe you can say any optimization to this algorithm or code
c: https://youtu.be/mWL7a444I0A
F can also be interpreted as euler path in each component, notice once u make a graph like edges from a[i] — b[i], we are sure every number can contribute to A or B, so we need to traverse every edge exactly once and everytime we enter through the edge give the first end point to A, and second end point to B, and to make euler tour possible, we need every degree even, which can be automatically handled by adding extra edges with 0.
324547251
About problem B: What if instead of two initial rectangles there were three or more rectangles and we are required to test if we can fill the grid with axb rectangles does anybody have insights or resources for a similar problem
The tutorial shows that if there are two rectangles with either
(x2 - x1) mod a != 0or(y2 - y1) mod b != 0, then the pattern is determined uniquely.So if we have a set of placed rectangles
{R1, ..., Rm}we either have two Ri, Rj with(xi - xj) mod a != 0or(yi - yj) mod b != 0and they uniquely determine the tiling (then we need to check that all other rectangles fit to this pattern).Or second case all
(xi - xj) mod a = 0and(yi - yj) mod b = 0then we can trivially tile everything by shifts of any of the rectangles by vectors(m*a, n*b), m,n are integral