Connection Status:
Competition Arena > DrawingPointsDivOne

DrawingPointsDivOne

SRM 560 · 2012-06-05 · by meret

SRM 560 · 2012-06-05 · by meret · Simple Search, Iteration
Class Name: DrawingPointsDivOne
Return Type: int
Method Name: maxSteps
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

This problem statement contains images. It may not display properly outside the applet.

Once upon a time, Little Wojtek had drawn a number of points with integer coordinates onto a sheet of paper. Then he made zero or more steps. Each step looked as follows: Let's call all the points on Wojtek's paper old points. For every four old points that formed the vertices of a 1x1 square, Wojtek would draw a point in the middle of that square. Once he had drawn all such new points, he took an eraser and erased all the old points.


An example is shown in the picture below. On the left is Wojtek's original paper. In the middle is the same paper with the new points filled in. (For clarity, the old points are black and the new ones are red.) On the right is the paper after the old points were erased.


   


He has been playing for a while when he was called downstairs to dinner. He looked at the paper with a surprised face and wondered how many steps he had made.


You are given two int[]s x, y of some equal length n. They describe all of the points that were drawn by Wojtek in the last step of his play. More precisely, you may assume that there are real numbers (not necessarily integers) dy and dx such that the following holds:

  • For each i between 0 and n-1, there is a point at coordinates (dx+x[i], dy+y[i]).
  • There are no other points anywhere on the paper, only those that follow from the previous statement.


Return the maximum number of steps Wojtek could have made. If there is no maximum (that is, if the number of steps can be arbitrarily large), return -1 instead.

Notes

  • Note that the points drawn by Wojtek in the last step of his play could have non-integer coordinates.
  • The paper used by Wojtek could have been arbitrarily large. In other words, ignore the paper size, it does not limit the number of steps in any way.

Constraints

  • x will contain between 1 and 50 elements, inclusive.
  • x and y will contain the same number of elements.
  • Each element of x will be between -70 and 70, inclusive.
  • Each element of y will be between -70 and 70, inclusive.
  • No two points described by x and y will be the same.
Examples
0)
{0, 3}
{0, 0}
Returns: 1

An example scenario: Wojtek draws the initial points at locations (100, 100), (100, 101), (101, 100), (101, 101), (103, 100), (104, 100), (103, 101), (104, 101), (315, 714). In the first and only step, Wojtek draws points at locations (100.5, 100.5) and (103.5, 100.5). These locations correspond to x and y in this test case.

1)
{0,2}
{0,0}
Returns: 0
2)
{-70}
{3}
Returns: -1
3)
{-41,-40,1,-11,-32,-7,24,-11,49,-15,-22,20,-8,54,54,69,16,-30,36,-6,-30,40,64,20,-66,
 -37,-33,-18,-35,36,9,61,-43,45,5,60,-8,-58,65,-66,41,12,34,-11,-57,-38,46,63,-55,3}
{5,-24,-2,-4,23,14,1,70,-26,45,15,48,32,-41,54,-47,-67,-46,-9,-53,54,28,-61,11,53,68,
 -33,62,37,-8,-17,-17,48,19,-49,56,-41,16,17,-50,28,59,10,50,23,-16,56,31,-70,-44}
Returns: 9
4)
{39,39}
{50,26}
Returns: 22

Submissions are judged against all 136 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DrawingPointsDivOne with a public method int maxSteps(vector<int> x, vector<int> y) · 136 test cases · 2 s / 256 MB per case

Submitting as anonymous