DIETCOKE - Editorial

cakewalk
nuttela

#1

PROBLEM LINK:

Practice

Contest

Author: Soham Chakrabarti

Tester: Soham Chakrabarti

DIFFICULTY:

Cakewalk

PREREQUISITES:

Math

PROBLEM:

You are provided an area divided into M x N blocks.

A straight, red line has been drawn from one corner to another (left to right).

Find the number of blocks that contains the red line on it.

EXPLANATION:

Explanation

First, suppose that N and M have no common factor. Then the diagonal line doesn’t go through any intersections, so each time it crosses a horizontal or vertical grid line, it adds 1 to the number of squares touched. And to get from the top left to the bottom right, it must pass through N−1 vertical grid lines and M−1 horizintal grid lines. Counting the orginal square in the top left, this gives a total of 1+(N−1)+(M−1)=N+M−1 squares touched. This formula applies to your first and second diagrams.

Now suppose that N and M have a common factor. Let q=(N,M) be the largest common factor of N and M. Then N/q and M/q have no common factor, so we can break the problem up into q smaller rectangles strung along the diagonal, each of size N/q×M/q; and in each such rectangle the number of squares visited is N/q+M/q−1. So the total number of squares visited is q×(N/q+M/q−1)=N+M−q.

Hence in all cases the number of squares touched is

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s and Tester’s solution can be found
Link