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!!!
=
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;
}