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

### atcoder_official's blog

By atcoder_official, history, 3 months ago,

We will hold AtCoder Beginner Contest 351.

We are looking forward to your participation!

• +52

 » 3 months ago, # |   0 GLHF!
 » 3 months ago, # | ← Rev. 2 →   0 why are the scoring distribution not uniform in ABC's? just a question. By uniform I meant that they vary from contest to contest.
•  » » 3 months ago, # ^ |   +6 I think they are based on the relative difficulty of each problem.
 » 3 months ago, # |   0 GLHF!
•  » » 3 months ago, # ^ |   +3 AC F,but I do not know how to solve E.
•  » » » 3 months ago, # ^ |   0 +1
•  » » » » 3 months ago, # ^ |   +3 I only spend 20min to solve F,but E is difficult.
•  » » » » » 3 months ago, # ^ |   0 Even I only spent 10 mins to solve F.
•  » » » » » » 3 months ago, # ^ |   0 It is apparent that F is BIT.
•  » » » » » » » 3 months ago, # ^ |   0 True.
 » 3 months ago, # |   0 I wish I could AC the first five questions.
•  » » 3 months ago, # ^ |   +6 Are you a primary school student?You're awesome.
•  » » » 3 months ago, # ^ |   +3 Me too. I wish to solve 6 problems
•  » » » » 3 months ago, # ^ |   0 and you did it!
•  » » » » » 3 months ago, # ^ |   +3 How G(((
•  » » » » » » 3 months ago, # ^ |   0 Please tell me how to solve e,orzzzzzzzzz.
•  » » » » » » » 3 months ago, # ^ |   0 Distance from Chebyshev to Manhattan
•  » » 3 months ago, # ^ |   0 Hope to solve 6 problems.
 » 3 months ago, # |   0 is easy?
 » 3 months ago, # |   0 GLHF!
 » 3 months ago, # | ← Rev. 3 →   -7 Problem C was sh*t
•  » » 4 weeks ago, # ^ |   0 No you are wrong ABC359C is worse than ABC351C as a C
 » 3 months ago, # |   0 is there any possibility to solve F using Dynamic segment tree ??
•  » » 3 months ago, # ^ |   0
 » 3 months ago, # |   +34 I might be the unluckiest man ever to get 6 second places in all ABCs while never getting the first place :( Why are these Japanese so fast :cry:
 » 3 months ago, # |   -30 D gave tle please can anybody suggest bool isValid(int nrow, int ncol, int m, int n) { return (nrow >= 0 && ncol >= 0 && nrow < m && ncol < n); } bool funCheckHash(vector>&grid, int r, int c) { int delrow[4] = { -1, 0, 1, 0}; int delcol[4] = {0, 1, 0, -1}; int m = grid.size(); int n = grid[0].size(); for (int i = 0; i < 4; i++) { int nrow = r + delrow[i]; int ncol = c + delcol[i]; if (isValid(nrow, ncol, m, n) && grid[nrow][ncol] == '#')return true; } return false; } int bfs(int r, int c, vector>&grid) { int m = grid.size(); int n = grid[0].size(); int ans = 0; queue>q; vector>vis(m, vector(n, 0)); vis[r][c] = 1; q.push({r, c}); int delrow[4] = { -1, 0, 1, 0}; int delcol[4] = {0, 1, 0, -1}; while (!q.empty()) { auto node = q.front(); int r = node.first; int c = node.second; q.pop(); ans += 1; for (int i = 0; i < 4; i++) { int nrow = r + delrow[i]; int ncol = c + delcol[i]; if (isValid(nrow, ncol, m, n) && !vis[nrow][ncol] && grid[nrow][ncol] == '.' && !funCheckHash(grid, nrow, ncol)) { q.push({nrow, ncol}); vis[nrow][ncol] = 1; } else if (isValid(nrow, ncol, m, n) && !vis[nrow][ncol] && grid[nrow][ncol] == '.' && funCheckHash(grid, nrow, ncol)) { ans += 1; vis[nrow][ncol] = 1; } } } return ans; } void solve() { int m, n; cin >> m >> n; vector>grid(m, vector(n, 'X')); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> grid[i][j]; } } int ans = 1; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '.' && !funCheckHash(grid, i, j)) { ans = max(ans, bfs(i, j, grid)); } } } cout << ans << " "; return; } 
 » 3 months ago, # |   0 getting WA on 16 testcases for problem D, any clue what edge cases i am missing,https://atcoder.jp/contests/abc351/submissions/52879952
•  » » 3 months ago, # ^ |   0 I guess this is the issue: fields next to magnets can (and sometimes should) be visited multiple times from different directions, so you have to either not mark them as visited, or clean them up after every traversal.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Why? Can you please explain? Edit : Got it, a magnet adjacent cell can be an element of more than one connected component sets. Hence we need to unmark all the magnet adjacent cells or atleast have a set of pairs where we can store the magnet adjacent cells.
•  » » » 3 months ago, # ^ |   -8 why some test cases are failing since i did the correct way to solve this problem.int r[4] = { -1 , 0 , 1 , 0}; int c[4] = {0 , 1 , 0 , -1}; int cnt1 = 0; int cnt2 = 0; set> v; void solve(int i , int j , vector&arr, int n, int m, vector&vis) { if ((arr[i][j] == '@')) { if (v.find({i , j}) == v.end()) { v.insert({i, j}); cnt1++; } return; } vis[i][j] = 1; cnt2++; // bug(i , j); for (int a = 0; a < 4; a++) { int nrow = i + r[a]; int ncol = j + c[a]; if (nrow >= 0 and nrow < n and ncol >= 0 and ncol < m and vis[nrow][ncol] == 0 and arr[nrow][ncol] != '#') { solve(nrow, ncol, arr, n, m, vis); } }} void solveit() { int n, m; cin >> n >> m; vector arr; for (int i = 0; i < n; i++) { string s; cin >> s; arr.push_back(s); } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (arr[i][j] == '#') { if (i > 0) { arr[i - 1][j] = '@'; } if (i < n - 1) { arr[i + 1][j] = '@'; } if (j > 0) { arr[i][j - 1] = '@'; } if (j < m - 1) { arr[i][j + 1] = '@'; } } } } // bug(n, m); // int get = solve(1,2,arr,n,m,vis); int ans = 0; // print2d(vis); // bug(get); vector> vis(n , vector(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (arr[i][j] == '.' and vis[i][j] == 0) { cnt1 = 0; cnt2 = 0; solve(i , j , arr, n, m, vis); ans = max(ans , cnt1 + cnt2); // bug(cnt1,cnt2); // bug(v.size()); v.clear(); // cout<
•  » » » » 3 months ago, # ^ |   0 formatting code would increase your chances by 69% to get help
•  » » 3 months ago, # ^ |   0 Test case: 3 3 ..# ... #.. Answer is 5, your code gives 3.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 how did you fix this issue? I'm facing the same test case wrong as said in the comments. if i just return on fields next to magnet and never mark them visited I get 11 as answer on the first test case.Edit: I found a way to tackle the TLE which we get for unmarking all those cells. Just use a set and set.count() which is $O(log n)$ and then we can use set.clear() at the end of every dfs. Here's my submission
 » 3 months ago, # |   0 Well. ABC began to have Grid BFS again! I only remember that ABC stopped doing so several months ago. I'm bored with the similar BFS problems. The codes are long and difficult to debug.
 » 3 months ago, # | ← Rev. 2 →   0 I get RE in Python for problem D for 20 test cases (rest all are AC). Can someone please help what might be causing the error...To clarify my code a bit, I have created a visited grid which records which grid locations have been visited. In the grid, all magnets are marked '#' and all cells to left right below and above are marked 'x'. Then i run dfs for all unvisited cells, in process marking the visiting cell as visited. I never mark the 'x' grid cells as visited since they can be visited multiple times from different 'regions' of dfs, and maintained a dictionary (could have used set too) to maintain which 'x' marked cells have been visited in current dfs (so that they are not revisited).In every array access I have (I think) put in place a boundary check to make sure no index is out of range. Any help would be appreciated. Thank you.
•  » » 3 months ago, # ^ |   0 Python by default has recursion depth limited to 1000, so for large grids it gives a RecursionLimitError.To fix this add sys.setrecursionlimit(100000) to the beginning of your code.
•  » » » 3 months ago, # ^ |   0 Oh yes, that fixed the issue. Thank you very much. I had read about this issue but I guess I hadn't been much attentive then TT.
 » 3 months ago, # |   +3 Since no Editorial is available until now, it will be helpful if somebody can share their approach in $E$.
•  » » 3 months ago, # ^ |   0 I. Since the moves preserve the parity of x+y, I first split all points into two independent groups and add their results together at the end.II. For every group, the distance then is simply distance in 'maximum' metric ($max(|x_0-x_1|,|y_0-y_1|)$) (easy to see).III. To calculate the sum of distances, I first transform this metric from maximum into Manhattan, for which the solution is simple and quite well known: Spoiler$x, y \rightarrow x+y, x-y$ IV. Finally, we need to calculate sum of differences over both coordinates, which can be done separately by sorting and maintaining sum and count of previously added elements. V. The final distance has to be divided by 2, which is an artifact of the transformation from point III but also easy to see when running against samples.
•  » » » 3 months ago, # ^ |   0 As I understand, what you are saying means that, if we have $2$ points: ($x_1$, $y_1$) and ($x_2$, $y_2$)After transformation, they will be: ($x_1+y_1$, $x_1-y_1$) and ($x_2+y_2, x_2-y_2)$Where the Manhatten distance between the transformed points is equal to the actual distance between the original points:|$x_1+y_1-x_2-y_2|+|x_1-y_1-x_2+y_2$| = max(|$x_1-x_2|, |y_1-y_2|$)Can you please prove why this is true?
•  » » » » 3 months ago, # ^ |   0 You forgot the $\dots*2$ from point V in the equation, maybe that was the problem in proving it?If you still struggle while remembering about $*2$, try to use the general fact that $|t|+|u| = max(|t+u|,|t-u|)$, then set $t=x_0+y_0-x_1-y_1$, $u=x_0-y_0-x_1+y_1$, like you wrote out.But it's easier to just draw it to be honest. :)
•  » » » » » 3 months ago, # ^ |   0 Was not aware of this one:|t| + |u| = max(|t+u|, |t-u|)which is logical since it is just taking the max between the different sign combinations.It makes sense now, thank you!
•  » » » » 3 months ago, # ^ |   0 After letting a = x1-y1, b = x2-y2, you can simplify the expression by case-analysis 1) a >= b and 2) a < b to remove the absolute operator. In both cases, the LHS and RHS of your last equation satisfy LHS = 2*RHS
 » 3 months ago, # | ← Rev. 4 →   +64 There is a very simple solution for F (one without any data structures). SolutionLet $f:\mathbb{Z}^N\to \mathbb{Z}$ be defined as $\displaystyle f(A):=\sum_{1\leq i •  » » 3 months ago, # ^ | 0 Such a clever observation and idea!! •  » » 3 months ago, # ^ | 0 Neat. •  » » 3 months ago, # ^ | 0 how did you come up with this :$\sum_{1 \leq i < j \leq N} \max{{{A_j - A_i, 0}}} = \sum_{1 \leq i < j \leq N} \left( \frac{|A_j - A_i| + (A_j - A_i)}{2} \right) $•  » » » 3 months ago, # ^ | ← Rev. 3 → +3 If you realize that the$\max_{}:\mathbb{R}^2\to \mathbb{R}$and "distance"$|\cdot-\cdot|:\mathbb{R}^2\to \mathbb{R}$functions can be both computed by taking the cases on the maximum value then one might think that there could be a connection between the two. In fact there is the general formula$ \max_{} \{ a,b \}= \frac{|a-b|+(a+b)}{2}. $The formula might seem weird at first if you take the cases$ |a-b|=\left\{\begin{array}{ll} a-b,&a\geq b \\ b-a,& a < b \end{array}\right. $you can see how one could have come up with "the cancelation" trick in the formula. •  » » 3 months ago, # ^ | +11 A little easier: Write$\max(A_j - A_i, 0) = \max(A_j, A_i) - A_i$. Then, the sum can be written as$\displaystyle \sum_{i = 1}^{N} \sum_{j = i + 1}^{N} \max(A_j, A_i) - A_i = \sum_{i = 1}^{N} \sum_{j = i + 1}^{N} \max(A_j, A_i) - \sum_{i = 1}^{N} \sum_{j = i + 1}^{N} A_i,$where the second sum is just the sum of$(N - i) \cdot A_i$for all$1 \le i \le N$, and the first sum can be calculated using sorting (basically the same method as yours, but I think this is slightly more natural to think of). •  » » 3 months ago, # ^ | 0 So nice trick!  » 3 months ago, # | 0 I spend 1 min thinking the solution of F and 4 min for coding after the round. Oops. •  » » 3 months ago, # ^ | ← Rev. 2 → +14$D > > > F$•  » » » 3 months ago, # ^ | +3 maybe it's even easier than C. •  » » » » 3 months ago, # ^ | 0 what did you do to make it so quick? I haven't done it yet but I've thought of segtree solution with some help of a mentor. •  » » » » » 3 months ago, # ^ | 0 After you solved some problems using the similar trick, you'll be able to come up the idea faster too. But unfortunately CF problems aren't so obvious :(  » 3 months ago, # | 0 You can check out video editorials of C, D, E, F if you are stuck  » 3 months ago, # | +36 Can somebody explain their solution for problem G?  » 3 months ago, # | 0 How can I approach problem E?? •  » » 3 months ago, # ^ | 0 If you color the lattice points like a checkerboard pattern, note that the rabbit cannot switch colors. So we can split the points$(x, y)$depending on the parity of$x+y$and solve the problem independently for each. Since the rabbit jumps diagonally we can think of changing our coordinate system, let the "x-direction" be the vector$(1, 1)$and the "y-direction" be the vector$(-1, 1)$. This transformation turns the point$(x, y)$into$(\frac{x+y}{2}, \frac{y-x}{2})$and now the rabbit jumps one space horizontally or vertically. (Note: When dealing with the case where x+y is odd, you can shift the points one space in any direction to avoid fractions.) Now, how do we find the total manhattan distance between each pair of points? You can solve this independently for total x distance and the total y distance. For total x distance, sort the points by their x-coordinate and consider how many times each gap (in the x direction) between two points is added to the sum. It is the product of the number of points on the left and the number of points on the right. Do the same for y-coordinates. •  » » » 3 months ago, # ^ | 0 Thanks!  » 3 months ago, # | 0  » 3 months ago, # | 0 I did problem F using ordered set. I have one doubt how can fenwick tree be used to calculate the count of elements greater than a particular number? ( actually i'm trying to code after long time, some insight would really help!) •  » » 3 months ago, # ^ | 0 Something like this: (segtree is a segment tree with operation "sum") # Add an element x current_count = segtree.get(x) segtree.set(x, current_count + 1) # Find the count of elements less than x segtree.prod(0, x) Then subtract that from the total number of elements to find the count greater than or equal to x.(Note, in problem F you need to use coordinate compression otherwise the segment tree will be too large.) •  » » » 3 months ago, # ^ | 0 got it thanks, i knew this technique before just wanted some help, so what we do is co -ordinates compression since values can go upto 1e9 , but co-ordinate compression makes them limited to 1e5 () , after that we update the segment tree with value 1 at those points. Then we keep traversing again and updating the values with -1 to remove them, so the sum to [current_value, n] will give us the count of values greater than current_value.Thanks again, to remind me this technique again!! •  » » 3 months ago, # ^ | 0 You can use the Fencwick tree to store$\sum X_{j}\forallX_{j} > Y_{i}i \in [0, N-1]$and$j \in [i + 1, N-1]$. Then you can use the formula$\sum X_{j}$—$cnt(X_{j}>Y_{i})*Y_{i}$. This works because all the values$<=Y_{i}$will contribute a$0$to the answer. You can now reverse the array and do the operations for left side i.e for reversed array$j\in[0, i-1]$. Now counting elements$<=\$ some elements and finding their sum can be done using Fenwick Tree. You can coordinate compress the elements since storing them would give MLE but remember their original values. Now use compressed values to iterate in the Fenwick Tree and original values to store the sum in Fenwick Tree. Calculate all the values using the formula. Spoilercin >> n; vl a(n); rep(i, n) cin >> a[i]; map mp; int val = 1; vl b = a; sort(all(b)); rep(i, n) { if(mp[b[i]]) continue; mp[b[i]] = val++; } vpll p(n); rep(i,n)p[i]={mp[a[i]],i}; vl toka(n); rep(i, n) { toka[i] = a[i]; } debug(toka) debug(p) vpll q=p; vl cnt(n), sum(n); vl pref(n+1); rep(i,n)pref[i+1]=pref[i]+a[i]; auto g = [&](int l,int mid,int h)->void { int sz1 = mid-l+1, sz2=h-mid; vpll x,y; rep(i,sz1)x.pb(p[i+l]); rep(i,sz2)y.pb(p[i+mid+1]); int i=0,j=0,k=l; while(ivoid { if(l>=h)return; int m = l + h >> 1; f(l,m,f); f(m+1,h,f); g(l,m,h); }; f(0,n-1,f); ll res = 0; p = q; reverse(all(p)); reverse(all(toka)); rep(i, n) { int id; ll tot = 0; id = 4e5+1; while(id) { tot += Bit[id]; id-=(id&-id); } ll cur_sum = 0; id = p[i].fi; while(id) { cur_sum += Bit[id]; id-=(id&-id); } sum[p[i].se] = tot-cur_sum; id=p[i].fi; while(id<=4e5+1) { Bit[id]+=toka[i]; id+=(id&-id); } } rep(i, n) { res += sum[i]-cnt[i]*a[i]; } cout << res << nl; `
 » 3 months ago, # |   0 https://atcoder.jp/contests/abc351/submissions/52887433Can somebody tell why TLE in 4th?
•  » » 3 months ago, # ^ |   0 You're creating a new 'vis' vector for every dfs call try optimising that.
 » 3 months ago, # |   0 Good luck !
 » 3 months ago, # | ← Rev. 2 →   0 I think it's terribly bad to design the corner case of 0 in problem G.I just submitted the code at the last 2 minutes of the contests,and WA on the last 2 tasks.This was a terrible experience for me.
 » 3 months ago, # |   0 too many manhattan
 » 2 months ago, # | ← Rev. 2 →   0 How to solve F using 2 ordered multisets. thanks
•  » » 2 months ago, # ^ |   0 I think BIT is more easy to solve the problem.