Idea
- The idea here is create a matrix with minimum rows at every round, so we are able to get the maximised value from the number of columns
- So assume we have
npebbles, the matrix is going to beab, whereais the number of rows andbis the number of column. And bothaandbare positive integers and are divisors ofn - So the goal now is to find the smallest
aaka the smallest divisor ofnaka the smallest Prime Number (质数) of the group of prime numbers that compositesn - The quotient of
nis the number of columns aka the number of pebbles we gain and can be used in the next round - We repeat this until
nis 1 or less
Space & Time Analysis
The analysis method we are using is Algorithm Complexity Analysis
Space - O(1)
- Ignore input size & language dependent space
- Not creating any objects on the Heap Segment
Time - O(?)
- I am not too sure, requires more readings on the time complexity of finding the next prime number
- But the solution takes
590 msto complete on codeforces
Codes
1st Attempt (Java)
Personal Reflection
- Why it takes so long to solve: NIL
- What you could have done better: Be more familiar with Number Theory
- What you missed: NIL
- Ideas you’ve seen before: Prime Number (质数)
- Ideas you found here that could help you later: Abstracting the problem into the a form that I can apply number theory concepts like Prime Number
- Ideas that didn’t work and why: NIL