Omówienie zadania Magic / Europejska Olimpiada Informatyczna Juniorów

Omówienie zadania Magic / Europejska Olimpiada Informatyczna Juniorów

Szczegółowe omówienie zadania Magic z Europejskiej Olimpiady Informatycznej Juniorów:
Link do powyższego omówienia zadania Magic:
https://youtu.be/UB6W7Dd_a3I
Link do zadania Magic:
https://mendo.mk/Task.do?id=774


Zadanie Magic pochodzi z I finału Europejskiej Olimpiady Informatycznej Juniorów.
Wymaga użycia jednej z dwóch technik:
* sum prefiksowych
* hashy

Rozwiązanie które omawia w filmie Mikołaj Bulge – brązowy medalista tych zawodów EJOI – wykorzystuje sumy prefiksowe.
Poniżej znajduje się kod obydwu możliwych rozwiązań zadania – za pomocą sum prefiksowych jak też hashy.

Zadanie na zawodach zrobiło na maksymalną ilość punktów 19 osób z 89 startujących:
https://ejoi.org/scoreboard/
Lista laureatów tych zawodów:
https://ejoi.org/ejoi-news/


Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625

Mikołaj Bulge jest prowadzącym zaawansowane zajęcia w ramach Olimpijskiego Koła Informatycznego:
https://oki.org.pl/harmonogram-zajec/
Chcesz dostawać informacje o zajęciach? – Zapisz się na newsletter OKI:
https://oki.org.pl/newsletter.php
Lista zadań z Olimpiad i konkursów informatycznych z podziałem na kategorie i rozwiązaniami:
https://oki.org.pl/lista-zadan-materialy.php


Kod C++ programu Magic, który jest omówiony w powyższym filmie i który otrzymuje 100%

#include<bits/stdc++.h>
using namespace std;

constexpr int mod=1e9+7;

int assigned[207];
vector<int>cnt;
map<vector<int>,int>mapa;
string s;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	char c;
	int n,res=0,x=0;
	cin>>n>>s;
	
	s='#'+s;
	
	for(int i=1; i<=n; i++){
		c=s[i];
		if(assigned[c]) continue;
		assigned[c]=++x;
		cnt.push_back(0);
	}

	mapa[cnt]++;
	
	for(int i=1; i<=n; i++){
		c=s[i];
		
		if(assigned[c]==1) for(int j=1; j<cnt.size(); j++) cnt[j]--;
		else cnt[assigned[c]-1]++;
		
		res+=mapa[cnt];
		mapa[cnt]++;
		
		if(res>=mod) res-=mod;	
	}
	
	cout<<res;
	
	return 0;
}

//UWAGA: Pomiędzy tym kodem a omówieniem na przykładzie wkradła się drobna nieścisłość (na szczęście nie wpływa w żaden sposób na poprawne działanie kodu).
//Jeśli postępować zgodnie z omówieniem , linijki 34 i 35 powinny wyglądać tak:
//	if(assigned[c]==1) for(int j=1; j<cnt.size(); j++) cnt[j]++;
//	else cnt[assigned[c]-1]--;

//Dla wszystkich którzy to wychwycili: brawo!!!
Link do pliku ze wzorcowym kodem C++ zadania Magic  
=
=
Poniżej kod który otrzymuje również 100%, ale który wykorzystuje hashe
#include <bits/stdc++.h>
using namespace std
// 100003 100019
long long pot1[55];
long long pot2[55];
long long tab[55];

int main() {
ios_base::sync_with_stdio(0); cin.tie(0); pot1[0]=1;

pot2[0]=1;
for(int i=1;i<=53;i++) {
   pot1[i]=pot1[i-1]*100003;
   pot1[i]%=1000000007;
   pot2[i]=pot2[i-1]*100019;
   pot2[i]%=1000000009;
}

map<pair,int> mapa;
map<char,short> kod;

short counter=1;
int n;
cin>>n;
string str;
cin>>str;

for(int i=0;i<n;i++) {
   if(kod[str[i]]==0) kod[str[i]]=counter++;
}
int res=0;
long long mini=0;
mapa[make_pair(0,0)]++;
long long act1=0;
long long act2=0;
for(int i=0;i<n;i++) {
   tab[kod[str[i]]]++;
   mini=100000007;
   bool b=1;
   for(short j=1;j<counter;j++) {
      mini=min(mini,tab[j]);
   }
   for(short j=1;j<counter;j++) tab[j]-=mini;
   act1=0;
   act2=0;
   for(short j=1; j<counter; j++) {
      act1+=tab[j]*pot1[j-1];
      act1%=1000000007;
      act2+=tab[j]*pot2[j-1];
      act2%=1000000009;
   }
   res+=mapa[make_pair(act1,act2)]++;
   res%=1000000007;
}
cout<<res;
return 0;
}

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz