TopCoder problem "DeckRearranging" used in SRM 420 (Division II Level One)



Problem Statement

    

We have a deck of cards. Each of the cards is either black or red. We will use the character B to represent a black card and the character R for a red card. By listing the cards from top to bottom of the deck we get a String deck.

We now want to insert all the cards into a new deck. Initially, the new deck is empty. We will now process the cards in the old deck from top to bottom. When processing the card that corresponds to character i of deck, take it from the old deck and insert it into the new deck in such a way that exactly above[i] cards are above it after the insertion.

Write a method that takes the String deck and int[] above, and returns the new deck encoded as a String in the same way as deck.

 

Definition

    
Class:DeckRearranging
Method:rearrange
Parameters:String, int[]
Returns:String
Method signature:String rearrange(String deck, int[] above)
(be sure your method is public)
    
 

Constraints

-deck will contain between 1 and 50 characters, inclusive.
-Each character in deck will be either 'B' or 'R' (uppercase letter B or R).
-The number of elements in above will be equal to the number of characters in deck.
-For each i, element i in above will be between 0 and i, inclusive.
 

Examples

0)
    
"BRBRR"
{0, 0, 1, 0, 3}
Returns: "RRBRB"

The order of cards in the old deck, top to bottom, is: B, R, B, R, R. This is the order in which we will process them.

Below we list the new deck, top to bottom, after each of the insertions. The most recently inserted card is given in uppercase, the other cards are in lowercase.

  1. B
  2. Rb
  3. rBb
  4. Rrbb
  5. rrbRb
Therefore the new deck is RRBRB.
1)
    
"RRRRRR"
{0,1,2,0,1,3}
Returns: "RRRRRR"
No matter how you rearrange a deck with 6 red cards, you will always get a deck with 6 red cards.
2)
    
"RBRRBRBB"
{0,1,2,3,4,5,6,7}
Returns: "RBRRBRBB"
In this example each card is placed at the bottom of the new deck. The result is the same deck as the old one.
3)
    
"RBRRBRBB"
{0,0,0,0,0,0,0,0}
Returns: "BBRBRRBR"
In this example, each card is placed on the top of the new deck. The result is the old deck turned upside down.
4)
    
"RBRRBRBB"
{0,1,0,0,4,0,6,7}
Returns: "RRRRBBBB"
In this example, we place each red card on the top, and each black card on the bottom. The result is a deck with all red cards on the top.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9914

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13511&pm=9914

Writer:

misof

Testers:

PabloGilberto , Olexiy , ivan_metelsky , zhuzeyuan

Problem categories:

Simple Search, Iteration, String Manipulation