Slabi test primeri na Asistent MOI 13

This message was edited 1 time. Last update was at 04/01/2016 20:54:55

Programava ima kontraprimer, no na mendo nema takov test primer. Zar treba da se vazi kako tocno resenie?

Kontraprimerot e : ABBAABBAAAAAAAAAAAA
Tocnoto e: AAA AAA AAA AAA - 12
Programata dava: AB BA AB BA - 8

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

int main(){
	ios::sync_with_stdio(false);

string str;
	cin >> str;
	int n = str.size();

vector<int> v[26]; // vektor koja za dadena bukva,
					   // dava i kade sto str[i] == v[c] za dadeno c, sortirano opagacki
	for(int i = n - 1; i >= 0; i--){
		v[str[i] - 'A'].push_back(i);
	}

int res = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < v[str[i] - 'A'].size() and v[str[i] - 'A'][j] > i; j++){
			int e = v[str[i] - 'A'][j]; // krajna bukva

//|verglanje| = |x| + |y| + |x| + |y|
			//|verglanje| = |x| + |x| + |x| + |x|
			//|verglanje| = 4 * |x|
			//golemina na verglanjeto e deliv so 4
			if((e - i + 1) % 4 == 0){ // da se proveri dali delot [i, e] e so golemina deliva so 4
				int sizep = (e - i + 1) / 4; // golemina na X

//proveruvame dali dvete XY se isti
				bool passed = true;
				for(int k = 0; k < sizep + sizep and passed; k++){
					if(str[i + k] != str[i + sizep + sizep + k]){
						passed = false;
					}
				}

//proveruvame dali prviot X i prviot Y se obratni
				for(int k = 0; k < sizep and passed; k++){
					if(str[i + k] != str[i + sizep + sizep - k - 1]){
						passed = false;
					}
				}

if(passed){
					res = max(res, e - i + 1);

//ovaa "optimizacija" ja ubrzuva programata dovolno za vremenskite limiti
					//no kontraprimerot pokazuva deka e greska
					i = e;
					break;
				}
			}
		}
	}

cout << res;
}

ReaLNero wrote:Programava ima kontraprimer, no na mendo nema takov test primer. Zar treba da se vazi kako tocno resenie?

Kontraprimerot e : ABBAABBAAAAAAAAAAAA
Tocnoto e: AAA AAA AAA AAA - 12
Programata dava: AB BA AB BA - 8

Не ја разгледав задачата и примерите, ама чисто како одговор на коментарот - не е баш најоптимално, ама се случува (како кај нас, така и на други национални и меѓународни натпревари). Едноставно, никогаш неможе да се стават сите можни тест примери за оценување (оти сакаме оценувањето да трае кратко време), ама па (бидејќи не се ставаат сите) можно е да пројде и некој код кој нема најточно/најоптимално решение.
Има вакви дискусии на форумот на TopCoder и CodeForces, па можеш таму да прочиташ повеќе ако сакаш.