Olá todos!

Esse é o primeiro editorial feito pelos alunos da UECE no Codeforces. Esse contest foi criado como um treino do grupo de estudos da maratona. A seleção das questões do UVa, organização do contest foi feita com muito empenho pelo alissonrgs. Obrigado especial aos que ajudaram a fazer este editorial: wjoao, Lamartine e novamente ao alissonrgs.

Por favor, leiam as questões, tentem fazer, se não conseguirem leiam o editorial. Em último caso vejam o código.

Burguer Time?

Pré-requisitos: Nenhum

O problema é facilmente resolvido se pensarmos que se houver um restaurante e uma farmácia no mesmo local (se houver um caractere 'Z' na string) a distância mínima já vai ser 0. Se não houver, basta iterar por toda a string guardando a posição da última aparição de 'R' e 'D'. Quando uma nova posição aparecer, verificar se a distância entre os 2 atuais é menor do que a anteriormente calculada.

#include <bits/stdc++.h>

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define all(a) a.begin(),a.end()
#define pb push_back
#define LSOne(S) (S & (-S))

typedef unsigned long long llu;
typedef long long ll;
typedef long double ld;

const int INF = 0x3f3f3f3f;

using namespace std;

int main(){
  int l;
  while(scanf("%d%*c", &l) && l){
  	char c;
  	int res = INF, d = -1, r = -1;
  	REP(i, l){
  		scanf("%c", &c);
  		if(c == 'R'){
  			r = i;
  			if(d != -1) res = min(res, abs(r-d));
  		} else if(c == 'D'){
  			d = i;
  			if(r != -1) res = min(res, abs(r-d));
  		} else if(c == 'Z') res = 0;
  	}
  	if(d != -1 && r != -1) res = min(res, abs(r-d));
  	cout << res << endl;
  }
  return 0;
}

Complexidade : O(n)

*n sendo o valor de L na questão.

Autor : Filipe Herculano Rocha

Anagram

Pré-requisitos: next_permutation

Para resolver essa questão vou usar dois métodos da biblioteca padrão: sort() e next_permutation(). O sort vai fazer a primeira string e o next_permutation vai gerar a próxima permutação da string inicial, na ordem lexicográfica. O problema é que a questão quer em ordem alfabética, então “Ba” virá antes de “aB”, dando resposta errada. Meu truque foi fazer um vetor com valores relativos aos caracteres, de modo que a string AaBbCc… vire o vetor {0,1,2,3,4,5...}. Daí, uso sort e next_permutation nesse vetor. Na hora de imprimir, verifico se o valor é par. Se for, então é maiúsculo. Senão, minúsculo.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    
    vector<int> v;
    string s;
    int n,i,x;
    
    cin>>n;
    while(n--){
        v.clear();
        
        cin>>s;
        for(i=0; i<s.size(); i++){
            if(s[i]<'a') x = (s[i]-'A')*2;
            else x = (s[i]-'a')*2 + 1;
            v.push_back(x);
        }
        sort(v.begin(), v.end());
        
        do{
            for(i=0; i<s.size(); i++){
                if(v[i]%2==0) cout<<(char)(v[i]/2 + 'A');
                else cout<<(char)(v[i]/2 + 'a');
            } cout<<endl;
        } while( next_permutation(v.begin(), v.end()) );
    }
    
    return 0;
}

Complexidade : O(n!)

*n sendo o tamanho da string.

Autor : Lamartine Cabral

Euclid Problem

Laser Sculpture

Pré-requisitos: Nenhum

Com uma simples passada por todo o vetor com as alturas finais dos blocos, nós conseguimos o resultado. Dado uma altura de um bloco i (0 <= i < C) em um vetor v, se o bloco for o primeiro, deve-se somar ao contador abs(A-v[i]) . Caso i não seja o primeiro, deve-se verificar se ele é menor que o bloco anterior e se for soma-se ao contador abs(v[i]-v[i-1]) . O motivo é que raios são comuns em alturas superiores à direita, porém não são comuns quando a altura é menor.

#include <bits/stdc++.h>

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define all(a) a.begin(),a.end()
#define pb push_back
#define LSOne(S) (S & (-S))

typedef unsigned long long llu;
typedef long long ll;
typedef long double ld;

const int INF = 0x3f3f3f3f;

using namespace std;

int main(){
  int a, c;
  while(scanf("%d", &a) && a){
    scanf("%d", &c);
    int v[c], cnt = 0;
    REP(i, c) scanf("%d", &v[i]);
    REP(i, c){
	    if(i) {
		    if(v[i] < v[i-1]) cnt += abs(v[i]-v[i-1]);
	    } else cnt += abs(a-v[i]);
    }
    cout << cnt << endl;
  }
  return 0;
}

Complexidade : O(n)

*n sendo o valor de C na questão.

Autor : Filipe Herculano Rocha

Maximum Product

Pré-requisitos: Nenhum

Como o tamanho máximo do vetor é N = 18 (bem pequeno), uma solução possível era testar todos os conjuntos existentes. Com um loop para representar o tamanho do conjunto a ser testado (1 <= i <= N), bastava realizar mais dois loops com os valores do vetor, um de (0 <= j < N) e o outro com o tamanho do conjunto (j <= k < j + i), multiplicava os valores do conjunto e no final testava se o valor era maior.

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

int v[NMAX+1];

int main() {
   int n, _case = 1;
   
   while( ~scanf( "%d", &n ) && n ) {
      for( int i = 0; i < n; i++ )
         scanf( "%d", &v[i] );
      
      ll maxp = 0;
      for( int i = 1; i <= n; i++ ) {
         for( int j = 0; j < n; j++ ) {
            ll p = 1;
            for( int k = j; k < j + i && k < n; k++ )
               p *= v[k];
            maxp = max( maxp, p );
         }
      }
   
      printf( "Case #%d: The maximum product is %Ld.\n\n", _case++, maxp );
   }

   return 0;
}

Complexidade: O(N^3)

Autor: Alisson Soares

Where is the Marble?

Zeros and Ones

Pré-requisitos: Prefix Sum

Como a string tinha apenas 1s e 0s era possível aplicar a soma de prefixos, assim usando um vetor, bastava passar uma única vez por toda a string e ir somando o valor da posição da string com a posição anterior do vetor ( sum[ i ] = str[ i ] + sum[ i-1 ] ). Feito isso as consultas ficam O(1), pois para uma consulta de i até j com j > i, basta calcular ( sum[ j ]-sum[ i ] + s[ i ] ), se for igual a diferença dos índices ( j — i + 1 ) é porque todos os valores na string são 1s, e caso for 0 é porque todos os valores na string são 0s.

Esse problema também era possível com força bruta, a cada consulta bastava fazer um ‘for’ verificando se uma posição no vetor era diferente da anterior, caso fosse é porque a sequência não é de mesmos dígitos, caso contrário sim.

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

int sum[NMAX+1];

int ctoi( char c ) { return (int)( c - '0' ); }

int main() {
    string s;
    int q, i, j, _case = 1;
   
    while( cin >> s ) {
        sum[0] = ctoi( s[0] );
        for( int k = 1; k < (int)s.size(); k++ )   
            sum[k] = sum[k-1] + ctoi( s[k] );
   
        cin >> q;
        cout << "Case " << _case++ << ":" << endl;
        while( q-- ) {
            cin >> i >> j;
            if( i > j ) swap( i, j );
         
            int v = sum[j] - sum[i] + ctoi( s[i] );
            if( v == j-i+1 || v == 0 )
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
      }
   }

   return 0;
}

Complexidade: O(n+q)

*n sendo o tamanho da string e q sendo a quantidade de queries

Autor: Alisson Soares

Pontentiometers