UVa 10706. Number Sequence with F#

This post describes an algorithm to solve UVa 10706: Number Sequence problem from UVa OJ. Before outlining the algorithm, we first give an overview of this problem in the next section.

Interpretation

This is a straight-forward problem, which however, requires careful introspection. Our objective is to write a program that compute the value of a sequence , which is comprised of the number groups . Each consists of positive integers written one after another and thus, the first digits of are —

11212312341234512345612345671234567812345678912345678910123456789101112345678910

It is imperative to note that, the value of has the following range . Realize that, the maximum value of is indeed Int32.MaxValue. In the provided test cases, the values of are stated. We simply have to compute ; therefore, we are required to write a function that has following signature: . That is —

f: 10 --> S.[10] = 4
f: 8  --> S.[8]  = 2
f: 3  --> S.[3]  = 2

Note also that the maximum number of test cases is 25. Question for the reader: What is the maximum possible value of for the specified sequence , which is constituted of ?

We hope that by this time, it is clear where we are headed towards. In next section, we outline an algorithm to solve this problem. But, before moving further, we would like to recommend you to try to solve it yourselves first and then, read the rest of the post. By the way, we believe that the solution that we have presented next can be further optimized (or, even a better solution can be derived). We highly welcome your feedback regarding this.

Algorithm

Recall that, is constituted of number groups . In order to identify the digit located at the position of , we first determine the number group that digit is associated with and then, we figure out the digit from .

To do so, we first compute the length of each number group . Consider the number group till —

112123123412345123456…12345678910

As mentioned, this sequence is basically constituted of as shown below (with their respective lengths).

1                    --> 1 
1 2                  --> 2 
1 2 3                --> 3
1 2 3 4              --> 4
1 2 3 4 5            --> 5
1 2 3 4 5 6          --> 6
1 2 3 4 5 6 7        --> 7
1 2 3 4 5 6 7 8      --> 8
1 2 3 4 5 6 7 8 9    --> 9
1 2 3 4 5 6 7 8 9 10 --> 11

It implies that the length of can be computed from the length of as shown below.

Using Eq.1, we calculate the cumulative sum of each number group as follows.

Why do we calculate cumulative sum? The purpose in this is to be able to simply run a binary search to determine which number group the digit belongs to in time. For example, consider i=40.

1                    --> 1 
1 2                  --> 2 
1 2 3                --> 6 
1 2 3 4              --> 10
1 2 3 4 5            --> 15
1 2 3 4 5 6          --> 21
1 2 3 4 5 6 7        --> 28
1 2 3 4 5 6 7 8      --> 36 
1 2 3 4 5 6 7 8 9    --> 45
1 2 3 4 5 6 7 8 9 10 --> 56

Using binary search, we can find out that contains the digit. Then, using a linear search, we can simply derive the first four digits of to eventually find out the corresponding digit, 4.

Similarly, for i=55, we can figure out that the digit is indeed 1.

Implementation

Next, we outline a F# implementation of the stated algorithm. We start with computing the cumulative sums of the lengths as follows. Continue reading “UVa 10706. Number Sequence with F#”

UVa 136. Ugly Numbers

This blog-post is about UVa 136: Ugly Number, a trivial, but interesting UVa problem. The crux involves computing 1500^th Ugly number, where a Ugly number is defined as a number whose prime factors are only 2, 3 or 5. Following illustrates a sequence of Ugly numbers:

1,2,3,4,5,6,8,9,10,12,15...

Using F#, we can derive 1500^th Ugly Number in F#’s REPL as follows.

	seq{1L..System.Int64.MaxValue}
	\|> Seq.filter (isUglyNumber)
	\|> Seq.take 1500
	\|> Seq.last

view raw gistfile1.fs hosted with ❤ by GitHub

In this context, the primary function the determines whether a number is a Ugly number or not–isUglyNumber–is outlined as follows. As we can see, it is a naive algorithm that can be further optimized using memoization (as listed here).

	(*
	* :a:int64 -> b:bool
	*)
	let isUglyNumber (x:int64) :bool =
	let rec checkFactors (n_org:int64) (n:int64) lfactors =
	match n with
	\| 1L -> true
	\| _ ->
	match lfactors with
	\| [] -> false
	\| d::xs ->
	if isFactor n d then
	checkFactors n_org (n/d) lfactors
	elif n > d then
	checkFactors n_org n xs
	else
	false

	checkFactors x x [2L;3L;5L]

view raw gistfile1.fs hosted with ❤ by GitHub

After computing the 1500^th Ugly number in this manner, we submit the Java source code listed below. For complete source code. please visit this gist. Alternatively, this script is also available at tryfsharp.org for further introspection.

	class Main {
	public static void main(String[] args) {
	System.out.println("The 1500'th ugly number is 859963392.");
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Please leave a comment in case of any question or improvement of this implementation. Thanks.

UVa 371. Ackermann Function

The underlying concepts of UVa 371: Ackermann Functions have been discussed in great details in our post of Collatz problem. In this post, we simply outlines an ad-hoc algorithm as a solution to this problem as follows.

	import java.io.PrintWriter;
	import java.util.Scanner;

	public class Main {
	private final Scanner in;
	private final PrintWriter out;

	private final static int _MaxValue = 1000000;
	private final static long[] memo = new long[_MaxValue];

	public Main() {
	in = new Scanner(System.in);
	out = new PrintWriter(System.out, true);
	}

	public Main(Scanner in, PrintWriter out) {
	this.in = in;
	this.out = out;
	}

	private static long[] getInts(String input) {
	String[] ints = input.trim().split(" ");
	long[] rets = new long[2];

	rets[0] = Long.parseLong(ints[0]);
	rets[1] = Long.parseLong(ints[1]);

	return rets;
	}

	private void solveAckermannProblem(long from, long to) {
	long maxValue = from;
	long maxLength = 0;

	for (long i = from; i <= to; i++) {
	long length = computeCycleLength(nextAckermannNumber(i));
	if (maxLength < length) {
	maxValue = i;
	maxLength = length;
	}
	}

	out.println(String
	.format("Between %d and %d, %d generates the longest sequence of %d values.",
	from, to, maxValue, maxLength));
	}

	private static long computeCycleLength(long n) {
	if (n == 0)
	return 0;

	if (n == 1)
	return 1;

	if (n < _MaxValue && memo[(int) n] != 0)
	return memo[(int) n];

	long len = 1 + computeCycleLength(nextAckermannNumber(n));// computing
	// length of
	// Ackermann
	// sequence

	if (n < _MaxValue) // storing it in cache
	memo[(int) n] = len;

	return len;
	}

	public static long nextAckermannNumber(long n) {
	if (n % 2 == 0)
	return n / 2;
	else
	return n * 3 + 1;
	}

	public void run() {
	while (in.hasNextLine()) {
	long[] range = getInts(in.nextLine());

	if ((range[0] == 0) && (range[1] == 0))
	break;

	long from = Math.min(range[0], range[1]);
	long to = Math.max(range[0], range[1]);

	solveAckermannProblem(from, to);
	}
	}

	public static void main(String[] args) {

	Main solver = new Main();
	solver.run();
	}

	}

view raw UVa371.java hosted with ❤ by GitHub

Please leave a comment if you have any question regarding this problem or implementation. Thanks.

The following Java code snippet outlines an algorithm using dynamic programming to solve this problem. Notice that the function solveLuggageProblem applies a bottom-up DP to construct dpTable. The boolean value of each dpTable[i][j] implies that whether it is possible to achieve weight j from the weights of 1..i suitcases. In this way, it determines whether halfWeight — the half of the total weights (of the suitcases)– can be derived from using 1..n suitcases, i.e., whether the weights of suitcases can be distributed equally into the boots of two cars.

	import java.io.PrintWriter;
	import java.util.Scanner;

	class Main {

	private final Scanner in;
	private final PrintWriter out;

	public Main(){
	in = new Scanner(System.in);
	out = new PrintWriter(System.out, true);
	}

	public Main(Scanner in, PrintWriter out){
	this.in = in;
	this.out = out;
	}

	private static int[] readLineAsIntegers(String input){
	String [] ints = input.trim().split(" ");
	int [] rets = new int[ints.length];

	for (int i = 0 ;i < ints.length; i++)
	rets[i] = Integer.parseInt(ints[i]);

	return rets;
	}

	private String solveLuggageProblem(int[] weights){
	final String _TRUE = "YES";
	final String _FALSE = "NO";

	int totalWeight = getTotalWeight(weights);

	if (totalWeight%2 != 0)
	return _FALSE;

	int n = weights.length+1;
	int halfWeight = totalWeight/2;

	boolean [][] dpTable = new boolean [n][halfWeight+1];

	// Base case 1: weights = 0 for all n --> True
	for(int i = 0;i<n;i++)
	dpTable[i][0] = true;

	// Base case 2: weights !=0 for all n=0 --> False
	for(int i = 1;i<halfWeight+1;i++)
	dpTable[0][i] = false;

	for (int i = 1; i< n; i++ ){

	for (int j = 1; j< halfWeight+1; j++){

	int w_i = weights[i-1]; // weight of ith item

	if(j<w_i) // this item can't be included since its over the limit:j
	dpTable[i][j] = dpTable[i-1][j];
	else
	dpTable[i][j] = dpTable[i-1][j] \|\| dpTable[i-1][j-w_i];
	}
	}

	return dpTable[n-1][halfWeight]==true?_TRUE:_FALSE;

	}

	private int getTotalWeight(int[] weights) {
	int totalWeight = 0;
	// compute total weight of the bags
	for(int indx =0;indx< weights.length;indx++){
	totalWeight += weights[indx];
	}
	return totalWeight;
	}

	public void run(){
	final int T = Integer.parseInt(in.nextLine().trim()); // no of test cases

	for (int i = 0 ; i< T ; i++){
	int [] weights = readLineAsIntegers(in.nextLine());

	// result:
	out.println(solveLuggageProblem(weights));
	}
	}


	public static void main(String[] args) {

	Main solveLuggageProblem = new Main();
	solveLuggageProblem.run();
	}

	}

view raw uva10664.java hosted with ❤ by GitHub

Please leave a comment if you have any question regarding this problem or implementation. Thanks.

	import java.io.PrintWriter;
	import java.math.BigInteger;
	import java.util.Scanner;

	class Main {

	private final Scanner in;
	private final PrintWriter out;

	public Main(){
	in = new Scanner(System.in);
	out = new PrintWriter(System.out, true);
	}

	public Main(Scanner in, PrintWriter out){
	this.in = in;
	this.out = out;
	}

	private static BigInteger bigIntAfterRemovingTrailingZeros(String num){
	int nonZeroIndex=num.length()-1;
	for (; nonZeroIndex>=0; nonZeroIndex--){
	if (num.charAt(nonZeroIndex) != '0'){
	break;
	}
	}
	return new BigInteger(num.substring(0, nonZeroIndex+1));

	}

	private static BigInteger[] readLineAsBigInts(String input){
	String [] ints = input.trim().split(" ");
	BigInteger [] rets = new BigInteger[2];

	rets[0] = bigIntAfterRemovingTrailingZeros(ints[0]);
	rets[1] = bigIntAfterRemovingTrailingZeros(ints[1]);

	return rets;
	}

	private static BigInteger reversedBigInt(BigInteger num1){
	BigInteger reversedNum = BigInteger.ZERO;
	final int _REM = 1;
	final int _QUOTIENT = 0;

	while (num1.compareTo(BigInteger.ZERO)>0){
	BigInteger [] results = num1.divideAndRemainder(BigInteger.TEN);

	reversedNum = reversedNum.add(results[_REM]);
	if(num1.compareTo(BigInteger.TEN)>=0)
	reversedNum =reversedNum.multiply(BigInteger.TEN);

	num1 = results[_QUOTIENT];
	}

	return reversedNum;
	}

	private static BigInteger getAddRevNumbers(BigInteger num1, BigInteger num2){
	return reversedBigInt(reversedBigInt(num1).add(reversedBigInt(num2)));
	}

	public void run(){
	final int T = Integer.parseInt(in.nextLine().trim()); // no of test cases
	BigInteger [] numbers;

	for (int testCase = 0 ; testCase< T ; testCase++){
	numbers = readLineAsBigInts(in.nextLine());// read input
	out.println(getAddRevNumbers(numbers[0], numbers[1]));// print result
	}
	}

	public static void main(String[] args) {
	Main uva713Solver = new Main();
	uva713Solver.run();
	}

	}

Category: UVa

UVa 10706. Number Sequence with F#

Interpretation

Algorithm

Implementation

UVa 136. Ugly Numbers

UVa 371. Ackermann Function

See Also

UVa 713. Adding Reversed Numbers

See Also

UVa 10664. Luggage

See Also