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

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)

Respuesta » C++ (G++) code

#include stdc++.h>
<="">>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  : 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;
 }
}

Enunciado del problema: Rounding Error, Problem

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

Respuesta » C++ (G++) code

#include stdc++.h>
<="">>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  : 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();
 }
}

Enunciado del problema: Mysterious Road Signs, Problem

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

Respuesta » C++ (G++) code

#include stdc++.h>
<="">>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  : 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;
 }
}

Enunciado del problema: Transmutation, Problem
Jose Maria Acuña Morgado - Desarrollador Web