Clase 10: Recapitulación I

Complete Search 3.0 + 1.0: You Can (Not) TLE

Calentamiento

Para ir activando nuestra mente, vayamos resolviendo los siguientes problemas:

Far Relative’s Problem

Code

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

const int N = 5000 + 5;

int n;
int L[N];
int R[N];
char G[N];

int main() {
    scanf("%d\n",&n);
    for(int i=0; i<n; i++){
        scanf("%c %d %d\n",G+i,L+i,R+i);
    }
    int ans = 0;
    for(int day = 1; day <= 366; day++){ // Iteramos sobre los dias
        int QF = 0;
        int QM = 0;
        for(int i=0; i<n; i++){ // Verificamos quienes estan disponibles
            if(L[i] <= day and day <= R[i]){
                if(G[i] == 'F') QF++;
                else QM++;
            }
        }
        ans = max(ans,2*min(QF,QM)); // Maximizamos la respuesta
    }
    cout << ans << endl;
    return 0;
}

Greed

Code

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

const int N = 100000+5;

int n;
int a[N];
int b[N];

void solveLinear(){ // Solucion obteniendo los 2 maximos en O(n)
    long long sumA = 0LL;
    for(int i=0; i<n; i++){
        sumA += a[i];
    }
    int max1 = -1, max2 = -1;
    for(int i=0; i<n; i++){
        if(max2 < b[i]){
            max2 = b[i];
        }
        if(max1 < max2) swap(max1,max2);
    }
    puts(max1 + max2 >= sumA? "YES":"NO");
}

void solveNlogN(){ // Solucion usando sort
    long long sumA = 0LL;
    for(int i=0; i<n; i++){
        sumA += a[i];
    }
    sort(b,b+n);
    puts(b[n-1] + b[n-2] >= sumA? "YES":"NO");
}

int main(){
    scanf("%d",&n);
    for(int i=0; i<n; i++) scanf("%d",a+i);
    for(int i=0; i<n; i++) scanf("%d",b+i);
    srand(time(0)); // Aleatoriamente usará alguna de las dos soluciones :v
    if(rand()&1) solveLinear();
    else solveNlogN();
    return 0;
}

DZY Loves Chessboard

Code

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

const int N = 100+5;

int n, m;
char s[N][N];

int main(){
    scanf("%d %d",&n,&m);
    for(int i=0; i<n; i++){
        scanf("%s",s[i]);
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(s[i][j] == '-') putchar('-');
            else putchar((i + j) & 1? 'W' : 'B');
        }
        puts("");
    }
    return 0;
}

Perfect Number

Code

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

int k;

bool perfect(int x){
    int sum = 0;
    while(x > 0){
        sum += x % 10;
        x /= 10;
    }
    return sum == 10;
}

int main(){
    scanf("%d",&k);
    int ans = 10; // Indice = 0 (?), El primer numero es 19
    while(k > 0){
        ans += 9;
        if(perfect(ans)) k -= 1;
    }
    printf("%d\n",ans);
    return 0;
}

Fuerza Bruta

Veamos el análisis de los siguientes problemas:

Magic Powder - 1

Enunciado: Deseas cocinar galletas y en la receta hay \(n\) ingredientes. Para preparar una galleta, necesitas \(a_{i}\) gramos del \(i\)-ésimo ingrediente. En estos momentos, dispones de \(b_{i}\) gramos del ingrediente correpondiente.

Quieres preparar la máxima cantidad de galletas posible y para ello tienes \(k\) gramos de una especia mágica, la cual se puede transformar en cualquiera de los \(n\) ingredientes.

Determina dicha máxima cantidad posible.

\[ 1 \leq n, k \leq 1000 \] \[ 1 \leq a_{i}, b_{i} \leq 1000 \]

Solución

Notemos que podemos fijar la cantidad de galletas que se deberían preparar y en base a ello analizar si es posible hacerlo.

Si queremos preparar \(x\) galletas, necesitaremos:

\[ needed = \sum_{i=1}^{n}\max{\{0,x\cdot a_{i} - b_{i}\}} \]

Además, notemos que el límite máximo para la cantidad de galletas posible es \(2000\), así que podemos simplemente iterar desde \(x = 0\) y sumarle de a uno hasta que ya no se pueda.

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

const int N = 1000+5;

int n, k;
int a[N];
int b[N];

bool can(int x){
    int needed = 0;
    for(int i=1; i<=n; i++){
        needed += max(0, x * a[i] - b[i]);
    }
    return needed <= k;
}

int main(){
    scanf("%d %d",&n,&k);
    for(int i=1; i<=n; i++) scanf("%d",a+i);
    for(int i=1; i<=n; i++) scanf("%d",b+i);
    int ans = -1;
    while(can(ans+1)) ans += 1;
    printf("%d\n",ans);
    return 0;
}

Restoring Painting

Enunciado: Tienes un cuadro de \(3\times 3\), donde cada celda puede tener un número entero del \(1\) al \(n\). El cuadro cumple con que la suma de cada cuadrado de \(2 \times 2\) dentro de él tiene la misma suma. Dados los valores \(a\), \(b\), \(c\) y \(d\), determinar la cantidad de cuadros diferentes que se pueden obtener.

\[ 1 \leq n \leq 10^{5} \]

Solución

Notemos que podemos fijar alguna de las esquinas y cada una de las otras esquinas podrá ser deducido considerando la suma constante. Si las esquinas tienen valores válidos, entonces el centro puede tomar \(n\) valores diferentes, los cuales debemos considerar para el conteo.

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

int n;
int a, b, c, d;

bool valid(int a11){
    int a31 = a11 + a - d;
    int a13 = a11 + b - c;
    int a33 = a31 + b - c;
    return 1 <= min({a13,a31,a33}) and max({a13,a31,a33}) <= n;
}

int main(){
    scanf("%d %d %d %d %d",&n,&a,&b,&c,&d);
    long long ans = 0LL;
    for(int i=1; i<=n; i++){
        if(valid(i)) ans += n;
    }
    printf("%lld\n",ans);
    return 0;
}

Binary Number

Enunciado: Tienes un número \(x\) en base binaria, al cual le realizarás el siguiente procedimiento:

ans = 0
while x != 1:
    if x % 2 == 1:
        x += 1
    else:
        x /= 2
    ans += 1

Sin embargo, te darán \(x\) en base binaria y además puede tener hasta \(10^{6}\) dígitos. Se te pide hallar la respuesta que se obtendría en el proceso.

Solución

Consideremos que realizamos la suma de manera trivial (sumando 1 al siguiente orden del número o añadiendo un 1 al final si estamos en la última posición) y que estamos en el orden \(i\) con el valor \(v_{i}\).

No es difícil notar que el valor de \(x\) se vuelve \(1\) cuando:

• \(i + 1 == v.size()\)

• \(v_{i} == 1\)

• \(\left\lfloor\frac{v_{i}}{2} \right\rfloor == 0\)

Debido a que no tendríamos ningún dígito más ni podríamos agregar ningún 1. Entonces basta con simular con un vector o string el procedimiento con este análisis y sumar a la respuesta de manera correspondiente.

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

const int N = 1000000+5;

int len;
char s[N];

int solve(vector<int> &v){
    int ans = 0;
    for(int i=0; i < v.size(); i++){
        int carry = v[i] / 2;
        v[i] %= 2;
        if(carry){
            if(i + 1 < v.size()) v[i+1] += carry;
            else v.emplace_back(carry);
        }
        if(v[i] & 1){
            if(i + 1 < v.size()) v[i+1] += 1;
            ans += 1;
        }
        ans += 1;
    }
    return ans;
}

int main(){
    scanf("%s",s);
    vector<int> x;
    for(int i = strlen(s) - 1; i >= 0; i--){
        x.emplace_back(s[i] - '0');
    }
    int ans = solve(x) - 2;
    cout << ans << endl;
    return 0;
}

Backtracking

Ahora recordemos Backtracking con algunos problemas más:

Dreamoon and WiFi

Enunciado: Dada una secuencia de operaciones \(s\) en la cual un símbolo \(+\) significa sumar 1 a la coordenada actual y un símbolo \(-\) significa restarle 1, determinar la probabilidad de que, luego de reemplazar algunos signos de interrogación de otra secuencia de la misma longitud por \(+\) o \(-\), se llegue a la misma coordenada. Considerar que la probabilidad de elegir \(+\) o \(-\) como reemplazo de un \(?\) es 0.5.

\[ |s| \leq 10 \]

Solución

Este problema consiste en simular el valor de la coordenada llevando además la probabilidad de los pasos realizados. Nuestra elección será usar backtracking.

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

const int N = 15;

int X;
char s[N];
double ans = 0.0;
int dx[] = {1,-1};
double p[] = {0.5,0.5};

void backtracking(int pos, int x, double prob){
    if(!s[pos]){
        if(x == X) ans += prob;
        return;
    }
    if(s[pos] == '?'){
        for(int i=0; i<2; i++){
            int nx = x + dx[i];
            backtracking(pos+1,nx,prob * p[i]);
        }
    }
    else backtracking(pos+1,x + (s[pos] == '+'? 1 : -1), prob);
}

int main(){
    scanf("%s",s);
    for(int i=0; s[i]; i++){
        X += s[i] == '+'? 1 : -1;
    }
    scanf("%s",s);
    backtracking(0,0,1.0);
    printf("%.10lf\n",ans);
    return 0;
}

Stone Pile

Enunciado: Dados \(n\) elementos con pesos \(w_{i}\), particionarlos en 2 grupos de forma que la diferencia entre la suma de sus pesos sea la mínima posible.

Solución

Podemos relacionar este problema con un problema de la mochila, dado que cada elemento puede tomar 1 de 2 opciones.

Con lo anterior, podríamos llevar ambos conjuntos de elementos para hallar sus sumas al final de todas las decisiones y minimizar la respuesta cada vez.

Sin embargo, una forma más eficiente sería sólo llevar la suma de pesos del conjunto con menor suma de pesos, dado que si tenemos que este conjunto tiene suma \(W\) y la suma de todos los elementos es \(S\), la respuesta sería minimizar:

\[ f(W) = (S - W) - W = S - 2\cdot W \]

Por lo que basta llevar solo este dato y siempre asegurarnos de que \(W \leq S - W\). Asegurarse de que la respuesta esté inicializada en \(\infty\).

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

const int N = 20 + 5;

int n;
int S;
int ans;
int w[N];

void backtracking(int pos, int smaller){
    if(pos == n){
        ans = min(ans, S - 2 * smaller);
        return;
    }
    if(smaller + w[pos] <= S - (smaller + w[pos])){
        backtracking(pos+1,smaller + w[pos]);
    }
    backtracking(pos+1,smaller);
}

int main(){
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%d",w+i);
        S += w[i];
    }
    ans = S;
    backtracking(0,0);
    printf("%d\n",ans);
    return 0;
}

¡Ahora pongamos en práctica lo que hemos recordado!

Entremos a Contest.