July 24, 2018 Automatic Vacuum Cleaner

As problems are solved by the intrepid Topcoder programmers, this simple problem from Topcoder Algorithm Contest 2018 in India proves to be a bit of a brain teaser.
The problem states that a vacuum cleaner is cleaning a rectangular room. The floor is divided into unit squares with R rows by C columns. The robot starts from the left corner and cleans towards the right. If you are given the number of rows ( R ), the number of columns ( C ), the number of cells cleaned (A), and the number of cells left to clean (B), one must calculate the number of moves that it takes to return to the original cell. The solution takes the arguments (R, C, A, B) as longs and returns a long integer with the number of steps needed to return to the original square.
A simple example of this problem in action is provided as such. If one has to clean a room with five rows, two columns with two cleaned cells and has two more cells to clean, how many moves does the robot take to return to the original square? The robot is in the second cell, and it will clean the next two cells and move to the left two times to return to its original cell.
Now that the logic is established, let us start solving the programming problem. We start by figuring out the distance between A and B. If A is in a corner or B ends up being in a different row in a different position, shifting left or right a few times will not be sufficient for solving the problem:
Finding the number of rows between A and B involves deciding the position based on row and column. For A, figuring out the row and column involves these equations:

	A’s row: (A’s cell number - 1)/(the number of columns)
	A’s column: (A’s cell number - 1) % (the number of columns)

For B, it involves using the position of A:

	B’s row:  (A’s cell number + B’s cell number - 1)/(the number of columns)
	B’s column: A’s cell number + B’s cell number - 1)% (the number of columns)

Afterwards, it is necessary to decide if A’s determined row has been calculated to be even or odd. If it is calculated to be odd, A’s column is changed to be the number of provided columns minus A’s column and 1. The same formula can be applied to the B cell. At the end, the absolute difference between the row measurements and the column measurements is calculated and the number of moves is provided.
The code snippet is written in C++:

long getDistance(long R, long C, long A, long B){
	long a_rows, b_rows, a_columns, b_columns;
	a_rows = (A - 1) / C;
	a_columns = (A-1) % C;
	if (a_rows % 2 != 0){
    a_columns = columns - 1 - a_columns;
  }
  else
  {
    a_columns = a_columns;
  }
  b_rows =  (A + B - 1) / C;
  b_columns = (A + B -1) % C;
  if (b_rows % 2 != 0){
    b_columns = columns - 1 - b_columns;
  }
  else
  {
    b_columns = b_columns;
  }
  long diff_rows;
  long diff_columns;
  If (a_rows > b_rows)
  {
    diff_rows = a_rows - b_rows;
  }
  else{
    diff_rows = b_rows - a_rows;
  }
  If (a_colums > b_columns)
  {
    diff_columns = a_columns - b_columns;
  }
  else{
    diff_columns = b_columns - a_columns;
  }
  return diff_rows+diff_columns;
}

The winning solution was implemented in C++. Be sure to keep your eyes peeled for the next Single Round Marathon or Marathon Match if you were not able to participate in the TCO SRM from India. Happy coding!


maxwells_daemon

Guest Blogger



UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds