We will hold AtCoder Beginner Contest 351.

- Contest URL: https://atcoder.jp/contests/abc351
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240427T2100&p1=248
- Duration: 100 minutes
- Writer: Nyaan, math957963, MtSaka, nok0
- Tester: MtSaka, Aus21
- Rated range: ~ 1999
- The point values: 100-150-250-425-500-500-650

We are looking forward to your participation!

GLHF!

why are the scoring distribution not uniform in ABC's? just a question. By uniform I meant that they vary from contest to contest.

I think they are based on the relative difficulty of each problem.

GLHF!

AC F,but I do not know how to solve E.

+1

I only spend 20min to solve F,but E is difficult.

Even I only spent 10 mins to solve F.

It is apparent that F is BIT.

True.

I wish I could AC the first five questions.

Are you a primary school student?You're awesome.

Me too. I wish to solve 6 problems

and you did it!

How G(((

Please tell me how to solve e,orzzzzzzzzz.

Distance from Chebyshev to Manhattan

Hope to solve 6 problems.

is easy?

GLHF!

Problem C was sh*t

No you are wrong ABC359C is worse than ABC351C as a C

is there any possibility to solve F using Dynamic segment tree ??

Yes

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:

D gave tle please can anybody suggest

getting WA on 16 testcases for problem D, any clue what edge cases i am missing,

https://atcoder.jp/contests/abc351/submissions/52879952

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.

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.

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<pair<int, int>> v; void solve(int i , int j , vector&arr, int n, int m, vector<vector>&vis) { if ((arr[i][j] == '@')) { if (v.find({i , j}) == v.end()) {

} void solveit() {

}

formatting code would increase your chances by 69% to get help

Test case:

Answer is 5, your code gives 3.

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

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.

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.

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.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.

Since no Editorial is available until now, it will be helpful if somebody can share their approach in $$$E$$$.

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.

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?

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. :)

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!

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

There is a very simple solution for F (one without any data structures).

SolutionLet $$$f:\mathbb{Z}^N\to \mathbb{Z}$$$ be defined as

then

where

so we can compute $$$f(A)$$$ in $$$O(N)$$$. Then

where $$$A'$$$ is $$$A$$$ but sorted.

Such a clever observation and idea!!

Neat.

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) $$$

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

The formula might seem weird at first if you take the cases

you can see how one could have come up with "the cancelation" trick in the formula.

A little easier: Write $$$\max(A_j - A_i, 0) = \max(A_j, A_i) - A_i$$$. Then, the sum can be written as

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).

So nice trick!

I spend 1 min thinking the solution of F and 4 min for coding

after the round. Oops.$$$D > > > F$$$

maybe it's even easier than C.

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.

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 :(

You can check out video editorials of C, D, E, F if you are stuck

Can somebody explain their solution for problem G?

How can I approach problem E??

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.

My solution: https://atcoder.jp/contests/abc351/submissions/52883361

Thanks!

My solution discussion stream discussing A-F problems

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!)

Something like this: (

`segtree`

is a segment tree with operation "sum")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.)

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!!

You can use the Fencwick tree to store $$$\sum X_{j}$$$ $$$\forall$$$ $$$X_{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.

Spoilerhttps://atcoder.jp/contests/abc351/submissions/52887433

Can somebody tell why TLE in 4th?

You're creating a new 'vis' vector for every dfs call try optimising that.

Good luck !

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.

too many manhattan

How to solve F using 2 ordered multisets. thanks

I think BIT is more easy to solve the problem.