### chokudai's blog

By chokudai, history, 5 weeks ago,

We will hold AtCoder Beginner Contest 218.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

• +117

 » 5 weeks ago, # |   0 Good luck to everybody!
 » 5 weeks ago, # |   +4 Hi chokudai I am interested in setting up the user editorials , if I can (ooops!!). How can I ?
•  » » 5 weeks ago, # ^ |   +17 People with atcoder rating of greater than or equal to 2000 see the "New Editorial" button on ABC's editorial page. Clicking on it opens a page to publish user editorials.
 » 5 weeks ago, # |   +12 My parents would rather let me participate in AtCoder contests than let me participate in Codeforces rounds, but they allow me to participate in both kinds of contests. Imagine you're in UTC+8 and then you can figure it out ;)
 » 5 weeks ago, # |   0 Nice problemset, any hints on problem H?
•  » » 5 weeks ago, # ^ |   0 How to solve G?
•  » » » 5 weeks ago, # ^ |   0 Do dfs traversal over the tree, now you need to keep track of the median for the entire path you're in, which can be done in several ways, i used ordered sets. Supose you want to know the best posible score for a node X, if depth of node X is even, is your oponent turn, so he will get you to the lowest possible outcome, otherwise is your turn, so you maximize it, run a top-down dp and print the value for node 1.
•  » » » » 5 weeks ago, # ^ |   +3 Doesn't that give you TLE? (Ordered set for every node)
•  » » » » » 5 weeks ago, # ^ |   0 Keep a global set, in which you only keep elements contained in the path from node $1$ to node $X$, to mantain this, you can add elements when you enter a node, and delete them just before you exit it.
•  » » » 5 weeks ago, # ^ |   0 I skipped the contest this week to prep (w/ sleep) for hacker cup round 1. I'm getting around to solving these now.As I have primarily been using python for these (although might switch to Go once I've finished building up a reasonable library), multiset wasn't available, and I didn't think to use a Fenwick tree. I'm solving it with 4 heaps. It is a bit slow (near 1.0s), but it does the job. (2 heaps for left and right insertions, and 2 heaps for left/removals) and just do the bookkeeping to cancel out the addition/removal heaps when the heads of each match).
•  » » 5 weeks ago, # ^ |   0 The problem statement is equivalent to placing $min(R,B)$ 2x1-Dominoes on $A$ and adding the covered $A_i$ s. But that's as far as I could get...
•  » » » 5 weeks ago, # ^ |   0 Does this cover the case when you do something like $AAB$?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 There is no need to do $AAB$ because you could do $ABA$ and get more points. $AAB$ would be the equivalent of placing the Domino on $A_{N-1}$ and the non existent $A_{N}$.
 » 5 weeks ago, # |   +32 To be honest, I don't think the difficulty C of this contest is suitable for the difficulty of ABC's usual problem C. Otherwise, a lot of people, including me, won't do D first or even other later problems before doing C. At least for me, the implementation difficulty of D is simpler than that of C :(
•  » » 5 weeks ago, # ^ |   0 I am so depressed with a C ... It made me feel incompetent :(
•  » » » 5 weeks ago, # ^ |   0 It's a thing that's popular on AtCoder (geometrical transformations), I usually get very mad when I see them, but they occur every once in a while. It's just about simulating rotations 4 times and writing a check function with the restricted canvas, but that in itself gets very implementation heavy and ugly. There's probably a better way to solve it, but this is how I usually get AC withing ~100 lines of code.
•  » » » » 5 weeks ago, # ^ |   0 Actually, I got AC with an about 40 lines and only 1.44kb code. Click to see the codenamespace Solution { const int N = 207; int n, cnt1, cnt2; char a[N][N], b[N][N], a1[N][N], a2[N][N], a3[N][N]; struct dist {int x, y;}dis[N * N]; struct node {int x, y;}p[2][N * N]; ib solve(char t1[N][N], char t2[N][N]) { F(int, i, 1, cnt1) p[0][i] = (node){0, 0}; F(int, i, 1, cnt2) p[1][i] = (node){0, 0}; F(int, i, 1, max(cnt1, cnt2)) dis[i] = (dist){0, 0}; cnt1 = cnt2 = 0; F(int, i, 1, n) F(int, j, 1, n) { if(t1[i][j] == '#') p[0][++cnt1] = (node){i, j}; if(t2[i][j] == '#') p[1][++cnt2] = (node){i, j}; } if(cnt1 != cnt2) return 0; F(int, i, 1, cnt1) dis[i] = (dist){p[0][i].x - p[1][i].x, p[0][i].y - p[1][i].y}; F(int, i, 2, cnt1) if(dis[i].x != dis[1].x || dis[i].y != dis[1].y) return 0; return 1; } iv Main() { read(n); F(int, i, 1, n) scanf("%s", a[i] + 1); F(int, i, 1, n) scanf("%s", b[i] + 1); int precnt1 = 0, precnt2 = 0; F(int, i, 1, n) F(int, j, 1, n) { if(a[i][j] == '#') precnt1++; if(b[i][j] == '#') precnt2++; } if(precnt1 != precnt2) return No, void(); F(int, i, 1, n) F(int, j, 1, n) a1[i][j] = a[n - j + 1][i]; F(int, i, 1, n) F(int, j, 1, n) a2[i][j] = a[j][n - i + 1]; F(int, i, 1, n) F(int, j, 1, n) a3[i][j] = a1[n - j + 1][i]; // F(int, i, 1, n) {F(int, j, 1, n) putchar(a3[i][j]); puts("");} if(solve(a, b) || solve(a1, b) || solve(a2, b) || solve(a3, b)) return Yes, void(); return No, void(); } } 
•  » » » » » 5 weeks ago, # ^ |   0 Thats a lot code for a C in abc.
•  » » » » » » 5 weeks ago, # ^ |   0 Expecting for a shorter solution then...
•  » » » » » » » 5 weeks ago, # ^ |   0 smol?#include "bits/stdc++.h" using namespace std; #define ll long long int #define pb(a) push_back(a) #define vll vector #define loop(i, n) for (ll i = 1; i <= n; i++) #define loop0(i, n) for (ll i = 0; i < n; i++) #define in(i) cin>>i #define out(i) printf("%lld", i) #define pll pair #define vpll vector> #define mp(i, j) make_pair(i, j) #define google cout << "Case #" << tc - t << ": "; const ll mod = 1000000007; const ll big = 2999999999999999999; const ll small = -2999999999999999999; void in2(ll &a, ll &b) { cin >> a >> b; } void in3(ll &a, ll &b, ll &c) {cin >> a >> b >> c; } void arrayIn(vll &a, ll &n) { loop0(i, n) in(a[i]); } void rotate90(vpll& a, ll n) { loop0(i, a.size()) { ll ty = a[i].second; a[i].second = a[i].first; a[i].first = -ty + n; } } void translate(vpll& a, ll xb, ll yb) { loop0(i, a.size()) { a[i].first -= xb; a[i].second -= yb; } } int main() { ll n; cin>>n; vpll s, t; char c; loop0(i, n) { loop0(j, n) { cin>>c; if(c == '#') s.push_back({i, j}); } } loop0(i, n) { loop0(j, n) { cin>>c; if(c == '#') t.push_back({i, j}); } } sort(s.begin(), s.end()); sort(t.begin(), t.end()); if(s == t) { cout<<"Yes\n"; return 0; } loop0(i, 4) { rotate90(t, n); sort(t.begin(), t.end()); translate(t, t[0].first - s[0].first, t[0].second-s[0].second); if (s == t) { cout << "Yes\n"; return 0; } } cout<<"No\n"; } 
•  » » » 5 weeks ago, # ^ |   -19 https://atcoder.jp/contests/abc218/submissions/25785347You can check easy implementation :)
•  » » » 5 weeks ago, # ^ |   0 Seems like it makes sense to have some code templates for 2D array rotation and maybe other simple transformations to avoid wasting extra time on problems like this. It's not the first problem of this kind.
•  » » 5 weeks ago, # ^ |   +1 For me G was easier than C , as it required a good amount of code and had much less points than C ( Unluckily I missed G as I had value of infinity as 998245353 rather than 10^9+7)
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   0 I think my answer is wrong for problem C, but It has been accepted.Those test cases are giving me : Yes. 3 . # . # . . . . . . . # # . . . . .  5 . . . . . . . . . . . . # . . . . # # # . . # . . . . . . . . . . . . . . . # # . . . # # . . . # . Am I wrong ?Most of the people in the first page of the standings are getting "Yes" you can check if you want : https://atcoder.jp/contests/abc218/submissions/25773980
•  » » » 5 weeks ago, # ^ |   0 Yeah, you are right, these cases must give a "No" Output. My Submissionchokudai Please look into this.
•  » » » » 5 weeks ago, # ^ |   0 I want to add something the test case has spaces in between.but even after fixing that like this : 3 .#. #.. ... ..# #.. ... I still get Yes.
•  » » » » » 5 weeks ago, # ^ |   0 The spaces wont matter as most people take the input character by character (including me).
•  » » » 5 weeks ago, # ^ |   0 My code output "No" for both the test cases. It seems that my approach is right :D
 » 5 weeks ago, # |   0 plz explain C,D
•  » » 5 weeks ago, # ^ |   0 check out the editorials
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +3 CFirst, let's check the figure in the two grids are equal or not. For both matrices do the following operations. Until the first row contains a '#' remove the first row Until the first column contains a '#' remove the first column Now for every i,j, matrix1[i][j] = '#' <=> matrix2[i][j] = '#' should satisfy if they are equal.Check this for every rotation of matrix1.
•  » » » 5 weeks ago, # ^ |   0 I implemented the same logic, but getting WA on one test case and the rest of the test cases have passed.SubmissionAre there any bugs in my implementation?
•  » » » » 5 weeks ago, # ^ |   0 yes, I also got WA on the same test case, you can check, for reference19AC1WA Submission20AC Submission
•  » » » » » 5 weeks ago, # ^ |   0 which type of test case failed first time ??
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Have you got it yet? I got the same one and still dont know where I made mistake
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 For C, First, if only 90 degree rotation is considered, there may be only 4 patterns s at most. Then consider the translation. It can be found that you only need to see which of the four patterns mentioned above can be translated to completely match t. Specifically, we list the positions of all characters # in S and T in sequence, and then compare them one by one. Let set pattern $S$ have a amount of $c_1$ #, the position of the $i$-th # is $(x_{0,i},y_{0,i})$; pattern $T$ have a amount of $c_2$ #, the position of the $i$-th # is $(x_{1,i},y_{1,i})$, and then we just need to find out whether the following conditions are met: $\forall i\in[2,n],x_{0,i}-x_{1,i}=x_{0,1}-x_{1,1}$ $\forall i\in[2,n],y_{0,i}-y_{1,i}=y_{0,1}-y_{1,1}$ $c_1=c_2$ Just follow this implemention. It may be a bit hard. Code(C++)namespace Solution { const int N = 207; int n, cnt1, cnt2; char a[N][N], b[N][N], a1[N][N], a2[N][N], a3[N][N]; struct dist {int x, y;}dis[N * N]; struct node {int x, y;}p[2][N * N]; ib solve(char t1[N][N], char t2[N][N]) { F(int, i, 1, cnt1) p[0][i] = (node){0, 0}; F(int, i, 1, cnt2) p[1][i] = (node){0, 0}; F(int, i, 1, max(cnt1, cnt2)) dis[i] = (dist){0, 0}; cnt1 = cnt2 = 0; F(int, i, 1, n) F(int, j, 1, n) { if(t1[i][j] == '#') p[0][++cnt1] = (node){i, j}; if(t2[i][j] == '#') p[1][++cnt2] = (node){i, j}; } if(cnt1 != cnt2) return 0; F(int, i, 1, cnt1) dis[i] = (dist){p[0][i].x - p[1][i].x, p[0][i].y - p[1][i].y}; F(int, i, 2, cnt1) if(dis[i].x != dis[1].x || dis[i].y != dis[1].y) return 0; return 1; } iv Main() { read(n); F(int, i, 1, n) scanf("%s", a[i] + 1); F(int, i, 1, n) scanf("%s", b[i] + 1); int precnt1 = 0, precnt2 = 0; F(int, i, 1, n) F(int, j, 1, n) { if(a[i][j] == '#') precnt1++; if(b[i][j] == '#') precnt2++; } if(precnt1 != precnt2) return No, void(); F(int, i, 1, n) F(int, j, 1, n) a1[i][j] = a[n - j + 1][i]; F(int, i, 1, n) F(int, j, 1, n) a2[i][j] = a[j][n - i + 1]; F(int, i, 1, n) F(int, j, 1, n) a3[i][j] = a1[n - j + 1][i]; // F(int, i, 1, n) {F(int, j, 1, n) putchar(a3[i][j]); puts("");} if(solve(a, b) || solve(a1, b) || solve(a2, b) || solve(a3, b)) return Yes, void(); return No, void(); } }  For D, we only need to enumerate two points, not four. Let the two points we enumerated be $i$ and $j$, and then you just need to see whether the two points $(x_i, y_j)$ and $(x_j,y_i)$ exist. Be careful not to repeat the enumeration. Code(C++)namespace Solution { int n, ans, in[2007]; struct node {int x, y;}a[2007]; map vis; map > , int> v2; iv Main() { read(n); F(int, i, 1, n) read(a[i].x, a[i].y), vis[mp(a[i].x, a[i].y)] = i; F(int, i, 1, n) F(int, j, i + 1, n) { int id1 = vis[mp(a[i].x, a[i].y)], id2 = vis[mp(a[j].x, a[j].y)], id3 = vis[mp(a[i].x, a[j].y)], id4 = vis[mp(a[j].x, a[i].y)]; if(id1 && id2 && id3 && id4 && !(!(id1 ^ id2) || !(id1 ^ id3) || !(id1 ^ id4) || !(id2 ^ id3) || !(id2 ^ id4) || !(id3 ^ id4))) { int id[5] = {0, id1, id2, id3, id4}; sort(id + 1, id + 5); if(!v2[mp(id[1], mp(id[2], mp(id[3], id[4])))]) ans++, v2[mp(id[1], mp(id[2], mp(id[3], id[4])))] = 1; } } write(ans); return; } } 
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 You could use a hashmap for D,(checking whether it is possible to form a rectangle with every pair of points). That would be a slightly clean implementation.
•  » » » » 5 weeks ago, # ^ |   0 Yeah I know my implemention is not that simple :(
 » 5 weeks ago, # |   +10 I assumed that alien trick is applicable in H and it worked lol.
 » 5 weeks ago, # | ← Rev. 3 →   0 In problem E — Destruction, I got 13 tc passed and 10 wrong, can you please help me with what's wrong with my code. (When I submit, I assumed it will give me TLE) Codeimport sys from heapq import heappush, heappop, heapify from math import ceil from collections import defaultdict, deque def get_ints(): return map(int, sys.stdin.readline().strip().split()) def get_array(): return list(get_ints()) def input(): return sys.stdin.readline().strip() n, m = get_ints() graph = defaultdict(list) Arr = [] ans = 0 for i in range(m): a, b, c = get_ints() if a == b: if c >= 0: ans += c else: graph[a].append(b) graph[b].append(a) Arr.append((c, a, b)) Arr.sort(reverse = True) for i in range(len(Arr)): c, a, b = Arr[i][0], Arr[i][1], Arr[i][2] if c <= 0: continue if len(graph[a]) > 1 and len(graph[b]) > 1: ans += c graph[a].remove(b) graph[b].remove(a) print(ans) 
•  » » 5 weeks ago, # ^ |   +1 Just find the minimum spanning tree for E(be careful while dealing with loops and multiple edges), your answer will be $max(0,total\ cost-cost\ of\ MST)$.
•  » » 5 weeks ago, # ^ |   +3 I got 4 penalty's because I removed all edges even those which had negative weight. I guess that's your error too. Sort edges in non-decreasing order of weights and form a graph. If the edge forms a cycle and doesn't have weight <= 0, remove it, else add to the graph. Final answer is (Total sum of edge weights — sum of weights of included edges of graph).Submission
 » 5 weeks ago, # |   0 Is F brute force?
•  » » 5 weeks ago, # ^ |   0 Kinda, you can bruteforce all edges inside the shortest path (at most $N-1$), for all other edges the answer remains the same.
•  » » 5 weeks ago, # ^ |   +4 Yeah, it's kinda brute force. SpoilerYou should only calculate the answer for the edges which are in the shortest path (fix some path) between 1 and n.
•  » » » 5 weeks ago, # ^ |   0 Thanks got it!
•  » » » 5 weeks ago, # ^ |   0 Oh, silly me! I didn't think of such a way in the game!
 » 5 weeks ago, # |   0 C was the hardest for me :_:
 » 5 weeks ago, # | ← Rev. 2 →   0 I use "divide and conquer" + "max,add convolution " to solve H. Bug why the answer is convex QwQ?
•  » » 5 weeks ago, # ^ |   +17 ngl most of the in-contest solvers who use convexity often rely on proof by AC :P
•  » » 5 weeks ago, # ^ |   +10 I saw submissions using priority queue also where they are greedily converting to red which gives maximum profit. Btw can you please elaborate your solution. Thanks
•  » » » 5 weeks ago, # ^ |   +16 dp[l][r][x][cl][cr] means considering the range from l to r , you use x red ,cl,cr is the color of two endpoints .You can speed it up use divide and conquer . Now you only need to solve the following problem in O(n):Given A,B,(A,B is convex ),find C. Where $C[i]=\max_{x+y=i} (A[x]+B[y])$you can find the implement in my code :
•  » » 5 weeks ago, # ^ |   +8 I always thought that it is impossible to make $(max, +)$ convolution faster than $O(n \sqrt{n} )$. What is the complexity of your solution?
•  » » » 5 weeks ago, # ^ |   +8 O(n log n).
•  » » » » 5 weeks ago, # ^ |   +8 Oh, so you are using convexity of the arrays to make $(max, +)$ convolution faster. That's interesting, thanks!If someone is interested: here you can find more about this problem.
 » 5 weeks ago, # | ← Rev. 3 →   +11 I'm pretty sure that once upon a time I've seen the problem like today's F with a weighted graph and $N, M \leq 2 \cdot 10^5$. Does anyone remember a similar problem and has a link to it? I think that it was at Hackerrank, but not sure.UPD: It's basically this problem. Thanks to this solution from AtCoder :)
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 True , I too think I have seen something very similar to this somewhere.
•  » » 5 weeks ago, # ^ |   0 Do you know how to solve the question for your constraints ($N, M \le 2 \cdot 10^5$)?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +13 I do! Let's take any shortest path $P = ( e_1, \dots, e_k )$ between $s$ and $t$. Obviously, we already know the solution for the edges not in $P$. Now, for every $i$ we want to omit the edge $e_i$ in the shortest possible way. Let's take a moment to think what does it actually mean "to omit" $e_i = (v_1, u_1)$. It means that there should exist another edge $e = (v_2, u_2)$ such that $d(s, v_2) \leq d(s, v_1)$ and $d(s, v_2) + len(e) > d(s, v_1)$. Between all such edges we want to find one that minimizes $d(s, v_2) + len(e) + d(u_2, t)$. We can calculate the distances from $s$ and to $t$ at the beginning of the algorithm and create a sweep-line-like algorithm which will be solving the problem for all edges $e_i$ one by one by maintaining all the "good" edges $e$ at a given moment in time. We can do that with a segment tree (probably, an ordinary set is enough but I didn't bother much). The final complexity would be $O ((N + M) \log N)$.My explanation is probably horrible, so I implemented the solution. Enjoy!
•  » » 5 weeks ago, # ^ |   +8 LinkI solved this problem few days back. I copied my code to find the edges that will always be in the shortest path.
•  » » » 5 weeks ago, # ^ |   0 Thanks! Although your problem is similar and uses a lot of related ideas, I don't really see how it implies the today's F. How do you proceed after you found the edges that always are in a shortest path?
•  » » » » 5 weeks ago, # ^ |   0 There can be atmost n-1 such edges. For each such edge, I ran a bfs from 1 and didn't use that edge. The shortest distance of n (if n is reachable) will be the answer for that edge.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 Yes, but this gives us $O(N + M)$ per edge, so the total complexity is $O(N \cdot (N + M) )$, right?UPD: I probably misread your comment and thought that you used the linked problem to solve today's F. But I was wrong and you just used a part of the solution to identify the "critical" edges. If I understand you correctly, you could have used the edges in any shortest path and get the same complexity theoretically. Anyway, thanks for sharing your solution!
•  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Yes, actually I found ABC's F pretty much similar to this problem except one idea. So I shared it. But it seems you are looking for same problem with different constraints. So this problem isn't that relevant.
 » 5 weeks ago, # |   +8 en_translator is still working on translating today's editorial for H. Great thanks!
 » 5 weeks ago, # |   0 I am getting WA on C on only 2 cases. Can someone help me figure it out?. This is my code. I used coordinate compression on both the matrices and checked if both the compressed matrices were equal.Thanks ;)
 » 5 weeks ago, # |   0 Problem D is exactly same as this problem on Codechef.
•  » » 5 weeks ago, # ^ |   0 Well, the constraint in the CodeChef problem is N≤10⁵, which is 50 times as more as in Problem D. (+ input several testcases if you haven't)
 » 5 weeks ago, # |   0 problem E difficulty has gone down by a lot recently.
•  » » 5 weeks ago, # ^ |   0 Thats because the quantity of tasks has also increased i Guess..
 » 5 weeks ago, # | ← Rev. 4 →   0 Could anyone please point out where this solution for C fails.Thanks.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0
 » 5 weeks ago, # |   +10 I think my answer is wrong for problem C, but It has been accepted.Those test cases are giving me : Yes. 3 . # . # . . . . . . . # # . . . . .  5 . . . . . . . . . . . . # . . . . # # # . . # . . . . . . . . . . . . . . . # # . . . # # . . . # . Am I wrong ?
•  » » 5 weeks ago, # ^ |   0 i got No on both TC you mentioned
•  » » » 5 weeks ago, # ^ | ← Rev. 4 →   0 Most of the people in the first page of the standings are getting "Yes" you can check if you want :https://atcoder.jp/contests/abc218/standingsYou can check jiangly submission : https://atcoder.jp/contests/abc218/submissions/25773980
•  » » 5 weeks ago, # ^ |   0 I think it is because your test cases have spaces in between.The problem statement gives the inputs without spaces.If you remove the spaces so it looks like this, your problem should be solved: 3 .#. #.. ... ..# #.. ... 5 ..... ..... ..#.. ..### ..#.. ..... ..... ...## ...## ...#. 
•  » » » 5 weeks ago, # ^ |   0 Even after removing the spaces I get "Yes".Here is my submission if you want to check :https://atcoder.jp/contests/abc218/submissions/25776184
 » 5 weeks ago, # | ← Rev. 4 →   -13 I am getting AC on 19-TC and WA only on one TC (Case name — hand_04.txt) in problem C. either give me this TC from somewhere TT or please debug my code.
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   0 Sorry I tried to help !!
•  » » 5 weeks ago, # ^ |   0 You have a problem in this line :int diff=abs(s[0].first — t[0].first) + abs(s[0].second — t[0].second);test case : 3 # . . # . # . . . . # . . . . # . # you are getting Yes.
•  » » 5 weeks ago, # ^ |   0 I modified your code and here is the submission: https://atcoder.jp/contests/abc218/submissions/25796147Basically, need to change 2 things: 1. remove Abs() 2. Use diffx and diffy in parallel instead of diff.
•  » » » 5 weeks ago, # ^ |   0 Thanks, it worked! Also, just removing abs() worked. We don't need to divide diff into diffx and diffy.
 » 5 weeks ago, # | ← Rev. 4 →   0 Please, can somebody help with my solution for G. I did everthing as in the editorial but used ordered_set instead of multiset or BIT. I spent almost an hour trying to find problem, but I couldn't. UPD: I found problem. It was because erase in ordered_multiset doesn't work. So if you want to erase you need to erase using iterator of lower_bound, but I forgot that in ordered_multiset the lower_bound and upper_bound functions are swapped.
•  » » 5 weeks ago, # ^ |   +3 Thanks for the info , I was also having the same error but as I was unable to figure out the reason I switched code from Multiset to set of pair.
 » 5 weeks ago, # |   0 Why checking rotation only is not sufficient in problem C?
•  » » 5 weeks ago, # ^ |   0 Because, according to the problem statement, the shapes can be matched by rotations and translations.
•  » » 5 weeks ago, # ^ |   0 never mind :))
 » 5 weeks ago, # |   0 Here is a way to solve problems C and D on ABC 218. Problem C can be solved as a geometry problem, where you basically: find the figures' outline boxes, rotate the first figure's box, compare the resulting boxes for all rotations. Here is my submission for C with neat organization & comments. Problem D can be solved by using DFS to find the four points. for every point, store all points that have the same X in one vector, same Y in another vector, use DFS on every point to find the next point with the same X or Y (alternating between finding X or Y), make sure the four points we find aren't repeated by: finding the same X for the first point, making sure the X and Y coordinates are increasing for the first 3 points (left-top, left-bottom, right-bottom). My submission for D using DFS.
 » 3 weeks ago, # |   0 I tried something out for C Attached the approach here: https://atcoder.jp/contests/abc218/submissions/26074628