CCO '17 P2 - Cartesian Conquest

View as PDF
Submit solution
Points: 20 (partial)
Time limit: 1.0s
Memory limit: 1G
Author:
Eliden
Problem type
Canadian Computing Olympiad: 2017 Day 1, Problem 2

Long ago, in the land of Cartesia, there ruled the Rectangle Empire. The Empire was large and prosperous, and it had great success with expanding its territory through frequent conquests. The citizens of this ancient civilization followed many curious customs. Unfortunately, the significance of these are now shrouded in mystery.

The Rectangle Empire operated under a system of rectangular districts. These districts were carefully managed to meet three special criteria.

  1. The Empire's territory is divided into districts such that each piece of land controlled by the Empire belongs to exactly one district.
  2. The boundaries of the districts, when viewed on a map, must be rectangles such that the length of the longer side of the rectangle is twice the length of the shorter side.
  3. The side lengths of the districts must be integers, when measured in \Xi (note that \Xi was the primary unit of length in the Rectangle Empire).

When the empire was first established, it consisted of a single district. Since then, the empire has gained additional districts through conquest of neighbouring regions. Whenever the empire gained control over a new region of land, they always established a single new district using that exact land. This means that the empire was always mindful about the geometric properties of the land they were hoping to conquer. You can assume that no two of these conquests occurred at the same time.

The addition of new districts was the only way that the boundaries of the empire ever changed. Furthermore, each district, once added, was never modified or merged with another.

The final, most important tradition of the Rectangle Empire was to make sure that the overall territory of the empire was always a rectangle, though it did not necessarily need to satisfy the 2:1 ratio for the side lengths that individual districts satisfy.

Recently, archeologists have discovered that at one point in time, the empire had dimensions N by M (measured in \Xi). You need not be alarmed if these numbers are very large; after all, Cartesia is an infinite plane. Your task is to estimate the number of districts in the empire when it was at this size. Over all possible ways that the empire was founded and expanded, what is the minimum and maximum number of districts?

Input Specification

The input will be a single line, containing two integers N and M (1 \le N, M \le 10^8).
For 5 of the 25 marks available, N, M \le 1\,000.
For an additional 8 of the 25 marks available, N, M \le 10^6.

Output Specification

Output a single line, containing the minimum number of districts, followed by a space, followed by the maximum number of districts.

Sample Input

10 6

Sample Output

5 8

Explanation of Sample Output

The illustrations below show how this minimum and maximum number of districts could have been achieved. Districts are labelled \#1, \#2, \#3, \dots giving the order in which they were added to the region. The dimensions of each district are shown in brackets as (k \times 2k) or (2k \times k):


Comments


  • 0
    Kirito  commented on May 27, 2017, 8:59 p.m.

    New case was added by d, and the batches were weighted.

    Batches are now:

    • 5/25
    • 8/25
    • 11/25
    • 1/25

  • -20
    Eliden  commented on May 18, 2017, 4:12 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 22
      kobortor  commented on May 19, 2017, 1:15 a.m. ← edited

      Bonus Challenge: Find the worst case complexity of the problem.

      Edit: enter image description here


      • 3
        Eliden  commented on May 20, 2017, 7:45 p.m. ← edited

        If anyone is wondering, I've found a good way to approach calculating the worst case time complexity. Although the best upper bound I've proven is O\left(N^{0.915}\right), I expect that the correct exponent is slightly lower, perhaps under 0.9.

        Update: I wrote a program that eventually gave a significantly tighter bound: an exponent of roughly 0.8.


  • -3
    zadrga  commented on May 14, 2017, 9:05 a.m. ← edited

    Why can't we divide rectangle 3-6 to nine 1-2 rectangles (for maximum number of rectangles)?


  • 1
    koosaga  commented on May 14, 2017, 6:43 a.m. ← edited

    What happens if N = 3, M = 5? I think there are no possible ways.


    • 5
      FatalEagle  commented on May 15, 2017, 9:21 p.m.

      The story implies that the input guarantees that this is always possible.