Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### rng_58's blog

By rng_58, history, 9 months ago, ,

E: I assumed that the answer is either at most N or infinity. Why is this true?

G: Is there a solution that doesn't require reading papers (or at least reading the wikipedia article mentioned in the statement)? I heard that there's a paper that describes the solution.

•
• +38
•

 » 9 months ago, # |   +7 E: Because if rank doesn't drop at some point it never drops again. This is true because if im(Ak) = im(Ak + 1) then this image stabilizes. Moreover I was convinced that all this task is about is how to sped it up from obvious to tricky O(n3) by taking random vector and computing Ak v, was disappointed.
•  » » 9 months ago, # ^ |   +10 Can you please explain a bit more how to make this speed up?
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +10 I already more or less described it. You take random vector v and compute Av, A2v, A3v, ..., Anv and output smallest k such that Akv = 0 or Infinity if Anv ≠ 0
•  » » » » 9 months ago, # ^ |   +5 Okay, thank you, now I understand your approach
•  » » 9 months ago, # ^ |   0 We were able to get accepted by simply optimizing the O(n^3 log n) approach.
•  » » » 9 months ago, # ^ |   +10 Yes, that was what I was talking about, that was actually passing quite easily.
•  » » 9 months ago, # ^ |   0 What is the proof for "image stabilizes" fact? Specially, when we are working in mod prime?
•  » » » 9 months ago, # ^ | ← Rev. 3 →   +10 It's due to the fact, that im(Ak) is a subset of im(Ak - 1). So if im(Ak) = im(Ak - 1), than for each v in im(Ak) there is an u such that Au = v and u is in im(Ak - 1) = im(Ak). And this means, that v is in im(Ak + 1) too. So im(Ak + 1) is a subset of im(Ak). QED.
•  » » » » 9 months ago, # ^ |   0 Yes, that I get it. I mean, if C = A*B, then columns of C are linear combination of the columns of A. But I was wondering, why the modulo operation does not knock some vector off? I mean, why it's also true when doing modulo operation.
•  » » » » » 9 months ago, # ^ |   0 Well, i haven't used anything connected with the field I am working in. Everything I've said is also true in Zp
 » 9 months ago, # |   +10 Problem G can be solved in (if you assume, that arithmetic operations work in O(1)). You should use Adleman-Manders-Miller root extraction method (I don't see any difference between this method and Tonelli-Shanks). This article contains a good description of the algorithm. Additionally, you should modify their method, so that it has better complexity. In order to do that, you should use baby-step-giant-step instead of brute-force in the last part of the solution.I guess, that teams, who have solved this problem, knew Tonelli-Shanks before the contest or read the article in Wikipedia.Yes, it's not really a new problem, I'm sorry for that. But Tonelli-Shanks is actually pretty simple, and I want it to become more well-known.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +20 There is additional trick here. We can't use baby step giant step as a blackbox. We need to use fact that we know that our result will be small, so that even though it is modulo q, it works in (because p is upper bound on result we are searching for in this moment) instead of usual (and we know p can be upper bounded by 109 because cases when are easy (this is where this comes from, because we can bound and then we solve BSGS in ))Btw, I don't think that Tonelli-Shanks is pretty simple xD
 » 9 months ago, # |   0 Does anynody have a rather clean approach that they’re proud of for problem Oddosort? Or at least something that could be written rather quickly?
•  » » 9 months ago, # ^ |   +10 Well, I think our is quite ok. It's quite easy to get a range that is non-decreasing. Let's do a big loop, inside which do following. In another Get next two such ranges, and merge them. If one left, to nothing with it. If only one left total we are already won. The only problem we had, is we wrote solution for <=, not <, and got problems with stability.
•  » » » 9 months ago, # ^ |   0 That solution is O(n2) on decreasing arrays, isn’t it?During the contest we thought that intended solution was O(nlog(n)), so we implemented a variation of merge sort. It’s pretty embarassing if O(n2) fits no problem.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   +25 No, it's not. You probably understand that we get first two blocks, but we are scanning array and merge 1 and 2 block, 3 and 4-th, and etc. This works nlogn, because number of blocks is divided by two every time. codeloop { if head == nil { break } else { } if ans_head == nil { } else { break } prev = nil ptr = head loop { first = ptr if first == nil { break } else { } loop { prev_ptr = ptr ptr = ptr #next if ptr == nil { break } else { } if ptr #value < prev_ptr #value { break } else { } } prev_ptr #next = nil second = ptr if second == nil { if prev == nil { ans_head = head break } else { prev #next = first break } } else { } loop { prev_ptr = ptr ptr = ptr #next if ptr == nil { break } else { } if ptr #value < prev_ptr #value { break } else { } } prev_ptr #next = nil if second #value < first #value { new_ptr = second second = second #next } else { new_ptr = first first = first #next } if prev == nil { head = new_ptr } else { prev #next = new_ptr } loop { if first == nil { if second == nil { break } else { new_ptr #next = second new_ptr = second second = second #next } } else { if second == nil { new_ptr #next = first new_ptr = first first = first #next } else { if second #value < first #value { new_ptr #next = second new_ptr = second second = second #next } else { new_ptr #next = first new_ptr = first first = first #next } } } } prev = new_ptr } } 
•  » » » » 9 months ago, # ^ |   +13 It's the official solution. I wrote a program in C++ first and then used some sed scripts to convert it to Meow++ (removing brackets, comments, debug function calls, etc). That allowed me to debug conveniently using all standard tools.
•  » » 9 months ago, # ^ |   +33 You can do a mergesort. There are only 18 levels of recursion which can be emulated by 18 (identical except for variables) nested loops.
 » 9 months ago, # |   +5 How to solve A?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Let's consider the image on a 2D plane. Now assuming that upper right corner is on (2^k, 2^k) and lower left corner is on (0, 0). We can do recursion to assign coordinate to each square. It would be like this:go(x1, y1, x2, y2):int x;cin >> x;if x == 1:squares.add({ x1, y1, x2, y2 });if x == 2:go(x1, (y1 + y2) / 2, (x1 + x2) / 2, y2);go((x1 + x2) / 2, (y1 + y2) / 2, x2, y2);go(...);go(...);Now we can iterate over the squares and check whether it connected with some previous squares or not. So we have a graph and there we need to find the number of connected components (we can use DSU instead of storing whole graph in memory).But the problem is that 2^k is really large to store this number in a long long variable. We can create struct to store coordinates is a binary representation (storing only powers).https://ideone.com/7ZgrFU
•  » » » 9 months ago, # ^ |   +5 O(n3)?
•  » » » » 9 months ago, # ^ |   0 I wasn't able to come up with faster approach. I guess it can be proved that it works in O(n2) time.
•  » » 9 months ago, # ^ | ← Rev. 6 →   +15 We solved it differently: For every square store 8 pointers (4 for squares inside), and 4 for adjacent squares that are bigger. We can maintain this data just by doing dfs/bfs + using dsu for simplicity. It is O(n). Code:/*** 2 0 2 0 1 1 0 2 0 1 0 1 1 ***/ #include using namespace std; typedef long long ll; typedef long double ld; int num = 0; bool ok[20000]; struct DSU { int sz[20000]; int pa[20000]; DSU() { for (int i = 0; i < 20000; i++) { sz[i] = 1; pa[i] = i; } } int root(int a) { if (a == pa[a]) return a; return pa[a] = root(pa[a]); } void merge(int a, int b) { if (a == -1 || b == -1) return; a = root(a); b = root(b); if (a == b) return; if (sz[a] > sz[b]) swap(a, b); sz[b] += sz[a]; pa[a] = b; } }; DSU dsu; struct Square { int id; int x; Square *a = NULL, *b = NULL, *c = NULL, *d = NULL; Square *x_ = NULL, *y_ = NULL, *z_ = NULL, *t_ = NULL; Square() { id = num++; cin >> x; if (x == 2) { a = new Square(); b = new Square(); c = new Square(); d = new Square(); b->x_ = a; c->x_ = d; c->y_ = b; d->y_ = a; a->z_ = b; d->z_ = c; a->t_ = d; b->t_ = c; } if (x == 1) { ok[id] = true; } } void fix() { if (x == 2) { { d->t_ = t_; if (t_ != NULL && t_->x == 2) { d->t_ = t_->a; } d->x_ = x_; if (x_ != NULL && x_->x == 2) { d->x_ = x_->c; } } { c->t_ = t_; if (t_ != NULL && t_->x == 2) { c->t_ = t_->b; } c->z_ = z_; if (z_ != NULL && z_->x == 2) { c->z_ = z_->d; } } { b->z_ = z_; if (z_ != NULL && z_->x == 2) { b->z_ = z_->a; } b->y_ = y_; if (y_ != NULL && y_->x == 2) { b->y_ = y_->c; } } { a->y_ = y_; if (y_ != NULL && y_->x == 2) { a->y_ = y_->d; } a->x_ = x_; if (x_ != NULL && x_->x == 2) { a->x_ = x_->b; } } a->fix(); b->fix(); c->fix(); d->fix(); } if (x == 1) { ok[id] = true; } } void answer() { if (x == 2) { a->answer(); b->answer(); c->answer(); d->answer(); } if (x == 1) { if (x_) { if (x_->x == 1) dsu.merge(id, x_->id); } if (y_) { if (y_->x == 1) dsu.merge(id, y_->id); } if (z_) { if (z_->x == 1) dsu.merge(id, z_->id); } if (t_) { if (t_->x == 1) dsu.merge(id, t_->id); } } } }; int main() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); Square A = Square(); A.fix(); A.answer(); int ans = 0; for (int i = 0; i < 20000; i++) if (ok[i] && dsu.root(i) == i) ans++; cout << ans << "\n"; } 
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +10 Can be done with the same idea even without DFS/BFS — just merge neighbouring black blocks with DSU. Here is the code#define rep(i, from, to) for (int i = from; i < int(to); i++) const int MAXN = 15001; int p[MAXN]; int find(int a) { return (a == p[a]) ? a : p[a] = find(p[a]); } void unite(int a, int b) { if (a == b) return; a = find(a); b = find(b); if (rand() & 1) swap(a, b); p[b] = a; } void make(int a) { p[a] = a; } struct Node { int color, id; Node* next[4]; }; Node nodes[MAXN]; vi v; int vtop = 0, idtop = 0; void merge(Node* l, Node* r, bool horizontal) { if (l->color == 0 || r->color == 0) return; if (l->color == 1 && r->color == 1) { unite(l->id, r->id); return; } if (horizontal) { if (l->color == 1) { merge(l, r->next[0], horizontal); merge(l, r->next[3], horizontal); } else if (r->color == 1) { merge(l->next[1], r, horizontal); merge(l->next[2], r, horizontal); } else { merge(l->next[1], r->next[0], horizontal); merge(l->next[2], r->next[3], horizontal); } } else { if (l->color == 1) { merge(l, r->next[0], horizontal); merge(l, r->next[1], horizontal); } else if (r->color == 1) { merge(l->next[3], r, horizontal); merge(l->next[2], r, horizontal); } else { merge(l->next[3], r->next[0], horizontal); merge(l->next[2], r->next[1], horizontal); } } } Node* read() { Node *node = &nodes[vtop]; node->color = v[vtop++]; if (node->color == 1) { make(idtop); node->id = idtop++; } if (node->color <= 1) return node; rep(i, 0, 4) node->next[i] = read(); merge(node->next[0], node->next[1], true); merge(node->next[3], node->next[2], true); merge(node->next[0], node->next[3], false); merge(node->next[1], node->next[2], false); return node; } void solve() { int x; while (cin >> x) v.pb(x); read(); int cnt = 0; rep(i, 0, idtop) cnt += p[i] == i; cout << cnt; } 
 » 9 months ago, # |   +5 Was B just accurate brute-force with backtracking?
•  » » 9 months ago, # ^ |   +20 Backtracking was one possibility, you could also for every triplet of pieces (with order) and all their rotations, reflections and displacements try to create a corner, compute the border of the corner and check whether there is a matching corner from the other three pieces.
•  » » » 9 months ago, # ^ |   +5 Meet-in-the-middle! Smart, thanks!