SRM 609, D2, 250-Pointer (MagicalStringDiv2)

James S. Plank

Tue Oct 15 11:48:12 EDT 2019

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: 2014
Competitors who opened the problem: 1229
Competitors who submitted a solution: 1199
Number of correct solutions: 1164
Accuracy (percentage correct vs those who opened): 94.7%
Average Correct Time: 8 minutes, 42 seconds.

In case Topcoder's servers are down

(Please use the workflow in the problem Cryptography).

Here is a summary of the problem:

You are given a string S, composed solely of the characters '<' and '>'
S.size() is even.
You are allowed to replace a '<' with a '>', and vice versa.
Let k be S.size() / 2.
Your goal is to convert S to k '>'s followed by k '<''s.
Return the minimum number of replacements than you need to do.
Topcoder constrains S.size() between 2 and 50. My testing script has strings up to 1000 in size, and you should be able to do up to about 10,000,000.

The examples

Example	S	Answer
0	`">><<><"`	`2`
1	`">>>><<<<"`	`0`
2	`"<<>>"`	`4`
3	`"<><<<>>>>><<>>>>><>><<<>><><><><<><<<<<><<>>><><><"`	`20`

Testing yourself

I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt. The shell script should take well under a second.

Hints

At 1199 submissions, a 97% success rate, and an average score of 227.77, this has to be one of the easiest Topcoder problems in history. I would hope that you get it in under five minutes. If you want help, keep reading, but I urge you to figure this one out on your own.

When do you change a character?

When its index is less than S.size()/2, and it is not a '>'.
When its index is greater than or equal to S.size()/2, and it is not a '<'.

Run through S and add those up.