top 3 reason for depression

1. breakup

2. Substance Abuse

3. WA in div2 A

For problem D, I didn't use DP at all. Instead, I build the graph of valid jumps and do BFS.

To build the graph, I process all values increasing by height, connecting a node to the first one it sees in the left and right directions that was processed earlier. This is just maintained with a set. Of course, I do this again but decreasing by height as well.

ahahahaha.. so clever

After 1 hr of unsuccessful struggle on A, i saw the title.

I actually got "ahahahahad" in problem A after a struggle of 1 hour:/

The constraints on task C were way too tight for no reason. I barely passed (with Java) in 997 ms after failing to 3 times.

The editorial for D is too bad. Can anyone explain me, Thanks in advance.

I solved problem C in a different way. I used the same observation. My program asked for each $$$i$$$ and $$$i + 1$$$ for odd $$$i$$$ and divides the indexes in two groups, the one of the smaller elements, and the one with the larger elements. We know the values for the smaller elements ($$$\min(x, y) = \max(x \mod y, y \mod x)$$$). Now we can solve recursively for the second set. It converges to $$$2n$$$. 92266927

How to solve problem B if you change $$$c_i = \gcd(b_i, b_{i + 1})$$$

How to die peacefully when solution of D failed just because of == in place of =

Alexandra has an even-length array a, consisting of 0s and 1s. The elements of the array are enumerated from 1 to n. She wants to remove at most n2 elements (where n — length of array) in the way that alternating sum of the array will be equal 0 (i.e. a1−a2+a3−a4+…=0). In other words, Alexandra wants sum of all elements at the odd positions and sum of all elements at the even positions to become equal. The elements that you remove don't have to be consecutive._ what was the meaning of consecutive element not to be removed but most solution got accepted without this condition being fulfilled

I think my solution of A is a bit easy to understand (idk you tell me)

Approach: run a while loop with $$$i = 0$$$ as initial index, if I see a $$$0$$$ I will include this in my sequence, else if I find a $$$1$$$ I will see the next element and if it is also $$$1$$$ I will include these both since they cancel out each other and increment the index by 2

finally I print the sequence.

Incomplete EdItOrIaL

I was thinking to use seqment tree with Dp to solve D

i.e Just never write editorial again, worst D explaination!

Was problem $$$A$$$ "Ahahahahahahahaha" written by dick? Seems so to me after reading it's name.

If a part of turorial is missing we can still use mango_lassi submission 92251944

thanks finally i will be expert :)

How does one even get to that observation in C?

Hi, my dp solution for problem D got WA on testcase 27 with just a slight difference with Jury’s answer.

Participant's output 102549 Jury's answer 102548

Basically my way of approaching it is for every building i, save the first building to its left/right that has height >= h[i], <= h[i] (4 dp values for each building).

Then using this information, compute another 2 arrays rg, rs.

rs[i]/rg[i] means the leftmost building which has height smaller/greater than h[i] and has i as its corresponding dp value talked about above.

After we got this values, just go from f[1] ~ f[n] and take the min of the previous steps that could jump to this point.

Can someone see why I got WA? Thanks!

can anyone tell me what is the problem with this submission? I just cant understand why my answer isnt correct...

Can someone please help me find an example test case where my solution for Question D will fail? I can't quite figure out why it is getting WA on TC 5 92270795

I got stuck in the 1st question !! So, I decided to start with the 3rd one. But even after solving 3rd, I could not figure out the logic of 1st question. A(hahahahahahahaha) .... Anyway a nice contest !!

In 3rd approach of problem B , i got that number of distinct values of $$$c_i$$$ should be $$$O(logA)$$$.But i didn't got why we need to iterate only $$$O(nlogA)$$$ times ? It might be possible that first few values of $$$c_i$$$ might be equal ? Can someone explain through an example .

Can anyone please point out mistake in my code for 2C?I have been looking for many hours now but can't find it :( What can be the mistake? (Got WA on Test case 8) https://codeforces.me/contest/1407/submission/92283806

how to solve E?

The question actually "ahahahahahaha"ed me for the first 20 minutes, then I "ahahahahahaha"ed the question with a pretest passed verdict.

In problem D, one can observe that using the DP approach for calculating the first next larger element, the jumps done while calculating $$$dp[i]$$$ are exactly the valid jumps stated by the problem. This can make the code simpler.

The other solution (the also computes for each index, the first previous larger/smaller), proves that the complexity of the DP approach is $$$O(n)$$$, or more precisely, the DP approach will make $$$2n$$$ jumps.

Greedy Solution to 1407E - Egor in the Republic of Dagestan

Save all edges in the reverse direction (save edge $$$(u,v,t)$$$ at $$$v$$$ instead of $$$u$$$).

Now do a BFS from $$$n$$$. Supposing we are currently dealing with $$$v$$$. For an edge $$$(u,v,t)$$$, if $$$u$$$ has been colored in $$$t$$$, then $$$u$$$ is inevitable and needs to be added to the queue. Otherwise, we set $$$u$$$'s color to be the opposite of $$$t$$$ so that $$$u$$$ would not be added, at least temporarily.

In the end, we check if $$$1$$$ has been visited. If $$$1$$$ has not been visited, then we have found a way to make $$$1$$$ and $$$n$$$ not connected. Otherwise $$$dist[1]$$$ is exactly the longest shortest path we are required to find.

The greedy strategy works, because it is always better, or at least not worse to make the decision at an earlier stage. Supposing there are $$$(3,5,0)$$$ and $$$(3,6,1)$$$, and we visit $$$5$$$ first during the BFS. If we set $$$3$$$'s color to $$$0$$$ (so as to ban $$$6$$$ instead of $$$5$$$), then $$$(3,5)$$$ will be a valid path, and since $$$5$$$ is visited earlier than $$$6$$$, the distance from $$$5$$$ to $$$n$$$ is no larger than that from $$$6$$$ to $$$n$$$, which is not what we want.

Since we have set the colors during the BFS, we only need to output them. For those uncolored nodes, either color is OK.

Code: 92282786

Problem D should add following statement to clarify the task: Vasya can ONLY use discrete jumps, It means that all non-discrete jumps are not accepted. I'm a bit confusing why doesn't Vasya jump straight from 1 to n in the first sample test :-)

In Problem C, in editorial's solution we are not flushing the stream.

My Code gives AC when I flush, But EXACT SAME Code gives Idleness limit error when I don't flush the stream.

If author's solution is working why mine isn't :/ Can anyone please tell the error ?

(Code is printing a new line after ever output!)

EDIT: Got it. I had a macros which defined endl as "\n", thereby not flushing with endl.

Chinese tutorial has been uploaded.

For task E: Why is it necessary to reverse the edges? Why not just begin from 1st Node and try to reach the Nth node.

From what I understand, it might be to reduce the number of unnecessary nodes that the queue visits. Can someone explain it more clearly? What is the intuition behind it and when is such a modification helpful?

The problemset was well balanced in terms of difficulty level.

May someone please explain how do we implement the third idea in the solution of problem B? Thanks in advance :D

In editorial of C, how come the first query is valid given you are querying for (0, 1) and according to constraints : 1 <= x ,y <= n

In problem E editorial, why are edges reversed and then processed starting from n ?

@i.e . for (int i = 0; i < n; i++) { for (int to : jumps[i]) { dp[to] = min(dp[to], dp[i] + 1); } } cout << dp[n — 1];

could u please explain it and time complexity of this particular loop in soln of problem D div-2. Thanx in advance.

Can someone please explain me the logic of question B...

Apparently A(hahahahahahaha) was not so apparent

The Problem E, Test #11.
92324802 Emmm, what happened? why the hint say the answer is 5?

Can we use "\n" in c++ to flush the output instead of cout.flush()? I have solved interactive problems on other platforms and "\n" works fine. I used "\n" in problem C to flush output and got Idleness limit Exceeded.

Editorial of D states that if hx <= hy than hy is first skyscrapper that not smaller than hx.

Consider this case: heights: 2 6 4

let hx = 2 and hy = 4

here hx <= hy but hy is not first skyscrapper not smaller than hx. Instead it's the 2nd skyscrapper.

Question D. Discrete Centrifugal Jumps With an explanation.

I hope my comments will help others to understand the solution :)

// vrkorat211 - Vivek Korat

const int N = 3e5 + 5;
 
int n;
int a[N];
void GO()
{
    cin>>n;
    for (int i = 1; i <= n; ++i)
    {
        /* code */cin>>a[i];
    }
    std::vector<int> dp(n+1);
    stack<pair<int,int>> st1,st2;

    st1.push({a[1],1});
    st2.push({a[1],1});

    // dp[i] = minimum step to reach at index i with given two jump properties.
    // pair.second in stacks will store index of pushed element.
    // it will be used to access dp array.

    /**Algo.**/

    // st1 will keep elements with strictly decreasing order.
    // st2 will keep elements with strictly increasing order.

    // for both sequence, if the sequence is broken then pop some elements
    // to get sequence property(strictly increasing or strictly decreasing) back. 

    // when we pop element than one of the jump properties will be followed so update dp[i]
    // accordingly.

    /**\Algo.**/

    // Above comments may help to understand the code :)

    dp[1]=0;

    for (int i = 2; i <= n; ++i)
    {
        //one move always possibee from index (i-1) to index (i) in 1 step;
        dp[i] = dp[i-1] + 1;

        if(a[i] > a[i-1])//st1 property violates.
        {
            //pop untill strictly deacreasing property follows with current element
            while(!st1.empty() && st1.top().first < a[i])
            {
                st1.pop();

                if(!st1.empty())
                {
                    //a[i] and top element follows jump property.
                    //update dp[i]
                    dp[i] = min(dp[i],dp[st1.top().second]+1);
                }
            }
        }
        else if(a[i] < a[i-1]) //st2 property violates.
        {
            //pop untill strictly increasing property follows with current element
            while(!st2.empty() && st2.top().first > a[i])
            {
                st2.pop();
                if(!st2.empty())
                {
                    //a[i] and top element follows jump property.
                    //update dp[i]
                    dp[i]=min(dp[i],dp[st2.top().second]+1);
                }
            }
        }

        // remove top equal elements from both stacks.
        // Because they violates sequence property of both stacks.
        while(!st1.empty() && st1.top().first == a[i])st1.pop();
        while(!st2.empty() && st2.top().first == a[i])st2.pop();

        // Now current element is in proper sequence for both stacks.
        // So push it in both stacks.
        st1.push({a[i],i});
        st2.push({a[i],i});
    }

    //finally d[n] is minimum step to reach at index n.
    cout<<dp[n]<<endl;
}