X and Y
All submissions for this problem are available.
The trick is simple. It's Valentine's Day. You're here to code. Why not help a guy fix a date for him? :D
This is a very geeky situation. The guy and girl are both good friends. They like each other as well. Strangely, both of them are programmers too! :P
Geeky situation!? Well yes, lemme explain. The guy finally asks her out on Valentine's Day, i.e. today. She responds “I am stuck in a question at the moment” The guy is like??!!!! (what a true programmer eh?) She then asks him to help her out so that they can wind up quickly and go have some coffee together (some relief for him finally) :D
However, since it is going to be his first date, the guy is very nervous. So, this has only added to the tension and his mind has literally stopped working now. (yes, love can do that to you I guess :P)
Since you are a geek too (coming to the lab to participate in a programming contest on Valentine's Day?! of course you're a geek :P), please help him out with the problem at hand and hence fix the date. :)
The question is: given a string minStr and two integers N and minInv, you are to return a string of length N consisting of the first N lowercase alphabets. Further, this string should not be lexicographically smaller to minStr and should have a minimum of minInv inversions. If such a string is not possible, return -1.
1) For a given string S of length N, an inversion is a pair of integers (i, j) such that 0 <= i < j <= N-1 and S[i] > S[j]. (That is, the character at 0-based index i is greater than the character at 0-based index j.) For example, the string "abcab" has 3 inversions: (1, 3), (2, 3), and (2, 4).
2) A String A is lexicographically smaller than a String B if A is a prefix of B or A contains a smaller character at the first position where the Strings differ.
The first line of the input consists of T, the no of test cases. Each test case starts with a single line consisting of N, minInv and minStr separated by a space.
For each test case, output on a new line the desired string mentioned above.
- 1 ≤ T ≤ 10^6
- 1 ≤ minInv ≤ 10^6
- 1 ≤ N ≤ 26
- 1 ≤ |minStr| ≤ N
Input: 2 2 1 ab 15 0 e Output: ba eabcdfghijklmno
Example case 1. "ba" consists of a single inversion and is lexicographically greater than "ab" both of which are requirements.
Example case 2. "eabcdfghijklmno" is the required string because the original string "e" had 0 inversions which meets our requirement. Hence, we simply append characters from a to o (excluding e which is already there in the beginning) to make the length N. You can see here that a further lexicographically smaller string is not possible without violating the constarints.
Problem Setter: Ayush Jaggi
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.