TopCoder srm 708b BuildingStrings

problem

The score of a string is its length multiplied by the number of different characters in the string. For example, the score of “abbcdxc” is 7 * 5 = 35. This is because the length of this string is 7 and there are five different characters: a, b, c, d, x.

Bear Limak wants to find a sequence of strings satisfying the following conditions:

There number of strings is between 1 and 50, inclusive. The length of each string is between 1 and 50, inclusive. The sum of scores of the strings is exactly K. Each character in each string is a lowercase English letter (‘a’ - ‘z’). You are given the K. Compute and return any sequence of strings with the above properties. If there are multiple solutions, you may return any one of them.

code

TopCoder srm 708a SafeBetting

problem

Limak is in a casino. He has b dollars. He wants to have at least c dollars (to be able to buy flowers for a girl he likes). In order to achieve that, he must win the money he’s missing.

The casino allows guests to risk some of their money on bets. Limak can make as many bets as he likes, but he has to make them one after another. Each time Limak makes a bet, he chooses the amount he wants to bet. The amount must be a positive integer. Each bet has two possible outcomes: either Limak loses the money, or he gets it back doubled.

For example, suppose Limak has 20 dollars. If he bets 5, he will be left with 20 - 5 = 15 dollars. If he loses the bet, that is his new total. If he wins the bet, he’ll get back 2*5 = 10 dollars, which will bring his total up to 15 + 10 = 25 dollars.

Limak doesn’t want to lose all his money. More precisely, he wants to make sure that at any moment he will have at least a dollars. He will not make a bet if losing the bet would mean that he will have less than a dollars.

For example, suppose Limak currently has 20 dollars. If a = 15, in the next round Limak can bet 1, 2, 3, 4, or 5 dollars. Note that a bet of 6 dollars is not allowed: if he lost it, he would have 20 - 6 = 14 dollars, which is less than a.

You are given the s a, b, and c. We will assume that Limak follows the rules described above when choosing the amounts to bet. Compute and return the smallest B such that Limak can reach his goal (i.e., have at least c dollars) after making B bets.

code

Tread vs Process

problem

What is the difference between a thread and a process?

answer

English

• A process can be thought of as an instance of a program in execution. A process is an independent entity to which system resources( cpu time and memory) are allocated. Each process is executed in a separate address space, and one process cannot access the variables and data structures of another process. If a process wishes to access another process' resources, inter-process communications have to be used. These include pipes, files, sockets and other forms.

• A thread exists within a process and shares the process' resources (including its heap space). Multiple threads within the same process will share the same heap space. This is very different from processes, which cannot directly access the memory of another process. Each thread still has its own registers and its own stack, but other threads can read and write the heap memory.

Japanese

• プロセスは各プロセスごとにシステムリソース(CPU時間とメモリなど)を割り当てられたインスタンスで、異なるアドレス空間で実行される。そのためプロセス間で他のプロセスのリソースにアクセスしたければ、パイプ、ファイル、ソケットなどのプロセス間通信を行う必要がある。

• スレッドはプロセス内の同じメモリ空間を、複数のスレッドで共有する。そのため一般的に複数のスレッドが同じメモリを読み書きでき、他のプロセスが使用しているメモリにアックセウできないプロセスとはここが大きく異なる。

Paths with Sum

problem

You are given a binary tree in which each node contains an integer value(which might be positive or negative). Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go down wards(traveling only from parent nodes to child nodes).

how to solve

solution1: brute force in recursively.

In the brute force approach, we just look at all possible paths. To do this, we traverse to each node. At each node, we recursively try all paths downwards, tracking the sum as we go. As soon as we hit our target sum, we increment the total.

code

solution2: using hash table.

code

Sparse Search

problem

Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string.

how to solve

If it were not for the empty strings, we could simply use binary search. With empty strings interspersed, we can implement a simple modification of binary search. We just find closest non-empty string if mid is empty.

code

Sorted Matrix Search

problem

Given an M * N matrix in which each row and each column is sorted in ascending order, write a method to find an element.

how to solve

http://articles.leetcode.com/searching-2d-sorted-matrix-part-ii/

The above link is very easy understanding.

We begin with the upper right corner. Instead of traversing diagonally each step, we traverse one step to the left or bottom. Essentially, each step we are able to eliminate either a row or a column. This algorithm runs in O(n+m).

code

Minimal Tree

problem

Given a sorted(increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

How to solve

This minimal tree means creating height balanced tree. Firstly, we want the root to be the middle of the array, since this would mean that half the elements would be less than the root and half would be greater than it. We proceed with constructing our tree in a similar fashion. The middle of each subsection of the array becomes the root of the node. The left half of the array will become our left subtree, an the right half of the array will become the right subtree. We do this in recursively we create a height balanced tree in O(N).

• Insert into the tree the middle element of the array.
• Insert (into the left subtree) the left subarray elements.
• Insert (into the right subtree) the right subarray elements.
• Recurse.

code