EquivalentStrings
SRM 801 · 2021-02-22 · by misof
Problem Statement
In this problem we consider strings of digits and one simple transformation: swapping adjacent digits whose values differ by more than 1.
Two strings are called equivalent if one can be changed into the other using a sequence of zero or more transformations described above.
For example, "017040" and "470100" are equivalent (you can change one into the other using six swaps) but "107040" is not equivalent with them.
You are given the
E.g., if seeds = {"012", "47"}, queries = {"012", "120", "201", "47", "74"}.
Return the size of the largest subset of queries such that no two strings in the subset are equivalent.
Notes
- The reference solution does not need to make any assumptions about the way the queries are produced. It would also solve any other input of the same size. The specific way chosen was only used in order to keep the input small.
Constraints
- seeds will contain between 1 and 50 elements, inclusive.
- Each element of seeds will be non-empty.
- The total length of all elements in seeds won't exceed 2500.
- Each character in seeds will be a digit ('0'-'9').
{"017040"}
Returns: 4
The array queries[] contains six distinct strings. There are two pairs of equivalent strings in queries: "040017" and "704001" are equivalent, as are "001704" and "400170". Thus, we can select a subset of size at most four.
{"474", "474", "744", "474"}
Returns: 1
queries = {"447", "474", "744"}, and as all three strings are equivalent, we can only select one of them.
{"0123456789", "02468"}
Returns: 11
All cyclic rotations of "0123456789" are non-equivalent. All cyclic rotations of "02468" are equivalent.
{"344345678765676776767789877787765544556677889877888999998887878988999876776556766788765677655433432121011010100112332110121100112122111011222321121012233222123322100112345432323233211122223332110001112210011000111223444434445454443456667899899987876656544555676667654455555666676666778788987888988877878889898998767666788887898788887666788899999989899888765544454456566556766555433322212110001101000122234321222101210001112211211210001222234567887876565432344567788987889999988988999987887676678898788787899999998898766555565454543345677665443456787877667787777767765654565545677665667889998767878765444455565455444334433443455434454443234543322210123434323323232122100110001001012101011221001121232211222223444545565655443211232212112333434334544333334543211212123443434432212101111234444321121100121223432233210110121122332332123434545554455566545445456787767777788988789899899899899999988999878998777766678998988778989876566787889877656544345554432111234444554344432110110121100100010010000011223233211010001111233445666545677878989987656666544565454566787788998788789999898777898998765656656777766676565555665432322122122322232100111122321234455544445566544344445566556778888787665454445654565543211222122333221121212332101234334455556778766676777788888888998999899899889889898766656555656788899888777878998876676767655555443222122222121122343455433345678998999887766778789989998767777777787765443232222322333344345665666543321111223456544556554556666777665565566656765433454433443454445567877888777877878787888765566667878988767667787877899898789899887765678988878898787898788877654556667789887888877765655455678778777788899999889899889878898988878778778878767777765543233345444334454445445445432212101210101010011123445556544565678989876654332101000001101000111122123344321223433232122345566566656665676544321232234545444322111000001223343223322233443444456555678778877877677655433234323455443222221101111012121212112223334432233332222322334566566555566667655434555665432121012223445677666765433344445433433322332343322101010011001101121100012233234433454456544556554334334454343432222211121001123345677878899988898998777899989887667789998788765456789898998878899887655544456778899988876789889898888998766667889898766676654321012232212110101111234434334343222123334456787778878766677889989889987655655665445443454566778898787655545432110000000110112112212101000100123211010101121010110110111001001010121000100112344333334545678778876676766655455567676544555654543344345443432100122111111234433"}
Returns: 2499
{"1"}
Returns: 1
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EquivalentStrings with a public method int count(vector<string> seeds) · 65 test cases · 2 s / 256 MB per case