ColorfulBuilding
SRM 582 · 2012-12-13 · by semiexp
SRM 582 · 2012-12-13 · by semiexp · Dynamic Programming
Problem Statement
Problem Statement
There are N skyscrapers standing in a line from left to right.
The buildings are numbered 1 through N, in some order (not necessarily from left to right).
You do not know this order.
For each i, the height of building i is i.
Thus, the heights of the N buildings form a permutation of 1 through N.
Each of the buildings is painted using a single color. Multiple buildings may share the same color. For each i, you know the color of building i. (The technical details are specified below.)
You are standing far to the left of all the buildings. From your location, you can only see parts of some buildings, because smaller buildings farther from you are obscured by taller ones that are closer. Formally, you can see (some top part of) building X if and only if all of the buildings in front of X (that is, to the left of X in the row) are lower than building X.
Additionally, from where you are standing you cannot distinguish between two buildings that have the same color. More precisely, whenever you see two buildings with heights H1 and H2 (H1 < H2) such that they both have the same color and you can see no building that stands between them, they seem to you as one building. This also naturally extends to more than two buildings of the same color.
You think you now see L buildings. In other words, as you look at the buildings from where you are standing, you see exactly L-1 places where the color changes.
You are givenString[] s color1 and color2, and the int L.
The String[] s color1 and color2 can be used to determine the colors of buildings in the following way:
Concatenate all elements of color1 to obtain a String C1.
Concatenate all elements of color2 to obtain a String C2.
The strings C1 and C2 will each have exactly N characters.
Now, for each i and j: buildings i and j have the same color if and only if both C1[i-1]=C1[j-1] and C2[i-1]=C2[j-1].
In other words, for each i the color of building i is described by the two-character string C1[i-1] + C2[i-1].
Given this information, compute and return the number of possible orders of the N buildings, modulo 1,000,000,009.
Each of the buildings is painted using a single color. Multiple buildings may share the same color. For each i, you know the color of building i. (The technical details are specified below.)
You are standing far to the left of all the buildings. From your location, you can only see parts of some buildings, because smaller buildings farther from you are obscured by taller ones that are closer. Formally, you can see (some top part of) building X if and only if all of the buildings in front of X (that is, to the left of X in the row) are lower than building X.
Additionally, from where you are standing you cannot distinguish between two buildings that have the same color. More precisely, whenever you see two buildings with heights H1 and H2 (H1 < H2) such that they both have the same color and you can see no building that stands between them, they seem to you as one building. This also naturally extends to more than two buildings of the same color.
You think you now see L buildings. In other words, as you look at the buildings from where you are standing, you see exactly L-1 places where the color changes.
You are given
Given this information, compute and return the number of possible orders of the N buildings, modulo 1,000,000,009.
Constraints
- color1 and color2 will each contain between 1 and 36 elements, inclusive.
- color1 and color2 will contain the same number of elements.
- Each element of color1 and color2 will contain between 1 and 36 characters, inclusive.
- For each i, the i-th elements of color1 and color2 will contain the same number of characters.
- Each character of each element of color1 and color2 will be a lowercase or an uppercase letter ('a'-'z' or 'A'-'Z').
- L will be between 1 and N, where N is the total number of characters in color1.
Examples
0)
{"aaba"}
{"aaaa"}
3
Returns: 6
There are 4 buildings. Buildings 1, 2, and 4 share the same color, building 3 is different. There are 6 valid orders of buildings (from left to right): 1, 2, 3, 4 1, 3, 2, 4 1, 3, 4, 2 2, 1, 3, 4 2, 3, 1, 4 2, 3, 4, 1 Note that if the buildings stand in the order 1, 2, 3, 4, you can see all four buildings. However, as buildings 1 and 2 have the same color, you regard them as one building. Therefore, you think you see 3 buildings.
1)
{"aaba"}
{"aaba"}
4
Returns: 0
For each possible order of these buildings you will think you see at most 3 buildings.
2)
{"ab", "ba", "a", "aab"}
{"bb", "ba", "a", "aba"}
5
Returns: 432
Make sure to concatenate all the elements of color1 and color2.
3)
{"xxxxxxxxxxxxxxxxxxxx",
"xxxxxxxxxxxxxxxxxxxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxOOxxxxxxxxxxxxxxxx",
"xxOOxxxxxxxxxxxxxxxx",
"xxOOxxxxxxxxxxxxxxxx",
"xxOOxxxxxxxxxxxxxxxx",
"xxOOxxxxxxxxxxxxxxxx",
"xxOOxxxxxxxxxxxxxxxx",
"xxOOxxxxxxxxxxxxxxxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxxxxxxxxxxxxxxxOOxx",
"xxxxxxxxxxxxxxxxOOxx",
"xxxxxxxxxxxxxxxxOOxx",
"xxxxxxxxxxxxxxxxOOxx",
"xxxxxxxxxxxxxxxxOOxx",
"xxxxxxxxxxxxxxxxOOxx",
"xxxxxxxxxxxxxxxxOOxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxxxxxxxxxxxxxxxxxxx",
"xxxxxxxxxxxxxxxxxxxx"}
{"xxxxxxxxxxxxxxxxxxxx",
"xxxxxxxxxxxxxxxxxxxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOxxxxxxxxxxxxOOxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxOOOOOOOOOOOOOOOOxx",
"xxxxxxxxxxxxxxxxxxxx",
"xxxxxxxxxxxxxxxxxxxx"}
58
Returns: 619787617
4)
{"SJXcabKTWeUXhwxGixFepQaQlFxrAedNAtVP",
"gorBIkcTlOFbLDbFeElYAyAqszQdMbpxSRdE",
"SQVHPehlNtesbJDflyGxMqvgzjXisRnqDcQO",
"pIAEBwbmpPWCooQAujbGXFGLvXxTmExLARkf",
"AFnWyWKVObfxDGCjTxdZaObgwdxlPKtIxaAd",
"uznMpJVNjAofbHJjOrZeSHgSagOCUMGbvkVR",
"LBRrDbTAyKfVnedKiRfzgRzECpcsziqaTwdo",
"JrJHvsEVVGDkNVGqLbpxyLDPloBuNDQKnReI",
"SSYpbjKHSCnQhuyYrVauWDHDyhAoGyecrZMv",
"UdetQfWEUWHHuAxRSdkJOOJSixKpQXpCFZHO",
"KXVsQbuQtIgsULOMsTvPFNUqkBldMTLCipYK",
"hoXConjnDWQkZVtyZlwSedvdVrNWqQhGUClQ",
"TpsvvyoXsXmQpBAGGVDrXCkodoRHQZmpoQDW",
"csiJspzTqeFBRmPgeEtTAzfrfCGlTZqcPuyO",
"vsPDVBJVaJmUAtDdcsKoUkPEbDmAwtZKwjjP",
"MOfoMhMiKIvGQoeIJXHzyClWRtRuKXMqxUAF",
"KyyUCkRBjsYvmPFFEGBqqVhIUdtvIyyLacfu",
"BfuwfSajSlcuTzhMufHSQLudvGEGlyHsEmBD",
"PLpIXZkdyXveTMfSvqnDGKWOZrTBMUIlZrqF",
"dzVMCqrSLbanRJTYpDJNHAOLPSzmvSEPQJYm",
"rAjRkrSjouJyFaCSPPLYSzqDmMoADyWAbobJ",
"eOCBrJNoyFnGpXpxiExXcoOHnVsaEPXhPfLe",
"XMjRksnxWssPEINhdhbiLBSYpCLtwNshFjXS",
"HnnDeUAbuswsgsYQuAaXySLkFYUwFXwYTreM",
"uqLnwOEGbwZZDgAAWEdLRZxFlogDmlhjhgHM",
"NcfaQsgPQfirkYDRFrLQpySmBGfRHumKULZf",
"mOpmmgclsxRzXskEywfryqCRyATNoJwnlHiD",
"AnoKoKAjrasttjNlHCROnvTJMhEHlVPVoVMo",
"yegLyIuRkkENFAjwzDoPLKjgUHHEkfzYDIpo",
"EcxRGGfuaBXUFXkSxctJWOLmmVbvoMkWtTvV",
"nBMkOBHgaltEVzfyGxseGhmBscfGIbxFbqRn",
"GvkEcLtqdOofGtsbWDafVMbNdJxsffKDzSiR",
"jhZQUVzTzalrZcebvyqPWtOUUyniBKTWdyLi",
"ODJLQPMdjDdTlxrfGsNmBfeGYjzeXApqKDhJ",
"vlJkWMzdVQujKdLViQClOrJXMTBkuZEasFgg",
"FAsbuzrLVIgaryqXBfuBRAbReleXSSgEKSvt"}
{"XAhlUHtfjOpOlQlowWppQcodMGUiqoLobxnD",
"IDzGlKrHiVGdBjZxIcoxjwagbWieKvUwZrjg",
"SkpkTVeIFeoNQzUUgmYAYskKONNZdgXxSiWd",
"rXBGhTmqnvxkmqiutoDzPusDiOUggEFXGCzm",
"fzrxVuTbFXunGbeEavjshmrIRlDorTuISCxn",
"LsvIaxTkOBjcskiekmrKNNFEXqnfMNXLWqqu",
"ekzxGIlbJPVEQPYAbTuMtZKsCiubDXDiBVzU",
"hZuOCJxvBOYENGSFcUiKKAKfCdebutVmnyvB",
"UveNkKRQmHnedrROQOpHJfrHjwcNLUShlDbn",
"ptUkvbaGDryHRkYfHKLkSgVpjWCEcgazyxGK",
"nVPYEqTTJsRPjzjfdOiULhnZPFeNcnbXaQlk",
"IPXBXRhMQIkxpygsgbcRfMuvIcuzUPPHGOWX",
"yWWlNyEyqZSIOXBFAybIuFpVqpvmKRaRFrAE",
"EvBJVtHvKhjrFcmtpdBbFTdTVtXXZQKAglKT",
"bCVjHzUvyINFkxXageZQMzCyNhcifACdJVDh",
"lZITYcDSeIbLweyFtoMAfOQyBNupKlhcNpgo",
"BduslNrJdWOUukYFFidEkMFaghfofpxVgvJd",
"YrJpDZKqdjEPzdLsOQEdkcrBfNHPemXHokCW",
"GjeUKSGjDlgKTyUGNrMQbBLxRUcgrWpkAwOD",
"wgxTcswqdJHaDugNIRMvrhBsdDaJAssVbSRW",
"qmVmqFEpvgGioMXDSFqEoQcDOAaUoGPEovSO",
"KrukPlpfOhawaovCfteTSCIdLMrtImVtiMyQ",
"ykwmxHsKMFzFHwcbyyedLvhZPnaNGqJMMCxd",
"HUNYCXjNLQIFCLLGpCXHBCHLTxLynBxnHFbx",
"uwjzbNbJepVFgMPUXVirxYHzExquBEtPmKju",
"xXAxAbJePyUsVHeLytDvAxBGMRtnvCEiZZqe",
"xMkQoIVxWPXPgaOYmDjTOXiMImVdzojERNxS",
"dwICFwMAmdOIUxyAdXdshasnzwyhfnVWVqZJ",
"etypXNVvSTEQvriGBZdSGmDEHhvpSqkFklCS",
"YkxpFBCRYUueRcKaJUXVdaMoYMYEooPQVMOr",
"DTrexDqclZNKdPuTRFHualJSFziCLPCZjpxo",
"TfEijcAsSJPikkmBSbXMqYHAhPTcpcKVSkIX",
"xKXHYPYMJxFpSbxltDKYuRiTkOLxpQKnXZPs",
"YFYuvuYHfpFJcrLNIdlNfBxRnWdppsdalBkx",
"NFTysBvNFjejdnlhRTclbcfGipNCxpFEOriY",
"thkgVflJYmbUYbIlafNUMGePQWiZyYzYXvUR"}
1200
Returns: 396065426
Submissions are judged against all 105 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ColorfulBuilding with a public method int count(vector<string> color1, vector<string> color2, int L) · 105 test cases · 2 s / 256 MB per case