Remove the minimum number of blades.

Question

I recently ran into this issue on a Timus online judge . For people, I don’t want to click on the link. The question is this:

Experienced participants in the Urals Championship come to Yekaterinburg in advance to get used to the harsh weather conditions, take a walk around the city and, of course, visit Limpopo Waterpark. Few people know that there is a plant number 404 near the water park, and this plant is called "Error 404" by the locals. the plant is not easy to find, and even harder to find out what happens there. Fortunately, you can watch the factory from the nearby pedestrian bridge. Due to the apparent silence and desolation of the plant, one might think that it was out of order, But this is not so. The main working area of ​​the plant is the repair of aircraft engines. Some time ago, the plant received an order to repair a broken gas turbine engine. It turned out that some blades were torn, which led to excessive load on the motor shaft. Experts at the plant decided that the engine could be quickly repaired by removing some of the undamaged blades, so that the center of mass of the remaining blades would again be on the axis of rotation. To keep engine power as large as possible, a minimum number of blades must be removed. At least one blade must be left, otherwise the engine will not work at all. Experts say that when all the blades were intact, their end points formed a regular n-gon. Tell them which blades should be removed.

> Input The first line contains the initial number of blades in the > turbine n and the number of torn blades k (3 ≤ n ≤ 20000; 1 ≤ k ≤ n − > 1). The integer n has at most two distinct prime divisors. The next > line contains k integers, which are the numbers of the torn blades in > ascending order. The blades are numbered from 1 to n clockwise. Output > In the first line output the minimum number of blades that should be > removed. In the second line output the numbers of these blades in any > order separated with a space. If several answers are possible, output > any of them. If it is impossible to repair the engine by removing some > of the blades, output "−1". > 

I am having trouble setting up this issue. My initial thought is that since the center of mass needs to be restored, a broken blade should be surrounded by an equal number of unbroken blades.

So, if we represent a broken blade as 0 and a continuous blade as 1, a specific configuration can be represented as: 011

I'm not sure that I am on the right track, and some of the reviews will be awesome, trying to understand this problem.

thanks

Answer 1

The ends of the blades initially formed a regular n gon. Visualize them as complex numbers. Without loss of generality, the radius is 1, the axis is at the origin, and the tip of the blade with number n is 1.

The tip of the blade represents the nth root of the unit, the tip of the blade k is in

 z_k = e^(2\pi i * k/n) 

The center of mass after removal of the blades k1, ... , kr is on the axis of rotation if and only if

 z_k1 + z_k2 + ... + z_kr = 0 

Now let 1 < d < n be the divisor of n . The blades k1 + m*d, 0 <= m < n/d form the vertices of a regular n/d -gon. Thus, their removal leaves the center of mass on the axis of rotation.

The strategy is to try to cover the list of indices of broken blades with a set of disjoint regular d_i , where d_i is the divisor n . So, in the list, find the pairs whose indices differ by the divisor n .

Answer 2

My initial thought is that since the center of mass needs to be restored, a broken blade should be surrounded by an equal number of unbroken blades.

Not. The propeller must be rotationally symmetrical. If one blade is torn by a 3-blade propeller, there is no way to re-enable it.

Key points are:

• Experts say that when all the blades were intact, their end points formed a regular n-gon.

• The integer n has at most two different prime divisors.

Start with something simple that works for these two properties, such as the decagon. Ask yourself: how do polygons and symmetry relate? How are the divisors of 10 then related to polygons and symmetry? To simplify things, can you imagine these polygons using scalars rather than two-dimensional points? Hint: modular arithmetic plays a solution.

Photographs of blade configurations (both non-fixed and fixed) should help. For example:

  2 2 2 2           
     3 1 1                                                 
   4 0 4 0 4 0 4 0     

   5 9 5 9 5 9     
     6 8 6 8 6 8 8       
         7 7 7 7           
    whole 10-gon 2 broken blades 3 broken blades 3 broken blades

There are two possible solutions for 2 broken blades and the first 3 broken knives, although only one is optimal for each of them. The second 3-broken has one solution. Look for polygons.

Answer 3

This problem is really very complicated mathematically, but it can be simplified with a good understanding of how balancing works.

• If the number of blades “n” is a prime number, there is no other solution than removing each blade. You cannot rebalance even one missing blade when n is simple. If there is no solution for one blade, there will be no solution for several missing ones.
• The number of blades "n" is not simple, by definition (and by the rule of this problem) it is the product of two primes "p1" and "p2", for example: for 21 blades, p1 = 3, p2 = 7.

If one blade “k1” is missing, a balance will be obtained if the total of “N / p2 (example = 3) blades are equally spaced (visualize the Mercedes Benz mark). If two blades“ k1 ”and“ k2 ”are missing, a balance will be obtained. making it for "k2" as the previous case, EXCEPT if k1 and k2 are located at a distance of "p1" or the symmetry of "p2"

Examples with 12 and 20 blades complicate the task because they are multiples of 4, which means two symmetries of order 2. I prefer examples with 21 blades that do not have this problem.

• 21 Blades, one missing blade k1 = 1 → Balance is obtained by removing blades 8 and 15 (Symmetry p1 - order 3)
• 21 Blades, two missing blades k1 = 1, k2 = 2 → Balance is obtained by removing blades 8 and 15 for k1 and 8 and 16 for k2
• 21 Blades, two missing blades k1 = 1, k2 = 8 →, since k2-k1 = 7, you just need to remove blade 15 to complete the balance.
• 21 Blades, two missing blades k1 = 1, k2 = 7->, since k2-k1 = 6 = 2 * 3, you can notice that the blades are on symmetry of order 7, so you can complete the picture by removing the blades 4.10 , 13,16,19 to get the perfect balance. But interestingly, you can also consider it as an example of No. 2 and use twice the symmetry of order 3; therefore, there is also a solution by removing blade 8 and 15 for balance k1 and 14 and 21 for balance k2.

Therefore, to solve your problem, your algorithm should do the following: - If n is simple, simply print "-1" - there is no solution - After starting the first missing blade, scan the groups of missing blades separated by "n / p1 (= 7)" and "n / p2 (= 3)". Count how many groups of each symmetry group and how many blades you need to replace.

• In this example, your first order solution is simple:
  The number of removed blades will be (the number of symmetry groups p1) * 7 + (The number of symmetry groups p2) * 3 - the number of missing blades. You will have to handle the exceptions, as shown in Example 4, where it is better to treat the blades individually, but you get an image.