professor_of_stupidity's blog

Doubt in Solution for Codeforces Global Round 13 Problem B
By professor_of_stupidity, history, 4 years ago, In English

1491B - Minimal Cost 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;
    }
    
}
  • Vote: I like it
  • -15
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

. . # . . . .

. . . # . . .

. . . . # . .

. . . . . # .

. . . . . # .

here A[n] == A[n-1]

answer is min(u,v) but your logic will give incorrect solution.

. . # . . . .

. . . # . . .

. . . . # # .

. . . . . . .

. . . . . # .

One possible scenario.

Hope it helps.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You are only checking for last row which means only 1 of the a,b,c case is possible and other cases will be eliminated. For example There might be some rows before the last one which have seperation more than 1 from bottom or top row but you will miss this answer(0) if for last row the obstacle is inline with the one above as your code will run into case a.

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I think the whole column can be obstructed. The whole row can't be obstructed.

Edit:- Just realised what you said was correct. I hadn't seen the input params properly. (There can be no coin on the first column and only one coin on the first row) I literally got demotivated and left the contest after thinking just Problem B was too tough for me. Because I though first colum could be littered with coins. And it really got to me that just the first question required some weird backtracking jugglery.

Wasted 4 hours just realising I wasn't exhausting the input. Here's my go at it with O(1) space. Because you don't even need the array.

#include<iostream>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    for (int i=0; i<t; i++) {
        int n, u, v, ai, aip1;
        cin >> n >> u >> v;
        int min_val = min(u + v, 2 * v), min_u_v = min(u,v);
        cin >> ai;
        for (int j=1; j<n; j++) {
            cin >> aip1;
            if (abs(aip1-ai) > 1) {
                min_val = 0;
                // EXHAUSTTTT input STUPIDDD!! MISTAKE!!
                for (j++; j<n; j++) cin >> aip1;
                break;
            } else if (abs(aip1-ai) == 1) {
                min_val = min_u_v;
            }
            ai = aip1;
        }
        cout << min_val << endl;
    }
    return 0;
}
→ Reply