TopCoder SRM 428 DIV 2

C/C++ TopCoder
Problem Check Points
250 × -
500 - -
1000 - -

残り10分で思わず「死にたい！」って叫んでた。ダメダメだわ・・・

Problem 250 ThePalindrome

問題

John and Brus are studying string theory at the university. Brus likes palindromes very much. A palindrome is a word that reads the same forward and backward. John would like to surprise Brus by taking a String s, and appending 0 or more characters to the end of s to obtain a palindrome. He wants that palindrome to be as short as possible. Return the shortest possible length of a palindrome that John can generate.

http://www.topcoder.com/stat?c=problem_statement&pm=10182&rd=13519
解説

First, note that the answer in this problem is not large. If we append to s all its characters in reverse order, the resulted string will be a palindrome, so the answer does not exceed twice the length of s. Therefore, for each i between 0 and length of s we need to answer the following question: does it possible to append i characters to the end of s to obtain a palindrome? The answer for our problem is simply (the smallest among appropriate i's) + (the length of s).

If want to append i characters to make a palindrome, there's actually no any choice in what exactly characters to append. The last appended character must be the same as the first character of s (otherwise it won't be a palindrome for sure), the last but one appended character must be the same as the second character of s, and so on. In other words, we should append the first i characters of s in reverse order. Of course, after these characters are added, the result is still not guaranteed to be a palindrome, so this needs to be additionally checked.

This approach can be implemented in Java as follows:

public class ThePalindrome {
  boolean isPalin(String s) {
    for (int i=0; i<s.length(); i++)
      if (s.charAt(i) != s.charAt(s.length()-i-1))
        return false;
    return true;
  }

  public int find(String s) {
    for (int i=0; ; i++) {
      String tmp=s;
      for (int j=i-1; j>=0; j--)
        tmp += s.charAt(j);
      if (isPalin(tmp))
        return i + s.length();
    }
  }
}

Excercise (not of DII-Easy level). The described solution of the problem has a complexity of O(n^2) and works very fast when n ≤ 50. Find a solution for this problem that will work for n ≤ 100,000 (it should have a complexity of O(n * log n) or even O(n)).

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm428
My code
class ThePalindrome {
public:
  int find(string s) {

	int lp, rp;
	bool flag;
	for(int i=0 ; i<s.size() ; i++){

		lp = i;
		rp = i;
		flag = true;
		while(lp>=0){
			if(!(rp >= s.size() || s[lp]==s[rp])) flag = false;
			lp--;
			rp++;
		}

		if(flag && rp >=s.size()) return 2*i+1;

		lp = i;
		rp = i+1;
		flag = true;
		while(lp>=0){
			if(!(rp >= s.size() || s[lp]==s[rp])) flag = false;

			lp--;
			rp++;
		}
		if(flag && rp >=s.size()) return 2*i+2;	
	}
    return -1;
  }
};

Problem 500 TheLuckyString

問題

John and Brus are studying string theory at the university. According to Brus, a string is called lucky if no two consecutive characters are equal. John is analyzing a String s, and he wants to know how many distinct lucky strings can be generated by reordering the letters in s. If s is a lucky string in its original ordering, it should also be considered in the count.

http://www.topcoder.com/stat?c=problem_statement&pm=10180&rd=13519
解説

Since s contains at most 10 characters, there are at most 10!=3,628,800 ways to permute its letters. This is not too much, so nothing prevents us from checking all strings that can be obtained by permuting the characters of s and calculate how many of them are lucky. The most natural way to implement this is using recursion. Our recursive method will try to assign characters of s to positions 0, 1, ..., L-1, in order (where L is the length of s), in all possible ways, and so that they form a lucky string. It takes two parameters - integer pos is a position we are currently filling and character prev is the character we've put onto the previous position. There's also a global array have of 26 integers, where have[i] is how many i-th (in alphabet) letters we currently have. For each letter c in alphabet such that we have this letter and it is different than prev, we try to put this letter on position pos (we can't put the letter prev on position pos because we want to generate only lucky strings). To do this, we decrease the number of occurrences of the letter c in have by 1, recursively call the method with parameters pos + 1 and c, and than restore the state of have by increasing the number of occurrences for c by 1. If in some call pos = L, it means that we've just generated one more lucky string, so we increase some global counter cnt by 1. The search is initiated by a call with parameters pos=0 and prev=' ' (or some other character that is not a letter - to indicate that every character can be put at position 0). The answer is the value of counter cnt after the method has completed its work.

The actual code appears to be shorter than its explanation given in the previous paragraph. Java implementation follows.

public class TheLuckyString {
  int[] have = new int[26];
  int cnt = 0, L;

  void solve(int pos, char prev) {
    if (pos == L) {
      cnt++;
      return;
    }
    for (char c = 'a'; c <= 'z'; c++)
      if (prev != c && have[c - 'a'] > 0) {
        have[c - 'a']--;
        solve(pos + 1, c);
        have[c - 'a']++;
      }
  }

  public int count(String s) {
    L = s.length();
    for (int i=0; i < L; i++)
      have[s.charAt(i) - 'a']++;
    solve(0, ' ');
    return cnt;
  }
}

Excercise. The described solution works in O(L!). Can you come with something significantly faster? What about polynomial solution? (Hint: this problem is very similar to a DI-Hard problem from a recent SRM; you can just adapt solutions for that problem to get fast solutions for this one).

My code
bool isLucky(string s){
	for(int i=0 ; i<s.size()-1 ; i++){
		if(s[i]==s[i+1]) return false;
	}
	return true;
}

class TheLuckyString {
public:
  int count(string s) {

	  int cnt = 0;
	  sort(s.begin() , s.end());


	  do{
		  if(isLucky(s)) cnt++;

	  }while(next_permutation(s.begin(),s.end()));

	  return cnt;
  }
};

Problem 1000 TheDictionary

問題

John and Brus are studying string theory at the university. Brus has finished his special project - a dictionary that contains all strings of a special type. Each string in his dictionary contains exactly n occurrences of the lowercase letter 'a', m occurrences of the lowercase letter 'z', and no other letters. The strings are listed in alphabetical order.

Your task is to help John by finding the k-th (1-based) string in Brus's dictionary. If there are less than k strings in the dictionary, return an empty String instead.

http://www.topcoder.com/stat?c=problem_statement&pm=10183&rd=13519