Doubt in Solution for Codeforces Global Round 13 Problem B

Revision en1, by professor_of_stupidity, 2021-02-28 21:23:23

1491B - Минимальная стоимость Let me just jump straight to my doubt: The editorial gives the solution as:

My concern is, why do we need to check for all the ai's? My approach was: 1. Since the whole first column will not be obstructed, the user can go directly to the last row. 2. Now, in the last row, there can be two scenarios: the obstacle is inline with the obstacle of the 2nd last row or out of line. a. If they are in line, then I have the option of moving either piece two units horizontally, or move the last obstacle diagonally upwards. Hence:

ans = min(2*v, u+v)

b. Otherwise, if the separation between the last and second last obstacle is equal to more than two, then the user can "slid in" between them without spending any coins. Hence answer in this case would be 0.

c. Now if they are not in line and the condition b also fails, then I simply have to move the last obstacle either up or horizontally, only in one move, which would either clear off the last row or make a window between the last and second last obstacle so that the user can, again, "slid in" between them.

Can someone tell me what I am doing wrong in this approach? According to me, it should work, but it's giving wrong answer on a pretest only.

Here's my code if someone wants to look at it: (Don't care about the indices used. I had taken an array of size n+1)

if (arr[n]==arr[n-1])
{
    cout<<min(2*v, u+v)<<endl;
}
else
{
    if (abs(arr[n]-arr[n-1])>=2)
    {
        cout<<0<<endl;
    }
    else
    {
        cout<<min(u, v)<<endl;
    }
    
}
Tags #doubt, #global round 13

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English professor_of_stupidity 2021-02-28 21:33:53 6
en1 English professor_of_stupidity 2021-02-28 21:23:23 1737 Initial revision (published)