CPMagical CP Library

Problem solution · Python

CCC 2013 S5 - Factor Solitaire

CCC 2013 S5 - Factor Solitaire: a Python solution using binary search. Learn the idea, check the complexity, and read the full code, with credit to CCCSolutions.

Technique
Binary search
Source
CCCSolutions
Length
79 lines
Start with the idea.

Try the problem first. If you get stuck, read the approach below, then write your own solution. The full code is at the bottom.

Approach

Binary search

For CCC 2013 S5 - Factor Solitaire, the implementation exploits a monotonic condition to discard half of the remaining search space after every check.

  1. Identify the ordered answer range or sorted search domain.
  2. Write a predicate whose truth changes only once.
  3. Move the appropriate boundary after each midpoint check and return the final feasible position.

Code notes

  • 79 lines of Python from the credited upstream file ccc13s5.py.
  • The implementation keeps its working state in language-native values and containers.
  • No explicit loop blocks detected.

Complexity

Multiply the logarithmic number of midpoint checks by the cost of one predicate evaluation.

Check the problem constraints before deciding whether this complexity will pass.

Source

Code and credit

This code comes from CCCSolutions by CCCSolutions contributors · Milliken Mills High School and is used under the MIT licence.

Open problem ↗Original source ↗
Full codeCCC 2013 S5 - Factor Solitaire · PythonPython
Use this to learn the idea, then write your own version.
# CCC 2013 Senior 5: Factor Solitaire## The method is RIDICULOUSLY simple. Work BACKWARDS from the number.## How did I think of this?## The straight forward method of factoring completely# all the numbers up to 5,000,000 is simply too slow.## I studied the examples given. The numbers along the way to# the solution looked totally random. Why choose those ones?# There was no obvious answer. Eg why go from 60 to 61 at a huge cost# when one was so far from the end point?## I used my first program and printed the minimum cost for all #s up to 100.# Very quickly I noticed that the powers of 2 were VERY cheap. So too were# the numbers between them. Could I use some sort of modified binary search# system to get to my number? A few example cases proved this didn't work.## I returned to the 2013 example. I noticed the when I factored the# last number (2013 = 3 * 671) I got numbers that were added to get# from 1342 to 2013. Why would that even work?# If you factor a number, SUBTRACT one of the factors, what guarantee was# there that you'd end up on a number that also had those factors? (So you# could add them and get back to the first.) That was NOT at all obvious# to me. That's why my score on the contest would be about 30 and not 75 :-)## Okay, so 2013 has a factor of 671, what makes you think that the number# (1342 = 2013-671) would also have a factor of 671? (and even if this was,# why would this be the minimum cost route to the number?)## Answer: multiplication means repeated addition!# Since 2013 = 3 * 671, if you subtract 671 you are left with 2*671 or 1342.# This DOES have the same factor (671)! AND you get it at a minimum cost.## Repeat the process till you're back to 1 and QED!## The only fly in the ointment is when you hit a prime....# You can't go back from there as there are no factors, so subtract 1# (at a huge cost) and then keep going.## Here'a a trace for N = 15##   N  factors  what_to_subtract newN  newN_factors      cost#  15   3 * 5         5           10      2 * 5           2#  10   2 * 5         5            5      1 * 5         2+1=3#   5   prime!        1            4      4 * 1         3+4=7#   4   2 * 2         2            2      1 * 2         7+1=8#   2   prime!        1            1      1 * 1         8=1=9## min (15) = 9## I'm still fuzzy as to why this does give the minimum cost overall, but# IT WORKS, so please do NOT tell me why, I like the mystery and as a CS# person, all I really care about is HOW to make it work, not WHY. :-)  import math file = open("s5.15.in", 'r')N = int(file.readline().strip()) cost = 0while N > 1:    # find the first pair of factors of N (eg for 24 it's 2*12)    r = int(math.sqrt(N)) + 1    f = 2    while f <= r and N % f != 0:         f = f + 1         if f < N and N % f == 0: # its a real factor and N is not prime        x = N / f        N = N - x        cost = cost + N / x     else:                    # if N is prime, go back only 1        N = N - 1        cost = cost + Nprint cost

Keep practising

Did this explanation save you time? I'm a Grade 11 student building this free library to make difficult algorithms easier to understand.

Buy me a coffee ↗