[BLOG] soluções obi

obi2018-baldes.md

Enunciado
Na minha primeira leitura, vi que esta é uma questão clássica de segtree. Um vetor de tamanho 10^5 e 10^5 queries dentro desse intervalo. Iremos fazer uma segtree para o mínimo num intervalo e outra para o máximo, sendo a resposta da query em um intervalo o max-min. Para simplificar isso, podemos guardar as duas árvores apenas em um vetor de pairs.

Porém após implementar a primeira solução e não funcionar fiz uma segunda leitura e percebi que o max e o min não podem estar no mesmo balde (na mesma posição no vetor). Então troquei o pair por uma struct, para guardar de qual balde o max e o min vieram. Quando o min e o max estiverem no mesmo balde temos uma certeza, um dos dois faz parte da solução. Nesse caso podemos testar, o query sem o min, mas com o max e o query sem o max, mas com o min.

#include <bits/stdc++.h>
typedef struct ii {
    int first;
    int second;
    int i;
    int j;
} ii;
using namespace std;

const int MAX = 5e5+50;
const int inf = 0x3f3f3f3f;

ii tree[MAX]={};
int arr[MAX];

ii merge(ii a, ii b) {

    ii c = {min(a.first,b.first),max(a.second,b.second),-1,-2};

    if(c.first==a.first) c.i=a.i;
    else c.i=b.i;

    if(c.second==a.second) c.j=a.j;
    else c.j=b.j;

    return c;
}

void build(int pos, int i, int j) {
    if(i==j) {
        tree[pos]={arr[i],arr[i],i,i};
        if(arr[i]==0) {
            tree[pos]={inf,-inf,-1,-2};
        }
    } else {
        build(2*pos,i,(i+j)/2);
        build(2*pos+1,(i+j)/2+1,j);

        tree[pos]=merge(tree[2*pos],tree[2*pos+1]);
    }
}

void update(int pos, int i, int j, int target, ii val) {
    if(i==j) {
        if(tree[pos].first!=0&&tree[pos].second!=0) {
            tree[pos]=merge(tree[pos],val);
        } else {
            tree[pos]=val; 
        }
    } else {
        if(target <= (i+j)/2) update(2*pos,i,(i+j)/2,target,val);
        else update(2*pos+1,(i+j)/2+1,j,target,val);

        tree[pos]=merge(tree[2*pos],tree[2*pos+1]);
    }
}

void force_update(int pos, int i, int j, int target, ii val) {
    if(i==j) {
        tree[pos]=val; 
    } else {
        if(target <= (i+j)/2) force_update(2*pos,i,(i+j)/2,target,val);
        else force_update(2*pos+1,(i+j)/2+1,j,target,val);
        tree[pos]=merge(tree[2*pos],tree[2*pos+1]);
    }
}

ii query(int pos, int i, int j, int a, int b) {
    if(i>b||j<a) {
        return {inf,-inf, -1, -2};
    } else if(i>=a&&j<=b) {
        return tree[pos];
    } else {
        return merge(query(2*pos,i,(i+j)/2,a,b),query(2*pos+1,(i+j)/2+1,j,a,b));
    }
}

int main() {

    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++) scanf("%d",&arr[i]);

    build(1,0,n);

    for(int i=0;i<m;i++) {
        int op;
        scanf("%d",&op);

        if(op==1) {
            int w,p;
            scanf("%d%d",&w,&p);
            --p;
            update(1,0,n,p,{w,w,p,p});
        } else {
            int a,b;
            scanf("%d%d",&a,&b);
            --a,--b;
            ii p = query(1,0,n,a,b);

            if(p.i==p.j) {
                ii tmp = p;
                int ans=0;
                force_update(1,0,n,p.i,{p.first,-inf,p.i,p.j});
                ii A = query(1,0,n,a,b);
                force_update(1,0,n,p.i,{inf,p.second,p.i,p.j});
                ii B = query(1,0,n,a,b);

                ans=max(A.second-A.first,B.second-B.first);
                printf("%d\n",ans);

                update(1,0,n,p.i,p);
            } else {
                printf("%d\n",p.second-p.first);
            }
        }
        
    }

    return 0;
}

obi2018-bolas.md

Enunciado
Como o tamano do vetor é 8 e temos sempre 8 números para escolher, exitem 8! permutações possíveis. Como 8! é pequeno, podemos fazer uma solução de busca completa. Existem de varias soluções possíveis como com next_permutation. Segue uma solução de backtracking:

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

int vet[9]={};

int solve(int pos, int n) {
    if(pos==8) return 1;
    
    int ans=0;

    for(int i=0;i<=9;i++) {
        if(n != i && vet[i]) {
            vet[i]--;
            ans|=solve(pos+1,i);
            vet[i]++;
        }
    }

    return ans;
}

int main() {

    for(int i=0;i<8;i++) {
        int aux;
        scanf("%d",&aux);
        vet[aux]++;
    }

    int ans=solve(0,-1);
    puts(ans?"S":"N");

    return 0;
}

obi2018-cinco.md

Enunciado
Podemos criar um algoritmo guloso simples, trocar sempre (em ordem):

1. O dígito mais significativo que for trocado por um número maior do que ele
2. (na falha do primeiro) O dígito menos significativo que for trocado por um número menor do que ele

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

int main() {

    int n;
    scanf("%d",&n);
    int arr[n];

    for(int i=0;i<n;i++) scanf("%d",&arr[i]);

    for(int i=0;i<n;i++) {
        if(arr[i]<arr[n-1]&&(arr[i]==0||arr[i]==5)) {
            swap(arr[i],arr[n-1]);
            for(int j=0;j<n;j++) printf("%d%c",arr[j],j==n-1?'\n':' ');
            exit(0);
        }
    }

    for(int i=n-1;i>=0;i--) {
        if(arr[i]==0||arr[i]==5) {
            swap(arr[i],arr[n-1]);
            for(int j=0;j<n;j++) printf("%d%c",arr[j],j==n-1?'\n':' ');
            exit(0);
        }
    }

    puts("-1");

    return 0;
}

obi2018-maximin.md

Enunciado
Como o tamanho máximo do vetor é 10^5 podemos ordená-lo. Fazendo isso podemos ver que o número que estamos procurando está entre dois números vizinhos no vetor ou está em alguma das extremidades.

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

int main() {
    int n,r,l;
    scanf("%d%d%d",&n,&r,&l);
    int arr[n];
    for(int i=0;i<n;i++) scanf("%d",&arr[i]);

    sort(arr,arr+n);

    int dif=0;
    for(int i=1;i<n;i++) {
        int mid=(arr[i]+arr[i-1])/2;
        if(mid>=r&&mid<=l) dif=max(dif,min(abs(mid-arr[i]),abs(mid-arr[i-1])));
    }

    if(l>arr[n-1]) dif=max(dif, l-arr[n-1]);
    if(r<arr[0]) dif=max(dif,arr[0]-r);

    printf("%d\n",dif);

    return 0;
}

obi2018-muro.md

Enunciado
Podemos criar uma função recursiva: f(n) = f(n-1) + 4*f(n-2) + 2*f(n-3). Como existem estados que irão se repetir, podemos usar um vetor para guardar o valor da função já computados.

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

const int mod = 1e9+7;
const int MAX = 1e4+20;

int dp[MAX]={};

int solve(int pos) {
    if(pos==0) return 1;
    if(~dp[pos]) return dp[pos];

    int ans=0;

    ans = (ans+solve(pos-1))%mod;
    if(pos>=2) ans = (ans+4*solve(pos-2))%mod;
    if(pos>=3) ans = (ans+2*solve(pos-3))%mod;

    return dp[pos]=ans;
}

int32_t main() {

    memset(dp,-1,sizeof(dp));
    int n;
    scanf("%lld",&n);

    printf("%lld\n",solve(n));

    return 0;
}