The ARC's should be doable, they're gonna be frequent again soon.

Inclusion Exclusion. Number of ways that we can pick any value from 0 to 9 = 10^N . Number of ways that 0 doesnt occur = number of ways to pick any value from 1 to 9 = 9^N. By same logic, number of ways that 9 doesn't occur anywhere = 9^N Number of ways that both 0 or 9 don't occur = 8^N Hence answer is 10^N — 9^N — 9^N + 8^N . Use mods wherever required

Why so many downvotes he is just asking the approach didn't say anything wrong or asked anything wrong U can just use Inclusion exclusion

In this question you need to find all sequences so:

1. There is some i such that Ai = 0 (count of such i may be > 1)
2. There is some i such that Ai = 9 (count of such i may be > 1)

(both conditions must be met)

Let's iterate k — number of positions i such that Ai = 0/9

Number of ways to create "good sequences" with 0/9 is 2^k — 2 (on every position you have 2 ways to put 0/9) (-2 because you don't need to create sequences 00..000 and 99..999)

Let's count C(n, k) — the number of ways to select a set of i positions from n positions, where we want to put 0/9

Finally we want to fill the remaining positions with number 1..8. It is equal to 8^(n — i)

And final number of ways for some k equal to C(n, k) * (2^k — 2) * (8^(n — i))

P.S. more details about Binomial Coefficients you can read here Binomial Coefficients

I understand, I thought there's just 1 minute left which won't really make any difference. One cannot implement it that quick. Sorry though I should have been a bit more patient

approach for e

Simple DP. very similar to this

Just coins here are {3, 4, 5 .. N}

I did it using Combinatorics, Stars and bars. Divide the number into x sums, (1 to s/3) and for each, find all possible combinations, by keeping each of it exactly 3 initially.

https://stackoverflow.com/questions/8006697/finding-maximum-distance-between-x-y-coordinates

I removed the mod (absolute value) by considering 4 cases.

case 1 : xi > xj and yi > yj

we need to find now max(xi-xj + yi-yj) = max((xi+yi)-(xj+yj)) = max(xi+yi)-min(xj+yj)

for other cases I multiplied coords by -1 and solved by case 1 again

case 2 : multiply all x by -1

case 3 : multiply all y by -1

case 4 : multiply all x and y by -1

Manhattan distance between two points is: |$$$x$$$_a — $$$x$$$_b| + |$$$y$$$_a — $$$y$$$_b|.

Now if can be evaluated in 4 ways:
$$$dist$$$ = ($$$x$$$_a — $$$x$$$_b) + ($$$y$$$_a — $$$y$$$_b)
$$$dist$$$ = ($$$x$$$_a — $$$x$$$_b) — ($$$y$$$_a — $$$y$$$_b).
$$$dist$$$ = -($$$x$$$_a — $$$x$$$_b) + ($$$y$$$_a — $$$y$$$_b).
$$$dist$$$ = -($$$x$$$_a — $$$x$$$_b) — ($$$y$$$_a — $$$y$$$_b).

Now if you simplify them a little then the distance can be one of the two below:
1) $$$dist$$$ = ($$$x$$$_a + $$$y$$$_a) — ($$$x$$$_b + $$$y$$$_b)
2) $$$dist$$$ = (-$$$x$$$_a + $$$y$$$_a) + ($$$x$$$_b — $$$y$$$_b)

Now the distance will be maximum from above expressions.
submission link

https://leetcode.com/problems/maximum-of-absolute-value-expression/discuss/339968/JavaC++Python-Maximum-Manhattan-Distance

the approach to solve was same as this question.

you were just given distance function instead of f(i, j)

void solve() {
    int n, x, y;
    cin >> n;
    vector<int> sum(n), diff(n);
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        sum[i] = x + y;
        diff[i] = x - y;
    }
    int maxone = INT_MIN, maxtwo = INT_MIN;
    int minone = INT_MAX, mintwo = INT_MAX;
    int ans = INT_MIN;
    for (int i = 0; i < n; i++) {
        maxone = max(maxone, sum[i]);
        maxtwo = max(maxtwo, diff[i]);
        minone = min(minone, sum[i]);
        mintwo = min(mintwo, diff[i]);
        ans = max({ans, maxone - minone, maxtwo - mintwo});
    }
    cout << ans;
}

Alternatively, you can calculate the convex hull of the given points and brute force the vertices of the polygon.

A and B was no math ;)

and D was also of dp ..No math

how to solve F ? It seems easy at first.

how to solve F ? Think about 70 mins and more but still fail to figure

What was the approach for F?

Can you please explain your solution to E, I don't know which one test case was failing, I got 17 AC and 1 WA

Can you check why I am getting WA on F. here is submission

More than being well known, E is pretty easily searchable I think.

e is well-known, u can google it

can I get any test case for which my code is failing?

I think reordering is not possible only in the case where lets say x occurs m times in A and k times in B and both k>=(n+1)/2 and m>=(n+1)/2. By pigeonhole principle!

My code https://atcoder.jp/contests/abc178/submissions/16703079

This is the best solution I have ever read!!

I am not claiming following is correct but I also cannot see why it is wrong. It must be wrong because it gives runtime error. The process was:

1. Find net frequency of each element in the two arrays. If it is greater than n, then it is not possible to rearrange.
2. Otherwise we use a max-heap to store pair of {"frequency in B", "number"}. Now we loop A from 1 to N and simply pop from heap and check it with A[i]. If not equal then we place it in our final array. Otherwise we pop another value and place it in final array. We push back the changed frequency.

I think it runs into dead end where it no longer finds a suitable pair, but why it happens? Thanks!

i think thats the easiest code to read and understand.

10^n-2*9^n+8^n Inclusion exclusion

You can use DP for accounting for double counting

Answer = (total sequence with length n and all element <= 9) — (total sequences such that it contains neither 0 nor 9)

first term above is simply pow(10,n) for the second term I used inclusion exclusion:

A = Set of sequences that doesn't contain 0

B = Set of sequences that doesn't contain 9

n(A union B) = n(A) + n(B) - n(A intersection B)

n(A) = n(B) = pow(9,n)

n(A intersection B) = pow(8,n)

C is simple inclusion — exclusion. My one line code :

cout << sub(add(power(10, n), power(8, n)), add(power(9, n), power(9, n)));

D could be solve by brute force the number of elements in the sequence and the do a star-and-bar-like counting trick.

My approach of D (Without dp ) :
First of all fix the length of the sequence .
Suppose length is 5 ;
so a1 + a2 + a3 + a4 + a5 = S ; now for all i , a[i]>=3 ;
using stars and bars technique  ,
no of solution  of that equation is ncr(s-3*length +length -1 , length-1);here length = 5 ;
final answer = sum of solutions for each fixed length .

int ans=0;
    for(int len=1;len<=s;len++)
    {
       if(s<(3*len))continue;
       int sum=s-3*len;
       int yo=ncr(s-(3*len)+len-1,len-1);
       ans=(ans+yo)%mod;
    }
    cout<<ans<<endl;