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

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

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

Hope to solve 6 problems.

Yes

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.

Test case:

3 3
..#
...
#..

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

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.

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:

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.

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

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!

$$$D > > > F$$$

• 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

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

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.

cin >> n;
    vl a(n); 
    rep(i, n) cin >> a[i];
    map<int, int> 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(i<sz1&&j<sz2) {
            if(x[i].fi<y[j].fi){
                cnt[x[i].se]+=sz2-j;
                
                p[k++]=x[i++];
            } else p[k++]=y[j++];
        }
        while(i<sz1)p[k++]=x[i++];
        while(j<sz2)p[k++]=y[j++];
    };
    auto f = [&](int l, int h, auto &&f)->void {
        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;

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

I think BIT is more easy to solve the problem.