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;

I did D using combinatorics. It is the modified version of distributing n balls into r urns such that each urn contains at least 1 ball.

Solution of standard problem: (n-1)C(r-1).

Here problem can be reformulated as if you can use any number of urns (because the length of sequence can vary) and each urn should contain at least 3 balls.

Solution: summation of (n-1-2*i)C(i-1) for all i, where i is the number of urns and n is the sum we want. The term -2*i because we first put 2 balls in every urn so that problem is now transformed into a standard one containing at least 1 balls, for each i.

https://atcoder.jp/contests/abc178/submissions/16705277

nC2 * 10^(n-2) will duplicate

There are repetitions in your formula. For n = 4 the answer is 974. Check with your submission

Index is not necessary in the state.

In $$$C$$$ constraints are smaller, so if someone has weak combinatorics(like me) then dp is more intuitive imo. here is my sol using dp:

#include <bits/stdc++.h>

using namespace std;

constexpr int mod = 1e9 + 7;

struct M {
    unsigned v;
    M(long long a = 0) : v((a %= mod) < 0 ? a + mod : a) {}
    M& operator+=(M r) { if ((v += r.v) >= mod) v -= mod; return *this; }
    M& operator-=(M r) { if ((v += mod - r.v) >= mod) v -= mod; return *this; }
    M& operator*=(M r) { v = (uint64_t)v * r.v % mod; return *this; }
};

uint32_t add(M a, M b) { return (a += b).v; }
uint32_t mul(M a, M b) { return (a *= b).v; }
uint32_t sub(M a, M b) { return (a -= b).v; }

int n;
const int maxn = 1e6;
int dp[maxn][2][2];

int go(int id, bool zero, bool nine) {
    if (id == n) {
        return zero & nine;
    }
    int &ref = dp[id][zero][nine];
    if (~ref) {
        return ref;
    }
    int ans = 0;
    // 8 ways to place a numbers from [1, 8]
    ans = add(ans, mul(8, go(id + 1, zero, nine)));
    // place a 0 here
    ans = add(ans, go(id + 1, 1, nine));
    // place a 9 here
    ans = add(ans, go(id + 1, zero, 1));
    return ref = ans;
}


void solve() {
    memset(dp, -1, sizeof dp);
    cin >> n;
    cout << go(0, 0, 0) << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

Hey, in problem D, I think you also need to add 1 to dp[i].

if a<0 then use mod-abs(a) will work.

Don't forget to add mod when you are subtracting two numbers under mod.

we can do this : ans = (a-b+MOD)%MOD;

Total Number: 10^n

Without digit '9': 9^n

Without digit '0': 9^n

Without both: 8^n

Final Result: 10^n — 9^n — 9^n + 8^n

Total numbers you can make using all digits (10^n) — numbers with all digits but 9 (9^n) — all but 0 digits (9^n) + all but 0 and 9 (8^n) (because they were deleted twice);

WA or TLE?

I don't think it can work , the nodes and edges are too many !

of course it will :))))

maybe you can try using a segment tree to build the graph.

Resulting ordering of B array is some cyclic shift of itself. (If no shifting is possible, no solution).

you can see this solution I just tried to solve F using this and got AC. Logic is simple as well as code. Here is my code for this approach

Result of a1 — a2 + b1 may be negative, so just add MOD to it before taking remainder