1
\$\begingroup\$

Problem statement

You have a pile of n stones that you want to split into multiple piles, as well as a set, S, of m distinct integers. We define a move as follows:

  • First, choose a pile of stones. Let's say that the chosen pile contains y stones.

  • Next, look for some x in S such that x<>y and y is divisible by x (i.e., x is a factor of y); if such an x exists, you can split the pile into x/y equal smaller piles.

You are given q queries where each query consists of n and S. For each query, calculate the maximum possible number of moves you can perform and print it on a new line.

Input Format

The first line contains an integer,q, denoting the number of queries. The 2*qsubsequent lines describe each query in the following format:

  1. The first line contains two space-separated integers describing the respective values of n (the size of the initial pile in the query) and m (the size of the set in the query).

  2. The second line contains distinct space-separated integers describing the values in set S.

Constraints

  • 1 <= q <= 10

  • 1 <= n <= 1012

  • 2 <= m <= 1000

  • 1 <= si <= 1012

Output Format

For each query, calculate the maximum possible number of moves you can perform and print it on a new line.

Sample Input 0

1

12 3

2 3 4

Sample Output 0

4

Explanation 0

Initially there is a pile with 12 stones:

enter image description here

enter image description here

My introduction of the algorithm

The algorithm is one of medium level algorithm in hackerrank woman codesprint in Nov., 2016. It can be solved using recursive function and memorization.

In the contest, I did not write the recursive function because I overcooked the solution, ended up with a few hours scoring 0 from maximum score 50. I learned the lesson, write less code, avoid complicated code, think recursively. And I documented the study how to think recursively and tried to learn the simple recursive function.

After 3 months of the contest, I reviewed the algorithm again, and spent one hour to rewrite the C# code based on one of submissions I studied 3 months ago. Please help me review the algorithm.

The C# code passes all test cases using hackerrank online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace stoneDivisionStudyCode
{
    /*
    * 
    * Problem statement:
    * https://www.hackerrank.com/contests/womens-codesprint-2/challenges/stone-division-2
    *        
    */
    class StoneDivsion
    {
        public static Dictionary<long, long> memo = new Dictionary<long, long>();

        static void Main(string[] args)
        {
            ProcessInput();
            //RunTestcase(); 
        }

        public static void ProcessInput()
        {
            int queries = int.Parse(Console.ReadLine());

            for (int query = 0; query < queries; query++)
            {
                memo.Clear();

                string[] input = Console.ReadLine().Split(' ');

                long n = long.Parse(input[0]);
                int m = int.Parse(input[1]);

                long[] predefinedSet = new long[1003];

                predefinedSet = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);

                long answer = CalculateMaximumPossibleMoves(n, predefinedSet, m);

                Console.WriteLine(answer);
            }
        }

        /*
         * 1
         * 12 3
         * 2  3  4
         * Go over problem statement and explanation 
         * of sample test case
         */
        public static void RunTestcase()
        {
            memo.Clear();

            long n = 12;
            int m = 3;

            var predefinedSet = new long[3] { 2, 3, 4 };

            long answer = CalculateMaximumPossibleMoves(n, predefinedSet, m);

            Debug.Assert(answer == 4);
        }

        /*
        * Recursive and memorization two techniques                                   
        *             
        * Recursive function design - 
        * 
        * Timeout issue - using memorization
        * maximum size of integers < 1000
        * 1 <= m <= 1000 
        */
        public static long CalculateMaximumPossibleMoves(
            long pile,
            long[] predefinedSet,
            int sizeOfPredefinedSet)
        {
            // look up memorization dictionary 
            if (memo.ContainsKey(pile))
            {
                return memo[pile];
            }

            // go over all possible options to find maximum number of moves
            long maximumNumberOfMoves = 0;
            for (int i = 0; i < sizeOfPredefinedSet; i++)
            {
                long divisor = predefinedSet[i];

                if (pile % divisor != 0 || (pile / divisor <= 1))
                {
                    continue;
                }

                // solve a subproblem using recurisve function - a small pile
                long numberOfMoves = CalculateMaximumPossibleMoves(divisor, predefinedSet, sizeOfPredefinedSet);

                // how many piles - count in the factor of piles
                // first divide into small piles, then each small pile will be processed. 
                numberOfMoves = 1 + (pile / divisor) * numberOfMoves;

                // keep the maximum one only
                maximumNumberOfMoves = Math.Max(maximumNumberOfMoves, numberOfMoves);
            }

            memo[pile] = maximumNumberOfMoves;

            return maximumNumberOfMoves;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ I am learning recursive function. Please help! I like to share the blog I wrote in Nov. 2016 how I studied recursive function after the contest, and then found the website codereview.stackexchange.com through the study. I choose to share it in the comment instead of question, because some people may find it unrelated. :-) juliachencoding.blogspot.ca/2016/11/… \$\endgroup\$ – Jianmin Chen Feb 24 '17 at 7:41
  • \$\begingroup\$ If the code passes all test cases, why have you tagged the question as time-limit-exceeded? \$\endgroup\$ – 200_success Feb 24 '17 at 8:43
  • \$\begingroup\$ The code I asked for review is my third practice, because the time limited is 3 seconds for the algorithm in the contest in general on hackerrank, the size of q, n, m make a lot of implementation time-out, use recursive function with memorization will not time out. Otherwise, no need to use memorization. Hopefully, I understand your question. \$\endgroup\$ – Jianmin Chen Feb 24 '17 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.