Curs 3. Two Pointers
https://www.pbinfo.ro/probleme/4301/gustare
https://www.pbinfo.ro/probleme/3872/cnt-seq-max-min
Se da un șir de numere naturale să se determine secvența de lungime maxima care are diferenta dintre minim și maxim mai mica decat K
Se dă o matrice de dimensiuni N x M de numere naturale. Se cere determinarea unei submatrici cu număr maxim de celule în care diferenţa între valoarea maximă şi valoarea minimă este mai mică decât o valoare dată K. Restrictii: 2 ≤ N, M ≤ 150, 1 ≤ K ≤ 1 000.
https://www.infoarena.ro/problema/secv2
https://infoarena.ro/problema/nane
https://www.infoarena.ro/problema/propozitie
GUSTARE
for(int i = 1; i <=n ;++i) {
cin >>corn[i];
}
for(int i = 1; i <=m ;++i) {
cin >>apple[i];
}
sort(corn+1,corn+n+1);
sort(apple+1,apple+m+1);
cin >> t;
for(int i = 1; i <= t; ++i) {
cin >> x;
int apple_pointer = n;
int corn_pointer = 1;
found = false;
while(apple_pointer <= n || corn_pointer <= m) {
int suma = corn[corn_pointer] + apple[apple_pointer];
if(suma == x){
found = true;
cout << "DA\n";
break;
}
else
if(suma < x ) {
corn_pointer++;
}
else
{ apple_pointer--;
}
}
if(!found)
cout << "NU\n";
}corn 2 2 3 5
apple 2 4 6
corn_pointer si apple_pointer
Cum verificam daca este corect sa folosim TWO POINTTERS
https://www.pbinfo.ro/probleme/3872/cnt-seq-max-min
Daca st.....dr - este o secventa valida atunci si st+1...dr sau st ... dr-1 sau orice secventa din interior este valida
Spre exemplu max(st..dr) - min(st...dr) <= T;
P.p ca max(st..dr) - min(st...dr) <= T; - valida
Dem. ca st+1...dr este valida
St era chiar minimul => min(st+1,dr) a crescut => max(st+1..dr) - min(st+1...dr) <= T
St era chiar maximul -> max(st+1..dr) a scazut => max(st+1..dr) - min(st+1...dr) <= T -> valida
St nu era nimic => st+1...dr -> valida
#include <mutliset>
using namespace std;
multiset<int> ms;
st = 1;
for(int dr = 1; dr <= n; ++dr){
ms.insert(a[dr]);
s += a[dr];
int MIN = *ms.begin(); -> ms este un "vector sortat" deci valorea minima este la inceput, dar begin este o pozitie(pointer) al multisetului, pentru a afla valoarea avem nevoie de *ptr = val
int MAX = *ms.rbegin();
if(MAX.- MIN <= T) { //valida
//st....dr - >valida si este cea mai mare secventa valida cu capatul dr si toate secventele din interior sunt valide
nrsecv+=dr-st+1;
}
else {
while(MAX - MIN > T && st < dr) {
ms.erase (ms.find(a[st]));
++st;
MIN = *ms.begin();
MAX = *ms.rbegin();
}
nrsecv+=dr-st+1;
}
}
dr = 1
st = 1
1.1 -> 1 secventa
dr = 2
st = 1
1 2
2 2
dr = 3
st = 1
1 3
2 3
3 3
N* log2N
Pentru a determina secvential minimul si maximul exista 3 algoritmi:
SET/MULTISET din STL -> Cls 7 in sus
DEQUE -> Cls 8 in sus
RMQ -> Cls 10 in sus
UNORDERD_MAP
HASH_MAP
int moduloA = 66783, moduloB = 55533;
0,0:
0:
2:
3: (3,1),
...
....
62039 : (2132312, 5) . .... ....;......
66782
unorederd_map<int,int> mp;
mp[3]= 1;
mp[2132312] = 5;
cout << mp[2132312];
N/66783
int modulo = 66783
0:
1:
2:
3: (3,1),
...
....
62039 : (2132312, 5) . .... ....;......
66782
c <= 10
5 T = 2
1 7 2 3 4
ms :2 3
st = 1 dr = 1
MIN = 1
MAX = 1 => valida : 1 1
st = 2 dr = 2
MIN = 7
MAX = 7 => valida : 2 2
st = 3 dr = 3
MIN = 2
MAX = 7 => valida 3 3
st = 3 dr = 4
MIN = 2
MAX = 3=> valida : 3 4 4 4
st = 1, dr = 1
for(int dr =1; dr<= n; ++dr) { // se variaza dreapta
//introducem pe a[dr]
if(valida(st...dr)) {
nrsecv += dr-st+1;
lung_max = max(dr-st+1);
}
else {
while(nu este valida(st...dr) && st<=dr) {
// il scoatem pe a[st]
++st;
}
if(valida(st...dr)) {
nrsecv += dr-st+1;
lung_max = max(dr-st+1);
}
}
}Conditia TWO POINTTERS: st....dr -> valid => st+1...dr - valid.
OPERTATII PE BITI
14 = 1110 = 0 * 2^0 + 1*2^1 + 1 * 2^2 + 1 * 2^3 = 14
14/2 = 7 rest 0
7 / 2 = 3 rest 1
3/ 2 = 1 rest 1
1/2 = 0 rest 1
14 = 1110
3 = 0011
1110
0011 (|) OR |
-------
0 | 0 = 0
0 | 1 = 1
1 | 1 = 1
1 | 0 =. 1
1110
0011 (|) OR |
-------
1111 = 15
14 | 3 = 15Presupunem st.....dr este valida => st+1 dr este valida
st = 1, dr = 1
int frecvbit[35];;
void add(int x){
int sir[32];
int cnt = 0;
while(x > 0){
sir[++cnt] = x%2;
x/=2;
}
int bit = 0;
for(int i = cnt; i>= 1; --i) {
if(sir[i] == 1)
frecvbit[bit]++;
++bit;
}
}
void remove(int x){
int sir[32];
int cnt = 0;
while(x > 0){
sir[++cnt] = x%2;
x/=2;
}
int bit = 0;
for(int i = cnt; i>= 1; --i) {
if(sir[i] == 1)
frecvbit[bit]--;
++bit;
}
}
int nr_biti() {
int nr =0;
for(int i = 0; i<= 31; ++i)
if(frecvbit[i] == 1)
++nr;
return nr;
}
int main() {
for(int dr =1; dr<= n; ++dr) { // se variaza dreapta
add(a[dr]);
if(nr_biti() <= k) {
nrsecv += dr-st+1;
lung_max = max(dr-st+1);
}
else {
while(nr_biti() > k && st<=dr) {
remove(a[st]);
++st;
},
if(nr_biti() <= k) {
nrsecv += dr-st+1;
lung_max = max(dr-st+1);
}
}
}
}
O(N)
Se dă o matrice de dimensiuni N x M de numere naturale. Se cere determinarea unei submatrici cu număr maxim de celule în care diferenţa între valoarea maximă şi valoarea minimă este mai mică decât o valoare dată K. Restrictii: 2 ≤ N, M ≤ 150, 1 ≤ K ≤ 1 000.
cin >> N >> M;
for(int i= 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
cin >> a[i][j];
5 5 10 5
-3 9 1 2-
-4 10 1 2-
int MIN[M], MAX[M];
for(int lin_start= 1; lin_start <= n; ++lin_start) {
for(int j = 1; <= m; ++j)
MAX[j] = mica, MIN[j] = mare;
for(int lin_final = lin_start; lin_final <= n; ++ lin_final) {
for(int j = 1; j <= m; ++j) {
MAX[j] = max(MAX[j],a[j]);
MIN[j] = min(MIN[j],a[j]);
}
multiset<int> ms;
st = 1;
for(int dr = 1; dr <= m; ++dr){
ms.insert(MAX[dr]);
ms.insert(MIN[dr]);
int MIN = *ms.begin(); -> ms este un "vector sortat" deci valorea minima este la inceput, dar begin este o pozitie(pointer) al multisetului, pentru a afla valoarea avem nevoie de *ptr = val
int MAX = *ms.rbegin();
if(MAX.- MIN <= T) { //valida
//st....dr - >valida si este cea mai mare secventa valida cu capatul dr si toate secventele din interior sunt valide
nrsubmat+=dr-st+1;
}
else {
while(MAX - MIN > T && st < dr) {
ms.erase (ms.find(MIN[st]));
ms.erase (ms.find(MAX[st]));
++st;
MIN = *ms.begin();
MAX = *ms.rbegin();
}
nrsecv+=dr-st+1;
}
}
}
n^2*m*log2(m)
set<int> s;
s.insert(29);
s.insert(30);
s.insert(29)
s = 29 30