Codeforces 1136B. Nastya Is Playing Computer Games Codeforces Round #546 (Div. 2)

codeforces Zinnatul Islam Morol Tuesday, March 12, 2019

Problem link

Each manhole uses 3 moves: 1 move to throw the stone on it. Plus one move to open the manhole and retrieve the coin, and 1 more move to go to a neighboring manhole. Thus, 3*num. But this is only the base case when there are 2 manholes.

Consider the case when there are 3 manholes, and let's say you start from the middle(tc = 2), after picking up the coin at this manhole #2, you have to go to left(manhole 1) or right(manhole 3) to retrieve their coins. Suppose you decide to go left first, i.e manhole #1, then after picking up the coin at 1, now you have to go to 3 in order to collect the last coin. You have to skip manhole #2 as it's empty. It will take one additional move, which is obtained by (tc-1) = 1. In this case, (tc-1) = (num-tc) = 1 as tc is at the middle. In situations where there are unequal bipartitions, tc is either more towards the left or more towards the right. If tc is more towards the left(tc <= num/2), then traverse left first and then go right, which can otherwise be calculated by (tc-1). Vice-versa is true when tc is more towards the right(tc > num/2), which is found by (num-tc). Since the objective is to find the minimum number of moves, we take the min of the two, i.e. min(tc-1, num-tc).
Remember, each manhole takes up 3 moves on its own. The extra addition term is when we change directions and skip the already visited manholes.

credit:
AKASH DAS
( from - Comment )

A solution in c++

4 Comments

Duc Khai TongTuesday, 12 March 2019 at 22:20:00 GMT+6
I still haven't got it. Can you explain, please.
UnknownWednesday, 13 March 2019 at 04:49:00 GMT+6
Here is a less mathematical solution:-

#include
using namespace std;

#define LEFT -1
#define RIGHT 1
#define PICK_A_COIN 1
#define GO_TO_NEIGHBOURING_MANHOLE 1

int main(void)
{
int n, k, coins = 0, moves = 0;

// INPUT: No. of manholes & Index of initial manhole
cout << "INPUT: Enter number of manholes and index of initial manhole:" << endl;
cin >> n >> k;

// Translating to array index
k = k - 1;

// Creating a dynamic array
int *stones_on_manhole = new int[n];

// Initializing the array values to 1
std::fill_n(stones_on_manhole, n, 1);

// Initialization of current manhole which Nastya is on
int current_manhole = k;

// Determining the direction of movement from initial manhole
int step = (k < n / 2) ? LEFT : RIGHT;

// Collecting all the coins and counting the moves required
while (coins != n)
{
if (current_manhole == -1)
{
cout << "Reached leftmost manhole. Changing direction of traversal." << endl;
moves += k;
current_manhole = k + 1;
step = RIGHT;
cout << "Skipping previosuly visited(empty) manholes.\n";
cout << "Move Count = " << moves << endl
<< endl;
}

if (current_manhole == n)
{
cout << "Reached rightmost manhole. Changing direction of traversal." << endl;
moves += n - k - 1;
current_manhole = k - 1;
step = LEFT;
cout << "Skipping previosuly visited(empty) manholes.\n";
cout << "Move Count = " << moves << endl
<< endl;
}

cout << "Nastya is on manhole #" << current_manhole << endl;
cout << "# of stones on its cover = " << stones_on_manhole[current_manhole] << endl;
cout << "Next Move -> " << step << endl;
stones_on_manhole[current_manhole - step] += stones_on_manhole[current_manhole];
coins++;
cout << "Coins picked up = " << coins << endl;
moves += stones_on_manhole[current_manhole];
moves += PICK_A_COIN;
cout << "Move Count = " << moves << endl;
if (coins != n)
{
current_manhole += step;
moves += GO_TO_NEIGHBOURING_MANHOLE;
}
cout << endl;
}

// OUTPUT: Minimum number of moves to pick all the coins
cout << "OUTPUT:\tTotal Moves = " << moves << endl;

// Deallocation of the dynamically allocated memory
delete[] stones_on_manhole;
stones_on_manhole = NULL;

return 0;
}