CUTPIZ - Editorial

editorial
, ,
1

Problem Link - Cutting Pizza Practice Problem in 1400 to 1600 difficulty problems

Problem Statement:

In this problem, Vasya wants to divide his pizza, which already has some premade cuts at specific angles, into equal slices. The task is to determine how many additional cuts he needs to make to achieve this.

Each test case consists of:

  1. The number of premade cuts n.
  2. A list of n angles representing the positions of these cuts, measured counterclockwise from a fixed reference point (0 degrees).

We are tasked with finding out how many additional cuts (if any) are required to divide the pizza into slices of equal angular sizes.

Approach:

  • The pizza is a circle with a total angle of 360 degrees. If the pizza is divided into k equal slices, then the angle between each adjacent cut should be 360/k degrees.
  • If the existing cuts divide the pizza into a set of angles, we can check if it’s possible to partition these angles into equal slices.
  • The number of equal slices will be determined by the greatest common divisor (GCD) of the angular gaps between consecutive cuts.
  • We compute the differences between consecutive angles (considering the circular nature of the pizza), and the GCD of these differences tells us the smallest slice size.
  • If the GCD of the gaps between existing cuts is g, the pizza can be divided into 360 / g slices.
  • If 360 / g is greater than n, we need to add 360 / g - n cuts to make the number of slices equal.

Steps:

  • Calculate Gaps: Calculate the angular gaps between consecutive cuts. Don’t forget that the last cut wraps around back to the first cut.
  • Compute GCD: Compute the GCD of all the angular gaps.
  • Determine Needed Cuts: The number of slices the pizza will be divided into is 360 / GCD(gaps). If this number of slices is more than the number of premade cuts, we need to add cuts to make the slices equal.
  • Output the Number of Additional Cuts: The result is the difference between the desired number of slices and the number of premade cuts.

Complexity:

  • Time Complexity: For each test case, computing the gaps and the GCD of the gaps takes O(n) time, where n is the number of cuts.
  • Space Complexity: We use an additional array to store the gaps between cuts, which requires O(n) space per test case.