31 de marzo de 2019

Llega Code Jam 2019, la competición de programación de Google

00:21  ,  No hay comentarios

Codejam 2019
Code Jam es una iniciativa organizada por Google que reta a los programadores de todo el mundo a poner a prueba sus habilidades resolviendo múltiples rondas de problemas de algoritmia. Se permite el uso de cualquier lenguaje de programación y entorno de desarrollo para dar solución a estos problemas.


En esta temporada, se presentan problemas algorítmicos desafiantes (algunos de ellos son interactivos) para la comunidad global de programadores.

Cada año, el equipo de ingeniería de Code Jam y un grupo exclusivo de colaboradores de Google dedican miles de horas combinadas en la creación, prueba y publicación de algunos de los problemas algorítmicos más difíciles del mundo.

Este año se ha incorporado la característica de "formular una pregunta", que ofrece a los participantes la oportunidad de interactuar con los ingenieros de Code Jam durante las rondas en línea. También se están introduciendo nuevos conceptos, como la capacidad de probar una solución en sus servidores, así como proporcionar certificados a los competidores.

La ronda de clasificación se lleva a cabo el 5 de abril (regístrate aquí).
De las decenas de miles de participantes en el concurso, solo los 25 primeros calificarán para asistir el viernes 9 de agosto a la gran final en las oficinas de Google en San Francisco, Mountain View (California).

El nuevo Campeón del Mundo se llevará a casa $15,000, mientras que los 1.000 mejores competidores ganarán una camiseta de edición limitada de 2019.




Desafíos de la edición 2018 y ejemplos de resultados de uno de sus participantes

:

1- Rounding Error (5pts, 9pts, 11pts)


Enunciado del problema: Rounding Error, Problem

Respuesta » C++ (G++) code

#include 
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef vector vi;
typedef long long ll;
typedef pair pii;

int solve(){
 int n, l;
 cin >> n >> l;

 int ans = 0;

 priority_queue pq;

 int left = n;
 rep(_,0,l){
  int c;
  cin >> c;
  left -= c;
  int res = 200 * c - n;
  while(res >= 0){
   res -= 2*n;
   ans++;
  }
  pq.push(res);
 }
 rep(i,0,left){
  int res = pq.top();
  pq.pop();
  if(res < -n){
   pq.push(-n);
   --i;
   continue;
  }
  res += 200;
  while(res >= 0){
   res -= 2*n;
   ++ans;
  }
  pq.push(res);
 }
 return ans;
}

int main(){
 int t;
 cin >> t;
 rep(i,1,t+1){
  cout << "Case #" << i << ": " << solve() << endl;
 }
}

2- Mysterious Road Signs (10pts, 20pts)


Enunciado del problema: Mysterious Road Signs, Problem

Respuesta » C++ (G++) code
#include 
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef vector vi;
typedef long long ll;
typedef pair pii;

void solve(){
 int s;
 cin >> s;
 vi m(s), n(s);
 rep(i,0,s){
  int d, a, b;
  cin >> d >> a >> b;
  m[i] = d+a;
  n[i] = d-b;
 }
 
 map mm, nn;
 map mn;

 rep(i,0,s) mm[m[i]] = nn[n[i]] = mn[pii(m[i],n[i])] = 0;

 int ix = 0;
 trav(pa, mm) pa.second = ix++;
 ix = 0;
 trav(pa, nn) pa.second = ix++;
 ix = 0;
 trav(pa, mn) pa.second = ix++;
 
 vi mr(s), nr(s), mnr(s);
 rep(i,0,s){
  mr[i] = mm[m[i]];
  nr[i] = nn[n[i]];
  mnr[i] = mn[pii(m[i],n[i])];
 }

 vector ml(sz(mm)), nl(sz(nn)), mnl(sz(mn));
 rep(i,0,s){
  ml[mr[i]].push_back(i);
  nl[nr[i]].push_back(i);
  mnl[mnr[i]].push_back(i);
 }

 auto cnt = [&](int fr, int to, vi &v){
  return lower_bound(all(v), to) - lower_bound(all(v), fr);
 };

 auto good = [&](int fr, int to, int m1, int n1){
  int z = -1;
  if(mn.count(pii(m1, n1))) z = mn[pii(m1,n1)];
  int x = mm[m1], y = nn[n1];
  
  int res = cnt(fr,to, ml[x]) + cnt(fr,to, nl[y]);
  if(z >= 0) res -= cnt(fr,to, mnl[z]);

  return to-fr == res;
 };

 auto len = [&](int fr, int m1, int n1){
  int lo = 1, hi = s-fr+1;
  while(lo+1 < hi){
   int mi = (lo+hi)/2;
   if(good(fr, fr+mi, m1, n1)) lo = mi;
   else hi = mi;
  }
  return lo;
 };
 int rek = 0, num = 0;

 rep(i,0,s){
  int res = len(i, m[i], n[i]);
  if(i+res < s) {
   int j = i+res;
   res = max(res, max( len(i, m[i], n[j]),
       len(i, m[j], n[i]) ) );
  }
  if(res > rek){
   rek = res;
   num = 0;
  }
  if(res >= rek) ++num;
 }
 cout << rek << ' ' << num << endl;
}

int main(){
 int t;
 cin >> t;
 rep(i,1,t+1){
  cout << "Case #" << i << ": ";
  solve();
 }
}

3- Transmutation (15pts, 18pts, 12pts)


Enunciado del problema: Transmutation, Problem

Respuesta » C++ (G++) code
#include 
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef vector vi;
typedef long long ll;
typedef pair pii;

ll solve(){
 int m;
 cin >> m;

 vi r1(m), r2(m);
 rep(i,0,m) cin >> r1[i] >> r2[i];
 trav(x, r1) --x;
 trav(x, r2) --x;

 vector g(m);
 trav(x, g) cin >> x;

 ll tot = 0;
 trav(x, g) tot += x;

 auto works = [&](ll y){
  vector gg = g;

  gg[0] -= y;

  rep(_,0,m-1){
   rep(i,0,m) if(gg[i]<0){
    if(gg[i] < -tot) return false;
    ll pr = gg[i];
    gg[i] = 0;
    gg[r1[i]] += pr;
    gg[r2[i]] += pr;
   }
  }
  trav(x, gg) if(x < 0) return false;
  return true;
 };

 ll lo = g[0], hi = tot+1;
 while(lo+1 < hi){
  ll mi = (lo+hi)/2;
  if(works(mi)) lo = mi;
  else hi = mi;
 }
 return lo;
}

int main(){
 int t;
 cin >> t;
 rep(i,1,t+1){
  cout << "Case #" << i << ": " << solve() << endl;
 }
}



Tal vez te interese conocer algunos de estos temas:





0 comments:

Publicar un comentario