Contest da semana #1

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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.

Sorry for the lack of translation, we are from Brazil and the group is closed. Don't downvote this post just because you don't understand the language. We are using the platform to communicate internally. Please be nice ! :-)

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.

Code

#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;
  	}
  	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.

Code

#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

Pré-requisito: Algoritmo de Euclides extendido

Esse problema é a aplicação prática do algoritmo de Euclides extendido.

Code

#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;

ll x, y, d;

void euclid(ll a, ll b){
  if(b == 0){
    x = 1;
    y = 0;
    d = a;
    return; 
  }
  euclid(b, a%b);
  ll x1 = y;
  ll y1 = x - (a / b) * y;
  x = x1;
  y = y1;
}

int main(){
  ll a, b;
  while(~scanf("%lld %lld", &a, &b)){
    euclid(a, b);
    printf("%lld %lld %lld\n", x, y, d);
  }
  return 0;
}

Complexidade : O(log n)

Autor: Filipe Herculano Rocha

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.

Code

#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.

Code

#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?

Pré-requisitos: Ordenação, busca binária, lower_bound

Para achar a solução da questão, tinha que receber os N elementos, e ordená-los. Após isso receber Q consultas, cada uma delas, tinha que retornar o índice do número e se existir mais de um número igual, pegar o menor índice, no vetor ordenado.

Para se ordenar um vetor, pode-se usar a função sort.

Ex: int vetor[n]; sort(vetor, vetor+n);

Para realizar a busca binária em um vetor ordenado, você pode usar o lower_bound do cpp:

Ex: int *p = lower_bound(vetor, vetor+n, valor_buscado);

Obs: Detalhe que o lower_bound retorna um ponteiro para a posição do vetor, onde está o elemento encontrato, e caso ele não exista, ele retorna para algum número menor que o número buscado, e o mais próximo dele. Logo ao fazer o lower_bound, é necessário verificar se o valor de *p é igual ao valor da busca. Se for igual é porque foi achado e é necessário achar o indice e para isso é necessário apenas fazer uma operação de ponteiros, diminuindo p por vetor( A posição atual do ponteiro no meio do vetor, menos a posição do ponteiro inicial do vetor ) e o resultado disso é o indice, baseado em 0. Caso não fosse igual, o elemento não teria sido achado.

Complexidade : O(n*log n + q*log n)

Código com busca binária

#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 bs(vector<int> v, int num){
	int head = 0, tail = v.size()-1, body;
	while(head <= tail){
		body = (head+tail)/2;
		if(v[body] == num){
			if(body == 0 || v[body-1] != v[body]) return body;
			else tail = body-1;
		} else if(v[body] > num) tail = body-1;
		else head = body+1;
	}
	return -1;
}

int main(){
	int n, q, caso = 1;
	while(scanf("%d %d", &n, &q) && (n || q)){
		int index;
		vector<int> v(n);
		REP(i, n) scanf("%d", &v[i]);
		sort(all(v));
		printf("CASE# %d:\n", caso++);
		REP(i, q){
			int temp;
			scanf("%d", &temp);
			index = bs(v, temp);
			if(index == -1) printf("%d not found\n", temp);
			else printf("%d found at %d\n", temp, index+1);
		}
	}
  return 0;
}

Autor : Filipe Herculano Rocha

Código com lower_bound

#include<bits/stdc++.h>


using namespace std;


int numeros[10100];
int n, m, a, t =1;


int main(){
    while( cin >> n >> m && n ){
        for(int i = 0; i < n; i++){
            cin >> a;
            numeros[i] = a;
        }
    
    
        sort(numeros, numeros + n);
        cout << "CASE# "<< t++ << ":" << endl;
        for(int i = 0; i < m; i++){
            cin >> a;
            int * it = lower_bound(numeros, numeros+n, a);
            
            if( it == numeros+n ){ // O numero pesquisado era maior do que todos existentes
                cout << a << " not found" << endl;
            }else{
                int peso = *it;
                if( peso == a ){ // Verifica se o numero encontrato é igual ao pesquisado
                    cout << peso << " found at " << (int)(it-numeros)+1 << endl;
                }else{
                    cout << a << " not found" << endl;
                }
            }
        }
    }




    return 0;
}

Autor: João Vitor

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.

Code

#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

Pré-requisitos: Bit — Fenwick Tree

Utilização básica da bit. Usa-se o operador de Update em um ponto. e de Query para saber o resultado da soma entre intervalos.

Code

#include<bits/stdc++.h>


#define MAXN 200005 


int n, a, b, t= 1;
int Bit[MAXN];
char op[10];
 
void Update(int p, int v){
    while(p < MAXN){
        Bit[p] += v;
        p += p & -p;
    }   
}
 
int Query(int p){
    int ans = 0;
    while(p > 0){
        ans += Bit[p];
        p -= p & -p;
    }
    return ans;
}




int main(){
    while( scanf(" %d", &n) && n){
        memset(Bit, 0, sizeof Bit);
        for(int i = 1; i <= n; i++){
            scanf("%d", &a);
            Update(i, a);
        }
        if( t != 1 ) printf("\n");
        printf("Case %d:\n", t++);
        while( scanf(" %s", op) && op[0] != 'E' ){
            if( op[0] == 'S' ){
                scanf(" %d%d", &a, &b);
                int atual = Query(a) - Query(a-1);
                Update(a, b - atual);
            }else if( op[0] == 'M' ){
                scanf(" %d%d", &a, &b);
                printf("%d\n", Query(b)-Query(a-1));
            }
        }
    }
    
    return 0;
}

Complexidade: O(n*logn + q*logn)

*q sendo a quantidade de queries na BIT.

Autor: João vitor