Your profile pic is itself wonderful !!

Atcoder beginner contests are just a joke. Only 1-2 good problems (probably E and F) and others are just fillers. Atcoder beginner contests should be of Div-2 difficulty or atleast in-between Div-2 and Div-3.

I think F is easier than E. (I'm trying to solve F)

D was very interesting.

"B" in "ABC" stands for beginner.

Keep alive this round, try to alive next round(Be careful when there are two 1, and one 0).

Always increase a smaller variable and decrease a greater one in a pair, except for the one case: when two variables you need to change are $$$1, 1$$$ and the third one is $$$0$$$, in this situation you have to choose what variable to increase depending on the next request in order to avoid a case like where you have $$$2, 0, 0$$$ and the next request is $$$BC$$$.

Here's my solution.

You need to use the frequency map, In first loop perform f[ i — a[i] ]++, and in second loop perform count += f[ a[i] + i ]. that's it

For two attendees to pair i-j = hi + hj (Assume i>j) should hold where i and j are indices of the attendees. Move both the i terms on i side and j terms on the other then it reduces to i-hi = hj + j. Which is equivalent to finding number of comment elements in two arrays by making arrays for both i-hi and the other as hj+j.

E is pretty easy if you make the observation that for any j > i following condition has to holds, j — A[j] = A[i] + i. so keep a map to count the occurrence of A[i] + i observed till now. add the count of j — A[j] into the answer.

solution

You need to find number of pair of indices such that |j-i| = A[i] + A[j] . Assume j > i, then, you need to check which (i,j) satisfy j — A[j] = i + A[i].

You can start iterating from left, keep a count of i+A[i] and for every new index j, do, ans+=count[j-A[j]]

We are considering j > i so we need to find all i and j such that

j - i = a[j] + a[i] which is a[j] - j = - a[i] - i

so for each j we need find count all of those whose value - a[i] - i is equal to a[j] -j. We can use a map to store values of - a[i] - i and add it to our answer in each step for value a[j] - j.

Code

Just use the fact that A[i]+A[j]=abs(i-j) expands to i-A[i]=A[j]+j (atleast in positive value of abs sign). For the other one it'll cover cases by symmetry. No compute the two arrays with entries i-A[i] and j+A[j], store the counts of elements in a frequency map and return the answer.

A simple solution is here

An easy code to understand

What do you do when both A and B are equal and next event is AB?

For example: A = 1, B = 1 and C = 0 and event is AB.

You need to check if next event is BC or AC and work accordingly. Can't just make anyone of it +1 and other -1.

I guess only 2 details to deal with no ? Check if one of them is 0 or both of them are 1. My code wasn't that long either : https://atcoder.jp/contests/abc166/submissions/12771073

Can you share your detailed approach?

F

Start traversing a from back to front and at each i from $$$1$$$ to $$$N$$$ keep count of $$$i$$$-$$$Ai$$$ and check how many previous elements are there with current sum $$$i$$$+$$$Ai$$$.

My Solution

Comment

Your code has a complexity of O(N^2) and N is 1e5. So that is why you are getting TLE.

TLE = Time limit exceeded.

Checking every possible pair (complexity O(N^2)) is not efficient enough for such a big value of n as 2*10^5.

My solution was to choose such an option that I will survive current and also next round. If both choices are survivable then go greedy.

You could just run a DFS and check if you can reach a path of length n. Start with state a,b,c and then at each point proceed to a 2 posibble state given by choice[i].

Here is my submission: https://atcoder.jp/contests/abc166/submissions/12776155

I tried with 27*n dp but it failed

Greedy approach can get AC, You only need to check a couple of things first :

• If one of them is 0 you have to add it +1.
• If both of them 1, you need to check which one comes next first, for example if the order is AB then BC ( A = 1, B = 1, C = 0 ) you have to add +1 to B otherwise you add it to the other.
• If you're not in any of the other cases you can just add +1 to the minimum of them.
• Keep checking if one of them is less than 0 return No

Solution : https://atcoder.jp/contests/abc166/submissions/12771073

Maybe Highly optimized,choose the right answer first, so it succeed when first get into end state.

Can you share your code?

It all comes to when is the answer No : The only possibility it fails is if there are 3 zeros or 2 and a certain ordering to make it fail. That being said, The answer can be found fast enough for both cases.

D is quite easy. You just need to use brute force and compute all fifth powers of numbers from -1000 to 1000, and then you can use an O(n^2) algorithm to see if x is equal to the difference of any two. Code

I don't have a strong proof as to why will there always be a pair less than |a| , |b| <= 10^3 but had some intuitive feeling and it ACed

int power(int x,int b){
    return x*x*x*x*x;
}
 
void solve()
{
    int x ;
    cin>>x;
    int a = 0, b = 0;
    for(int a=-1000;a<=1000;a++){
        for(int b = -1000; b <= 1000; b++){
            if(power(a,5) - power(b,5) == x){
                cout<<a<<" "<<b;
                return;
            }
        }
    }
}