Codeforces Round #527 (Div. 3)_C. Prefixes and Suffixes

This is the first time I write blog on codeforces, actually I don't know whether this blog could write Problem-solving process or not so if there is something wrong in my passage, please do not give me so many negative comment! Thanks for your support!

---GNU C++11

---By the way, I'm a Chinese Collage student so I am not good at writing English. Though I'm a new hand in this sphere, I'm really keen on coding and hope to be a master one day!! And very glad to make friends with all of you! Work together and make progress.

---This time I write for the problem C. Prefixes and Suffixes in Codeforces Round #527 (Div. 3). The problem gives us the length of ans (n) and several prefixes and suffixes. As the Announcement says, For every pair of strings of equal length from the input, exactly one of them should be labeled as P, and exactly one as S. I just save the strings in the string array s. From my perspective, Since the author has ensure that it has an answer,we do not need to worry about that. So the possible ans should be 2. That is, we find out the 2 longest prefixes and suffixes from the given list (we easily know that the only difference between the real answer and them are one letter). Then combine them in a proper way, try to find out the possible answer!!

string save1, save2;
	for(int i = 0; i < 2 * n - 2; i++){
		if(s[i].size() == n - 1 && save1.size() == 0){
			save1 = s[i];
		}
		else if(s[i].size() == n - 1){
			save2 = s[i];
		}
	}
	//cout << save1 << " "<< save2 << endl;
	ans1 += save1 + save2[n-2];
	ans2 += save2 + save1[n-2];

The variable save1 and save2 save the string with length n-1, ans1 and ans2 use a direct way to save the 2 possible answer. Then we only need to compare each string in the array and find out which is 'P' and which is 'S'.

Let's say ans1 is the real answer first! When we compare every string with ans1, we need to find out if it is prefix or not. Remember, some strings have the same prefix and suffix so the first if judgement might give it two "P". Then we use a new string variable called result to save the finall output. (A string with 'P' and 'S')It doesn't matter which one we choose, but what we need to do is give a judgment whether the hypothesis is right or not.

*For example, we could say like this:"If the number of 'S' and 'P' are not equivalent, the hypothesis are wrong! If the length of result is not n is the same." So the programme is easy to write like this:

int num_s= 0, num_p = 0;
  	for(int i = 0; i < p; i++){	//A hypothesis， assuming ans1 is the real string. 
  		if(ans1.substr(0, s[i].size()) == s[i] && !mark[s[i].size()]){	//some string have the same perfix and suffix 
  			num_p++;//we use the string method ans1.substr(a ,b), which returns a string which starts from the position **a** of ans1, length is **b**. It is very useful in this situation.
  			result += 'P';
  			mark[s[i].size()] = 1;
		  }
		else if(ans1.substr(n - s[i].size(), s[i].size()) == s[i]){
		 	num_s++;
			result += 'S'; 	
		}
	}
	if(num_p == num_s && result.size() == p){ // judgement
		cout << result;
	}

mark is a map that I use here to record the situation that we already have a prefix. We don't want to record 2 prefix with same length!! That is definitely a wrong answer! And give a judgement at last. We know that the number of 'P' and 'S' should equivalent, and size of result should be p (which value is 2*n-1).

Next we need to talk about ans2. We reset the value of variebles and do the same thing as before.But this time we needn't to write another else if because if the ans1 is wrong, ans2 should be the ‘murderer’ definitely.

else{
		mark.clear();
		num_p = 0;
		num_s = 0;
		result = "";
		for(int i = 0; i < p; i++){	//ans2 is the murderer
  		  if(ans2.substr(0, s[i].size()) == s[i] && mark[s[i].size()] == 0){	//mark has the same function 
  			num_p++;
  			result += 'P';
  			mark[s[i].size()] = 1;
		  }
		  else{
		 	num_s++;
			result += 'S'; 	
		  }
	        }
	        cout << result;
}

Oh, another antic I learned during the hacking process is this:

#ifndef ONLINE_JUDGE                     //1
    freopen("in.txt", "rt", stdin);      //2
#endif                                   //3

The statement between line 1 and line 3 is the redirect statement as we know. The oj will ignore the statement on line 2 but on our computer it could be compiled and run. So it is easy for us to use the FILE and do not need to comment out the statement!!

This is the whole process of problem solving in my mind. Though div.3 is easier, I didn't get a high rating o(╥﹏╥)o. But I'll keep doing what I like and be with codeforces as long as possible!