Contest da semana #1

#	User	Rating
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	157
6	maroonrk	155
7	-is-this-fft-	152
8	Petr	146
8	orz	146
10	BledDest	145

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.

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

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

Rev.	By	When	Δ	Comment
en17	Sazzon	2016-11-26 18:19:20	53
en16	Sazzon	2016-11-26 17:51:29	0	(published)
en15	Sazzon	2016-11-26 16:55:52	13	(saved to drafts)
en14	Sazzon	2016-11-26 16:54:49	222
en13	Sazzon	2016-11-26 04:38:38	0	(published)
en12	Sazzon	2016-11-26 04:37:20	66
en11	Sazzon	2016-11-26 04:35:43	183
en10	Sazzon	2016-11-26 04:29:48	5037
en9	Sazzon	2016-11-26 04:08:17	1026	Tiny change: 'xidade :\n\nAuto' -
en8	Sazzon	2016-11-26 03:55:53	1546	Tiny change: 'ade : O(n!)\n\n*_n' -
en7	Sazzon	2016-11-26 03:26:24	161
en6	Sazzon	2016-11-26 03:10:25	1802	Tiny change: ' sum[ j ] - sum[ i ] ' -
en5	Sazzon	2016-11-26 02:56:47	1398	Tiny change: 'ade :** O(S.size())\n\n[Anag' -
en4	Sazzon	2016-11-26 02:26:38	117
en3	Sazzon	2016-11-26 02:19:53	2	Tiny change: ' todos! \nEsse é o' -> ' todos! \n\nEsse é o'
en2	Sazzon	2016-11-26 02:19:27	18
en1	Sazzon	2016-11-26 02:18:35	3701	Initial revision (saved to drafts)

History