SPOJ DYZIO

From Algorithmist
Jump to navigation Jump to search

56. Dyzio[edit]

Summary[edit]

The given input is a list of cutting instructions as ones and zeros to be applied to length of string. A one indicates the string is to be cut in half and a zero means that the string is to be ignored. The instructions pertain to the leftmost piece of the string. The problem is to determine how many cuts were required to cut the shortest piece of string.

Explanation[edit]

The cutting of the string can be visualized as the preorder traversal of a binary tree.

Assume that your position is in the root just before you have started reading the input. Now start reading the input string. If the current character is '1', visit the left subtree and the right subtree one after another. A '0' character means you have reached a leaf (the sub-tree is empty).

Do this recursively. You just have to count the number of nodes you have to visit until reaching the first deepest leaf of the tree.

the pseudo code would be something like this:

 VISIT(depth)   /* call this function with VISIT(0) */
   if depth > deepest
      deepest = depth
      ans = cut_no     /* initially cut_no will be 0 */
   if input[current_position] == 1
      cut_no = cut_no + 1
      current_position = current_position + 1
      VISIT(depth + 1)
      VISIT(depth + 1)
   else
      return

Implementation[edit]

Although a binary tree data structure certainly encompasses this problem, the solution can be obtained with a simple stack. In fact, a fully implemented tree soution may well exceed the time limit for this problem. Simply keep track of whether a node has been visited once or twice and note the maximum size that the stack achieves.

Input[edit]

There are exactly ten test cases. Each test case consists of two lines. The first line is the length of the instruction string. The next line consists of a sequence of '1's and/or '0's.

9
110011000
9
111000100
3
010
1
1
2
11
15
111100111000000
15
101010110011000
19
1100111011001010000
13
1100111000100
15
111010001010100

Output[edit]

4
3
0
1
2
7
7
9
5
4

See Also[edit]

Stack

Binary Tree