2
\$\begingroup\$

Problem statement

Consider an n-element sequence of integers, A = {a0, a0, ..., an-1}. We want to perform \$n\$ operations on \$A\$, where each operation is defined by the following sequence of steps:

  1. Remove any integer, ai, from \$A\$ and set it aside.

  2. Calculate scorek = runningSum mod ai, where 1 ≤ k ≤ n and runningSum is the sum of all the numbers removed from A during the previous k - 1 operations.

  3. Update runningSum such that runningSum = runningSum + ai, where ai is the integer that was removed from A during step 1 above.

enter image description here enter image description here

Introduction of Algorithm

The max score is the first medium level algorithm on Hackerrank Rookie 3 contest in May 5, 2017. The success rate is 14.10%, and I only scored 3.5 out of 35 points in the contest. In the contest, I did some work on recursive algorithm, but failed to implement the correct memoization, and did not know that bit mask is the solution to solve timeout issue.

After the contest I was busy to learn and teach myself. I thought that if I am a good tester, very patient to go over a few simple test cases first, I must have solved the problem.

So I like to try the idea on the algorithm after the contest. Two unit test cases are chosen, one is the array {\$1, 2\$}, and the other is {\$1,2,1\$}.

Test case {1, 2, 1}

C# code only passed first 5 test cases, timeout last 5 test cases. Source code can be looked up from the link. The solution is implemented with the correct memoization matching the recursive tree, but timeout since too many string concatenation.

Suppose that the array has three numbers, int[] numbers = new int[]{1, 2, 1}.

Calculated variable as Dictionary has the following: [0 1, 0] [0 2, 0] [0, 1] [1 2, 0] [1, 0] [2, 1] [,1]

The key is encoded using the function:

 public static string EncodeKey(HashSet<int> numbers)
 {            
    int[] sorted = numbers.ToArray(); 
    Array.Sort(sorted);
    return string.Join(" ", sorted); 
 }

Debug the code, and check how many times the dictionary is looked up. 3 times. key = "0 1", "0 2", "1 2".

Draw a recursion tree for this simple test case. Here is the graph: enter image description here

Apply bit mask technique

In order to solve time out issue, I had to use bit mask instead of using encoded key by using the above function EncodeKey with the argument HashSet numbers, apply bit mask techniques learned through top coder article called A Bit of Fun: Fun with Bits. The code is much easy to follow after I did draw recursive tree on the test case, and bit mask set operation is also easily to look up through the top coder article.

Here is C# code with those two test cases. C# code passes all test cases on Hackerrank. Please help me to be a good tester, a smart problem solver to work on basics first.

  #if DEBUG
using Microsoft.VisualStudio.TestTools.UnitTesting;
#endif

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

namespace MaxScore_usingBitArray
{
    class MaxScore_usingBitMask
    {
        /// <summary>
        /// source code reference is here:
        /// https://www.hackerrank.com/contests/rookierank-3/challenges/max-score/forum/comments/299005
        ///
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            ProcessInput();
            //RunTestcase(); 
        }       

        public static void ProcessInput()
        {
            int n = Convert.ToInt32(Console.ReadLine());

            var data = Console.ReadLine().Split(' ');
            long[] numbers = Array.ConvertAll(data, Int64.Parse);

            long maxScore = GetMaximumScore(numbers);
            Console.WriteLine(maxScore);
        }

        /// <summary>
        /// How to calculate score? 
        /// Please read the problem statement. 
        /// For test case int[]{1,2}, if first number array 1 is selected first, score 0 % 1 = 0. 
        /// Sum will be 1, and then number 2 will be scored as 1 % 2 = 1. Total score is 0 + 1 = 1. 
        /// There are 2 options to enumerate 2 numbers, maximum score is to choose maximum one of 
        /// those two options. 
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static long GetMaximumScore(long[] array)
        {            
            return getMaxScore(array, 0, array.Sum());
        }

        public static Dictionary<int, long> memo = new Dictionary<int, long>();

        /// <summary>
        /// Bit mask technique to solve timeout issue - 3 seconds time limit. 
        /// use the following article on topcoder for reference: 
        /// https://www.topcoder.com/community/data-science/data-science-tutorials/a-bit-of-fun-fun-with-bits/
        /// The following function uses an integer to represent a set, with a 1 bit representing
        /// a member that is present and a 0 bit one that is absent. 
        /// The following set operations are used in the function:
        /// Set Union  A | B
        /// Clear bit 
        /// A &= ~(1 << bit)
        /// Test bit  (A & 1 << bit) != 0
        /// </summary>
        /// <param name="numbers"></param>
        /// <param name="bitmask"></param>
        /// <param name="sum"></param>
        /// <returns></returns>
        private static long getMaxScore(long[] numbers, int bitmask, long sum)
        {
            if (memo.ContainsKey(bitmask))
            {
                return memo[bitmask];
            }

            var maximumScore = 0L;

            for (var i = 0; i < numbers.Length; i++)
            {
                var bitToCheck = 1 << i; // set ith bit

                if ((bitmask & bitToCheck) != 0) // test bit
                {
                    continue;
                }

                bitmask |= bitToCheck; // set union 

                var current = numbers[i];

                var score = ((sum - current) % current) + getMaxScore(numbers, bitmask, sum - current);

                bitmask &= ~bitToCheck; // backtracking, clear the bit - ith bit 
                maximumScore = Math.Max(score, maximumScore);
            }

            memo[bitmask] = maximumScore;

            return maximumScore;
        }
    }

#if DEBUG
    [TestClass]
    public class Test
    {
        [TestMethod]
        public void Test1()
        {                        
            var array = new long[] { 1, 2};

            MaxScore_usingBitMask.memo.Clear(); 
            long maxScore = MaxScore_usingBitMask.GetMaximumScore(array);
            System.Diagnostics.Debug.Assert(maxScore == 1); 
        }

        [TestMethod]
        public void Test2()
        {
            var array = new long[] { 1, 2, 1 };

            MaxScore_usingBitMask.memo.Clear();
            long maxScore = MaxScore_usingBitMask.GetMaximumScore(array);
            System.Diagnostics.Debug.Assert(maxScore == 1);
        }  
    }

#endif
}
\$\endgroup\$

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.