### chokudai's blog

By chokudai, history, 7 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! Comments (89)
 » Good luck to everybody!
 » Hi chokudai I am interested in setting up the user editorials , if I can (ooops!!). How can I ?
•  » » 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.
 » 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 ;)
 » Nice problemset, any hints on problem H?
•  » » How to solve G?
•  » » » 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.
•  » » » » Doesn't that give you TLE? (Ordered set for every node)
•  » » » » » 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.
•  » » » 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).
•  » » 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...
•  » » » Does this cover the case when you do something like $AAB$?
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   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}$.
 » 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 :(
•  » » I am so depressed with a C ... It made me feel incompetent :(
•  » » » 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.
•  » » » » 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[N * N]; ib solve(char t1[N][N], char t2[N][N]) { F(int, i, 1, cnt1) p[i] = (node){0, 0}; F(int, i, 1, cnt2) p[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[++cnt1] = (node){i, j}; if(t2[i][j] == '#') p[++cnt2] = (node){i, j}; } if(cnt1 != cnt2) return 0; F(int, i, 1, cnt1) dis[i] = (dist){p[i].x - p[i].x, p[i].y - p[i].y}; F(int, i, 2, cnt1) if(dis[i].x != dis.x || dis[i].y != dis.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(); } } 
•  » » » » » Thats a lot code for a C in abc.
•  » » » » » » Expecting for a shorter solution then...
•  » » » » » » » 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.first - s.first, t.second-s.second); if (s == t) { cout << "Yes\n"; return 0; } } cout<<"No\n"; } 
•  » » » https://atcoder.jp/contests/abc218/submissions/25785347You can check easy implementation :)
•  » » » 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.
•  » » 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)
•  » » 7 weeks ago, # ^ | ← Rev. 5 →   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
•  » » » Yeah, you are right, these cases must give a "No" Output. My Submissionchokudai Please look into this.
•  » » » » I want to add something the test case has spaces in between.but even after fixing that like this : 3 .#. #.. ... ..# #.. ... I still get Yes.
•  » » » » » The spaces wont matter as most people take the input character by character (including me).
•  » » » My code output "No" for both the test cases. It seems that my approach is right :D
 » plz explain C,D
•  » » check out the editorials
•  » » 7 weeks ago, # ^ | ← Rev. 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.
•  » » » 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?
•  » » » » yes, I also got WA on the same test case, you can check, for reference19AC1WA Submission20AC Submission
•  » » » » » which type of test case failed first time ??
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   Have you got it yet? I got the same one and still dont know where I made mistake
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   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[N * N]; ib solve(char t1[N][N], char t2[N][N]) { F(int, i, 1, cnt1) p[i] = (node){0, 0}; F(int, i, 1, cnt2) p[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[++cnt1] = (node){i, j}; if(t2[i][j] == '#') p[++cnt2] = (node){i, j}; } if(cnt1 != cnt2) return 0; F(int, i, 1, cnt1) dis[i] = (dist){p[i].x - p[i].x, p[i].y - p[i].y}; F(int, i, 2, cnt1) if(dis[i].x != dis.x || dis[i].y != dis.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; struct node {int x, y;}a; 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 = {0, id1, id2, id3, id4}; sort(id + 1, id + 5); if(!v2[mp(id, mp(id, mp(id, id)))]) ans++, v2[mp(id, mp(id, mp(id, id)))] = 1; } } write(ans); return; } } 
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   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.
•  » » » » Yeah I know my implemention is not that simple :(
 » I assumed that alien trick is applicable in H and it worked lol.
 » 7 weeks ago, # | ← Rev. 3 →   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], Arr[i], Arr[i] 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) 
•  » » 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)$.
•  » » 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
 » Is F brute force?
•  » » Kinda, you can bruteforce all edges inside the shortest path (at most $N-1$), for all other edges the answer remains the same.
•  » » 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.
•  » » » Thanks got it!
•  » » » Oh, silly me! I didn't think of such a way in the game!
 » C was the hardest for me :_:
 » 7 weeks ago, # | ← Rev. 2 →   I use "divide and conquer" + "max,add convolution " to solve H. Bug why the answer is convex QwQ?
•  » » ngl most of the in-contest solvers who use convexity often rely on proof by AC :P
•  » » 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
•  » » » 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 :
•  » » I always thought that it is impossible to make $(max, +)$ convolution faster than $O(n \sqrt{n} )$. What is the complexity of your solution?
•  » » » O(n log n).
•  » » » » 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.
 » 7 weeks ago, # | ← Rev. 3 →   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 :)
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   True , I too think I have seen something very similar to this somewhere.
•  » » Do you know how to solve the question for your constraints ($N, M \le 2 \cdot 10^5$)?
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   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!
•  » » LinkI solved this problem few days back. I copied my code to find the edges that will always be in the shortest path.
•  » » » 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?
•  » » » » 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.
•  » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   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!
•  » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   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.
 » en_translator is still working on translating today's editorial for H. Great thanks!
 » 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 ;)
 » Problem D is exactly same as this problem on Codechef.
•  » » 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)
 » problem E difficulty has gone down by a lot recently.
•  » » Thats because the quantity of tasks has also increased i Guess..
 » 7 weeks ago, # | ← Rev. 4 →   Could anyone please point out where this solution for C fails.Thanks.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →
 » 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 ?
•  » » i got No on both TC you mentioned
•  » » » 7 weeks ago, # ^ | ← Rev. 4 →   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
•  » » 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 ..... ..... ..#.. ..### ..#.. ..... ..... ...## ...## ...#. 
•  » » » Even after removing the spaces I get "Yes".Here is my submission if you want to check :https://atcoder.jp/contests/abc218/submissions/25776184
 » 7 weeks ago, # | ← Rev. 4 →   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.
•  » » 7 weeks ago, # ^ | ← Rev. 4 →   Sorry I tried to help !!
•  » » You have a problem in this line :int diff=abs(s.first — t.first) + abs(s.second — t.second);test case : 3 # . . # . # . . . . # . . . . # . # you are getting Yes.
•  » » 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.
•  » » » Thanks, it worked! Also, just removing abs() worked. We don't need to divide diff into diffx and diffy.
 » 7 weeks ago, # | ← Rev. 4 →   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.
•  » » 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.
 » Why checking rotation only is not sufficient in problem C?
•  » » Because, according to the problem statement, the shapes can be matched by rotations and translations.
•  » » never mind :))
 » 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.
 » I tried something out for C Attached the approach here: https://atcoder.jp/contests/abc218/submissions/26074628