HackerRank - stone division - remove memorization, time out on test case 11 and up, play with test case 14

stoneDivision_removeMemorization_play.cs

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

namespace stoneDivisionStudyCode
{
    class Program
    {
        /*
         * Nov. 21, 2016
         * study code: 
         * https://www.hackerrank.com/contests/womens-codesprint-2/challenges/stone-division-2/editorial
         *        
         */
        public static Dictionary<long, long> dp = new Dictionary<long, long>();
        public static Dictionary<long, bool> done = new Dictionary<long, bool>();

        public static long[] arr = new long[1003];
        public static long n;
        public static int m;

        static void Main(string[] args)
        {
            //solution();
            //testCase1(); 
            //testCase14(); 
            testCase14_No10(); 
        }
        /*
         * 1
         * 12 3
         * 2  3  4
         */
        private static void testCase1()
        {
            done.Clear();

            n = 12;
            m = 3;

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

            long ans = calculateMoves(n);

            Console.WriteLine(ans);
        }

        /*
         * test case 14 - timeout
         * 377083280820 10
           1 377083280820 2 188541640410 3 125694426940 4 94270820205 5 75416656164

         */
        private static void testCase14()
        {
            done.Clear();

            n = 377083280820;
            m = 10;

            DateTime start = DateTime.Now; 
            arr = new long[10] { 1, 377083280820, 2, 188541640410, 3, 125694426940, 4, 94270820205, 5, 75416656164 };                long ans = calculateMoves(n);

            DateTime end = DateTime.Now;
            TimeSpan span = end - start;
            int ms = (int)span.TotalMilliseconds; 

            Console.WriteLine(ans);
        }

        /*
         * 868639954646 233
           1 868639954646 2 434319977323 530891011454 482765796828 700972351247 67918065459 196463964374 213294909501 735454465567 189398853644 573705235871 217126392992 859802566651 940839415523 515742715709 356451237205 235293701200 51204546308 267125726004 656960639449 533188640459 942784327636 398700507062 692992128631 491450896401 511651659083 266815917795 457927558630 471052824693 707713254256 942988769051 329191029550 38712761891 494617757008 545396056021 167830114169 763124584595 984303779921 947971088026 196305734007 872884238399 705532707484 453783784876 538546318763 846944134466 479883909800 370029246037 493301233289 577736106443 189432541648 900629182843 676539653738 632640340040 100599040638 602576772301 121388771665 78012104152 525544083102 400509940365 591345848327 88836574163 431652117046 175139938134 987161037373 560835826434 689853073650 323337532959 98332714446 975061540363 284965077758 424006904199 648884043551 22261543600 809984814574 539276066510 278051579829 63619686864 159466035025 893432143322 685861774955 250402571081 67113089873 687841351436 573245162038 405893413630 363290142955 216952413243 672143873795 972091691224 172104408633 597384940455 422769858500 448204718637 255619852545 825942990803 488285855796 544876537003 306226285635 181217486449 86398337696 715611362112 195179875279 688002288708 389352257564 412954590836 470532138677 367336305231 101937732204 309474339402 665238348778 668739257367 284396095617 460349220672 195127494842 213964813883 25095279105 895588539459 214150552019 227656647257 279323948132 128470295517 638985185114 74950211825 136380717042 648349534625 342618515632 707992593879 557317561577 254125531588 652120235237 116802103007 536409681178 435761583226 269195565350 603431054603 872282049053 997681055479 609815484867 407853164276 224714780150 257682132654 480372984598 367696271217 910705400699 368943904812 376056295265 385982165990 836807501196 652117796147 617178957223 331964100257 817487583557 35684603551 867669490719 513603222640 398138458977 497588565556 666321936856 10927183401 871912755789 447085022907 339535254068 140554857905 438434812371 496998381165 404799055757 682374581218 424399247608 966186523768 600796183101 811462470983 111062452927 398115043821 335738706583 568102657980 859907114592 79901792565 70882507873 854127604849 214545096317 667458790863 543340638340 837396286405 125740488825 132252311334 555018179194 947819654017 413406131239 330213120512 608001918113 928511514824 838482280976 994258511533 25604885752 114974737626 611982629970 821789246239 285826931754 239437386561 789345962825 57228759036 372464542938 505336354922 562465104400 729848475378 355577676669 612992312546 585292551922 549094239689 641786250114 258867302000 83254336533 119554432601 223976674198 500175393185 839633282496 700236992597 786819737984 351443182664 407295044581 392097937177 192736216033 63444324627 590205418516 991056858857 167337658077 44920932881 778413117529 253153174212 831521750100 704826746967 
         */
        private static void testCase14_No10()
        {
            done.Clear();

            n = 868639954646;
            m = 233;

            string noString = @"1 868639954646 2 434319977323 530891011454 482765796828 700972351247 67918065459 196463964374 213294909501 735454465567 189398853644 573705235871 217126392992 859802566651 940839415523 515742715709 356451237205 235293701200 51204546308 267125726004 656960639449 533188640459 942784327636 398700507062 692992128631 491450896401 511651659083 266815917795 457927558630 471052824693 707713254256 942988769051 329191029550 38712761891 494617757008 545396056021 167830114169 763124584595 984303779921 947971088026 196305734007 872884238399 705532707484 453783784876 538546318763 846944134466 479883909800 370029246037 493301233289 577736106443 189432541648 900629182843 676539653738 632640340040 100599040638 602576772301 121388771665 78012104152 525544083102 400509940365 591345848327 88836574163 431652117046 175139938134 987161037373 560835826434 689853073650 323337532959 98332714446 975061540363 284965077758 424006904199 648884043551 22261543600 809984814574 539276066510 278051579829 63619686864 159466035025 893432143322 685861774955 250402571081 67113089873 687841351436 573245162038 405893413630 363290142955 216952413243 672143873795 972091691224 172104408633 597384940455 422769858500 448204718637 255619852545 825942990803 488285855796 544876537003 306226285635 181217486449 86398337696 715611362112 195179875279 688002288708 389352257564 412954590836 470532138677 367336305231 101937732204 309474339402 665238348778 668739257367 284396095617 460349220672 195127494842 213964813883 25095279105 895588539459 214150552019 227656647257 279323948132 128470295517 638985185114 74950211825 136380717042 648349534625 342618515632 707992593879 557317561577 254125531588 652120235237 116802103007 536409681178 435761583226 269195565350 603431054603 872282049053 997681055479 609815484867 407853164276 224714780150 257682132654 480372984598 367696271217 910705400699 368943904812 376056295265 385982165990 836807501196 652117796147 617178957223 331964100257 817487583557 35684603551 867669490719 513603222640 398138458977 497588565556 666321936856 10927183401 871912755789 447085022907 339535254068 140554857905 438434812371 496998381165 404799055757 682374581218 424399247608 966186523768 600796183101 811462470983 111062452927 398115043821 335738706583 568102657980 859907114592 79901792565 70882507873 854127604849 214545096317 667458790863 543340638340 837396286405 125740488825 132252311334 555018179194 947819654017 413406131239 330213120512 608001918113 928511514824 838482280976 994258511533 25604885752 114974737626 611982629970 821789246239 285826931754 239437386561 789345962825 57228759036 372464542938 505336354922 562465104400 729848475378 355577676669 612992312546 585292551922 549094239689 641786250114 258867302000 83254336533 119554432601 223976674198 500175393185 839633282496 700236992597 786819737984 351443182664 407295044581 392097937177 192736216033 63444324627 590205418516 991056858857 167337658077 44920932881 778413117529 253153174212 831521750100 704826746967";

            
            DateTime start = DateTime.Now;

            arr = Array.ConvertAll(noString.Split(' '), long.Parse);             

            long ans = calculateMoves(n);

            DateTime end = DateTime.Now;
            TimeSpan span = end - start;
            int ms = (int)span.TotalMilliseconds;

            Console.WriteLine(ans);
        }
        /*
         * Nov. 22, 2016
         * recurisve function
         * 
         * how to mkae it easy to construct the recursive function? 
         * The formula - 
         * If there are 12 nodes in a pile, then, if choose 3, divide into 3 piles, 
         * how many in each pile? pile/ runner
         * So, the task to calculate how many moves there is:
         * 1. divide once, 1
         * 2. plus 3 piles, for each pile to handle the same task 
         * 
         * Oh, do not get lost! Julia
         * 
         * one more thing, using memorization. 
         * declare an arary d[] = new int[1003], save the result
         * extra dictionary to look up if it is calculated. 
         */
        private static long calculateMoves(long pile)
        {           
            long ans = 0;
            for (int i = 0; i < m; i++)
            {
                long runner = arr[i];
                if (pile % runner == 0 &&
                    (pile / runner) > 1)
                {
                    ans = Math.Max(ans, 1 + ((pile / runner) * calculateMoves(runner)));
                }
            }           

            return dp[pile] = ans;
        }

        /*
         * Nov. 22, 2016
         */
        private static void solution()
        {

            int q = int.Parse(Console.ReadLine());

            for (int k = 0; k < q; k++)
            {               
                string[] nAndm = Console.ReadLine().Split(' ');

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

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

                long ans = calculateMoves(n);

                Console.WriteLine(ans);
            }
        }
    }
}