SRM 606, D2, 250-Pointer (EllysSubstringSorter)

James S. Plank

Sat Sep 3 15:32:13 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: January, 2014
Competitors who opened the problem: 814
Competitors who submitted a solution: 707
Number of correct solutions: 357
Accuracy (percentage correct vs those who opened): 43.86%
Average Correct Time: 16 minutes, 46 seconds.

The solution to this is to generate each possible transformed string, and keep track of the minimum. You'll start with i=0, and keep iterating until i+L > S.size(). For each value of i, you generate three strings, using the substr() method of strings:

The substring starting at index 0 with i characters.
The substring starting at index i with L characters.
The substring starting at index L+i with the remaining characters.

Next, use the sort() method to sort the middle string, and then concatenate the strings together. That is the transformed string.

I won't include the code for this one, but I will show the output of each loop on Examples 0 through 4:

Example 0:

i:0    TOPC ODER.  Sorted middle: COPT.  String: COPTODER.  Best: COPTODER
i:1   T OPCO DER.  Sorted middle: COOP.  String: TCOOPDER.  Best: COPTODER
i:2   TO PCOD ER.  Sorted middle: CDOP.  String: TOCDOPER.  Best: COPTODER
i:3   TOP CODE R.  Sorted middle: CDEO.  String: TOPCDEOR.  Best: COPTODER
i:4   TOPC ODER .  Sorted middle: DEOR.  String: TOPCDEOR.  Best: COPTODER
COPTODER

Example 1:

i:0    ESP RIT.  Sorted middle: EPS.  String: EPSRIT.  Best: EPSRIT
i:1   E SPR IT.  Sorted middle: PRS.  String: EPRSIT.  Best: EPRSIT
i:2   ES PRI T.  Sorted middle: IPR.  String: ESIPRT.  Best: EPRSIT
i:3   ESP RIT .  Sorted middle: IRT.  String: ESPIRT.  Best: EPRSIT
EPRSIT

Example 2:

i:0    AA AAAAAAA.  Sorted middle: AA.  String: AAAAAAAAA.  Best: AAAAAAAAA
i:1   A AA AAAAAA.  Sorted middle: AA.  String: AAAAAAAAA.  Best: AAAAAAAAA
i:2   AA AA AAAAA.  Sorted middle: AA.  String: AAAAAAAAA.  Best: AAAAAAAAA
i:3   AAA AA AAAA.  Sorted middle: AA.  String: AAAAAAAAA.  Best: AAAAAAAAA
i:4   AAAA AA AAA.  Sorted middle: AA.  String: AAAAAAAAA.  Best: AAAAAAAAA
i:5   AAAAA AA AA.  Sorted middle: AA.  String: AAAAAAAAA.  Best: AAAAAAAAA
i:6   AAAAAA AA A.  Sorted middle: AA.  String: AAAAAAAAA.  Best: AAAAAAAAA
i:7   AAAAAAA AA .  Sorted middle: AA.  String: AAAAAAAAA.  Best: AAAAAAAAA
AAAAAAAAA

Example 3:

i:0    ABRAC ADABRA.  Sorted middle: AABCR.  String: AABCRADABRA.  Best: AABCRADABRA
i:1   A BRACA DABRA.  Sorted middle: AABCR.  String: AAABCRDABRA.  Best: AAABCRDABRA
i:2   AB RACAD ABRA.  Sorted middle: AACDR.  String: ABAACDRABRA.  Best: AAABCRDABRA
i:3   ABR ACADA BRA.  Sorted middle: AAACD.  String: ABRAAACDBRA.  Best: AAABCRDABRA
i:4   ABRA CADAB RA.  Sorted middle: AABCD.  String: ABRAAABCDRA.  Best: AAABCRDABRA
i:5   ABRAC ADABR A.  Sorted middle: AABDR.  String: ABRACAABDRA.  Best: AAABCRDABRA
i:6   ABRACA DABRA .  Sorted middle: AABDR.  String: ABRACAAABDR.  Best: AAABCRDABRA
AAABCRDABRA

Example 4:

i:0    BAZING A.  Sorted middle: ABGINZ.  String: ABGINZA.  Best: ABGINZA
i:1   B AZINGA .  Sorted middle: AAGINZ.  String: BAAGINZ.  Best: ABGINZA
ABGINZA