L2: Divide and Conquer
Posible flujo de trabajo
- descargar el archivo .zip
de el problema de el Jutge.org 
que se quiere resolver -
unzipel archivo - en la carpeta obtenida teneis:
- un file .pdf con el enunciado del problema,
- uno o más files de texto con ejemplos de input
sample.inp - los correspondiente outputs correctos
sample.cor
- crear un file con el vuestro codigo sorgente C++ para resolver el problema
- compilar el codigo sorgente con
g++ -std=c++11.
Posibles flags utiles:-Wall -Wextra -Wno-overflow -Wpedantic -Werror -D_GLIBCXX_DEBUG - testar el ejecutable en los ejemplos:
por ejemplo con./a.out < sample.inp > output - testar que el file de
outputsea correcto:
por ejemplo condiff output sample.cor - una vez que estais convencidos que vuestra solucion es correcta, enviarla al Jutge
- no enviar al Jutge soluciones que no sean correctas en los ejemplos que teneis!
- no intentar re-escribir a mano los ejemplos de input
Problemas sobre Divide and Conquer
Los problemas de el apartado EDA Curs 2023/2024 Q2 \(\rightarrow\) Divide and Conquer.
P81966 Dichotomic search
P84219 First occurrence
P29212 Modular exponentiation
P33412 Resistant dichotomic search (~ Problem 2.12 seen in Problem class P3)
P34682 Fixed points 
P61833 Powers of a matrix
P74219 Fibonacci numbers (2)
P80595 How many inversions? (~ Problem 2.11 seen in Problem class P3)
P58512 Interest rates
X39049 Powers of permutations
X82938 Search in a unimodal vector (~ Problem 2.9 seen in Problem class P3)
= the problem might be harder than the rest
Problemas resueltos en clase
P29212 Modular exponentiation
Possible C++ code to start problem P29212
#include<iostream>
using namespace std;
int power(int n, int k, int m){
// do something here
}
int main(){
/*
const int M_MAX = 30000;
const int N_MAX = 30000;
*/
int n, k, m;
while(cin >> n >> k >> m){
cout << power(n, k, m) << endl;
}
}
Possible solution
#include<iostream>
using namespace std;
int power(int n, int k, int m){
if (k == 0) return 1;
int y = power(n, k/2, m);
int res = (y*y) % m;
if (k % 2 == 1) return (n*res) % m;// return (n*y*y) % m; is NOT OK!
else return res;
}
int main(){
/*
const int M_MAX = 30000;
const int N_MAX = 30000;
*/
int n, k, m;
while(cin >> n >> k >> m){
cout << power(n, k, m) << endl;
}
}
P61833 Powers of a matrix
Possible C++ code to start problem P61833
#include<iostream>
#include<vector>
using namespace std;
typedef vector<vector<int>> Matrix;
int m;
ostream& operator << (ostream& out, const Matrix& a){
// to format the output
}
Matrix operator*(const Matrix& a, const Matrix& b) {
// Matrix multiplication. The textbook algorithm is enough
// No need to implement Strassen here
}
Matrix operator%(const Matrix& a, int m){
// Modulo operator on a matrix is entrywise
}
Matrix identity(){
// For the identity matrix
}
Matrix power(const Matrix& a, int n, int m){
// Power of a matrix. Similar to P29212 Modular exponentiation
}
int main(){
Matrix a(2,vector<int>(2));
int n;
while(cin >> a[0][0] >> a[0][1] >> a[1][0] >>a[1][1] >> n >> m){
cout << power(a,n,m) << endl;
}
}
Possible solution
#include<iostream>
#include<vector>
using namespace std;
typedef vector<vector<int>> Matrix;
int m;
ostream& operator << (ostream& out, const Matrix& a){
out << a[0][0] << " " << a[0][1] << endl;
out << a[1][0] << " " << a[1][1] << endl;
out << "----------";
return out;
}
Matrix operator*(const Matrix& a, const Matrix& b) {
Matrix c(2, vector<int>(2, 0));
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 2; ++k){
c[i][j] += a[i][k] * b[k][j];
}
return c;
}
Matrix operator%(const Matrix& a, int m){
Matrix c(2,vector<int>(2,0));
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
c[i][j] = a[i][j] % m;
return c;
}
Matrix identity(){
Matrix id(2,vector<int>(2,0));
for (int i = 0; i < 2; ++i)
id[i][i] = 1;
return id;
}
Matrix power(const Matrix& a, int n, int m){
if (n == 0) return identity();
Matrix c = power(a, n/2, m);
return (n%2==0) ? (c*c) % m : (a*c*c) % m;
}
int main(){
Matrix a(2,vector<int>(2));
int n;
while(cin >> a[0][0] >> a[0][1] >> a[1][0] >>a[1][1] >> n >> m){
cout << power(a,n,m) << endl;
}
}
P34682 Fixed points
Possible C++ code to start problem P34682
#include<iostream>
#include<vector>
using namespace std;
int fixpoint(const vector<int> &v, int left, int right, int a){
// This procedure should return the smallest fixed point,
// i.e. the smallest i s.t. v[i] + a == i
// Would your divide and conquer approach work if v[1] <= v[2] <= v[3] ...?
}
int main(){
int cnt = 1;
int n;
while (cin >> n ){
vector<int> v(n+1);//Indices start at 1
for(int i = 1; i <=n; ++i)
cin >> v[i];
int m;
cin >> m;
vector<int> a(m);
for (int i = 0; i < m; ++i)
cin >> a[i];
cout << "Sequence #" << cnt << endl;
for (int i = 0; i < m; ++i){
// Call fixpoint(v, 1, n, a[i]); and do something
}
cout << endl;
++cnt;
}
}
Possible solution
#include<iostream>
#include<vector>
using namespace std;
int fixpoint(const vector<int> &v, int left, int right, int a){
if (left > right) return -1;
if (left == right){
if (v[left] + a == left) return left;
else return -1;
}
int mid = (left+right)/2;
/*
Since the ordering on v is strict, for k>0
v[x-k]<=v[x]-k
therefore if v[x] + a < x then
v[x-k] +a <= v[x] - k +a < x - k
hence, x-k cannot be a fixpoint
*/
if (v[mid] + a < mid) return fixpoint(v, mid+1, right, a);
else return fixpoint(v, left, mid, a);
}
int main(){
int cnt = 1;
int n;
while (cin >> n ){
vector<int> v(n+1);//Indices start at 1
for(int i = 1; i <=n; ++i)
cin >> v[i];
int m;
cin >> m;
vector<int> a(m);
for (int i = 0; i < m; ++i)
cin >> a[i];
cout << "Sequence #" << cnt << endl;
for (int i = 0; i < m; ++i){
int fp = fixpoint(v, 1, n, a[i]);
if (fp>=0) cout << "fixed point for " << a[i] << ": " << fp << endl;
else cout << "no fixed point for " << a[i] << endl;
}
cout << endl;
++cnt;
}
}