How did yo solve it? Can you explain your idea?

How did you solve $$$C$$$? Please tell.

Indeed how to solve $$$C$$$. Greedy algorithms like taking largest possible number fail. I felt it was kind of similar to yesterday's A

Digit dp-esque dp worked for me

dp digit

for a given k can we do it? if we can answer this then its easy just do k++ until we get one. It will never go too far. Now lets try to answer the first part that for a given k can we do it? Try to think of a dp state. run a loop from right to left digits one by one in n. ( i=1 to len(n)) i=1 corresponding to the rightmost digit.

we will pass three variables after every iteration i. lowest and highest carry, and mx_k that is the maximum no. of i-1 digit numbers possible up to this point. and lowest and highest carry should correspond to mx_k.

tough to explain the mx_k part. Give a good read and think you will get what I meant to say.

my solution

Another solution with dfs: The restriction that no digit can be 0 is troublesome, so I considered to clear out this. We minus n with numbers like 111111, 1111 first, and then the digits can be 0,1,2, which is a greedy problem similar to 1530A. Thus it can be proved that the answer is not greater than 5, and we are able to solve it by dfs. For each number, we only need to fix its length, and minus n with 11..1 with the same length. In the end check whether n (after minus) can be constructed by numbers which digits are 0 or 1 or 2. With a little amount of optimization, the solution was accepted.

If $$$a_i > a_{i+1}$$$, it's optimal to choose $$$b_i = b_{i+1}$$$, else it's optimal to choose $$$c_i = c_{i+1}$$$.
Then, the $$$b_i$$$ and the $$$c_i$$$ can be uniquely determined for a fixed $$$b_1$$$ and they have the form $$$\mid b_1 - k \mid$$$ ($$$k$$$ is different for each $$$b_i$$$ and $$$c_i$$$).
The optimal $$$b_1$$$ is the median of the $$$2n$$$ values of $$$k$$$.

ternary search on the value of $$$B_1$$$, knowing that $$$B_i=B_{i-1}+max(A_i-A_{i-1},0)$$$ and C as the complement of B

It's the first editorial in E. Seem like the author put it in the wrong place.

One of the (almost) middle elements can be 0

After fix we do simple greedy to left and right

arc123/submissions/24365978

I think AtCoder is turning harder and harder.

All the latest ARCs are mostly hard, you also need to get used to the ARC problems, on my first ARCs I always had a bad performance and the problems seem quite difficult, however after some contests, you will find the problems more accessible (excluding all F's, and some E's, and the other problems are still hard, but at least you can elaborate more on how to solve them). They are really fun and you can learn and enjoy a lot. I am really grateful to all atcoder writers, coordinators, and staff, the contests are great.

the sequence [a,b,c] is an arithmetic one if a-b == c-b so 2b — a — c must equal 0 let x = 2b — a — c and we will make x equal to 0 by two operations : 1. increase x by 2 (same to add 1 to b in the original problem) 2. decrease x by 1 (same to add 1 to a or c ) now there are 2 cases : x > 0 then the only way to make it 0 is decreasing it by one x times (so we need x operations). x < 0 then we will keep adding 2 until x becomes positive then back to the case 1 this case requires Ceil( x / 2 ) operations.

`

First sort all the three input arrays(A,B,C) and then count for valid triplets such that the upper bound of first element from the first array A uniquely exists in second array B and upper bound of that element from second array B uniquely exists in third array C.

sort( a.begin(), a.end() );
sort( b.begin(), b.end() );
sort( c.begin(), c.end() );
int count = 0;
for(int i = 0; i < n; i++){
    auto itr1 = upper_bound( b.begin(), b.end(), a[i] );
    auto itr2 = upper_bound( c.begin(), c.end(), *itr1 );
    if ( itr1 == b.end() || itr2 == c.end() ){
        break;
    }
    else{
        count += 1;
        b.erase(itr1);
        c.erase(itr2);
    }
}
cout << count << "\n";

I used 3 pointers approach.

Sort all the three arrays, start from the beginning. If x[i] < x[j], then there are two possibilities i.e x[j] < x[k] then we get the valid triplet so increment the answer and all the pointers by 1, otherwise if x[j] > x[k], then we'll have to pickup a bigger element from the 3rd array so we increment k by 1. Similarly if x[i] > x[j], we'll have to pickup a bigger element from the 2nd array so we increment j by 1.

Time Complexity of this method will be O(n*logn + n) = O(n*log(n)) as we are doing this in a single iteration after sorting all three arrays.

for u in range(int(input())):
    n = int(input())
    x = map(int, input().split())
    y = map(int, input().split())
    z = map(int, input().split())
    
    x = sorted(x)
    y = sorted(y)
    z = sorted(z)
    
    i = 0
    j = 0
    k = 0
    ans = 0
    
    while(i<n and j<n and k<n):
        if(x[i] < x[j]):
            if(x[j] < x[k]):
                ans += 1
                i += 1
                j += 1
                k += 1
                
            else:
                k += 1
        
        else:
            j += 1
            
    print(ans)