Today at 14:00 UTC there will be the third round of Google Code Jam. Top-25 contestants will be invited to the final round in the Seattle.

Good luck to everybody!

As an experiment the Educational Codeforces Round 33 will be rated for Div. 2.
×

# | User | Rating |
---|---|---|

1 | tourist | 3496 |

2 | moejy0viiiiiv | 3288 |

3 | W4yneb0t | 3218 |

4 | TakanashiRikka | 3178 |

5 | Petr | 3173 |

6 | dotorya | 3117 |

7 | izrak | 3109 |

7 | Um_nik | 3109 |

9 | anta | 3106 |

10 | ershov.stanislav | 3105 |

# | User | Contrib. |
---|---|---|

1 | rng_58 | 174 |

2 | csacademy | 170 |

3 | Swistakk | 160 |

4 | tourist | 157 |

4 | Petr | 157 |

6 | Errichto | 154 |

7 | Zlobober | 147 |

8 | matthew99 | 142 |

9 | Endagorion | 141 |

10 | BledDest | 135 |

Today at 14:00 UTC there will be the third round of Google Code Jam. Top-25 contestants will be invited to the final round in the Seattle.

Good luck to everybody!

Discussion of 2015 Google Code Jam Round 3 (GCJ 15 Round 3)

↑

↓

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/23/2017 03:10:28 (c6).

Desktop version, switch to mobile version.

User lists

Name |
---|

Auto comment: topic has been translated by Zlobober(original revision, translated revision, compare)is tourist or Petr Participate?

No . Tourist was the winner of Code Jam 2014, so he got a direct entry to this year's final .

tourist is Participating!

TankEngineer missed by just 15 seconds

At least two teenagers (me and jcvb) are in top 25. And champion(tourist) in the last year. I'm not sure whether ecnerwal and izrak are adults. So I think people ranked 26, 27 and 28 will advance.

He will advance because tourist is in top-25.

What solution was supposed in C-small? N <= 25, almost all maxtests in the small test =( Too tight for an

O(2^{N}*N^{2}) with optimizations that came to my head.I've splitted cases in two runs.

If that was what intended then it's the first time I see such tight constraints on GCJ. I'm sure there were no solutions with wrong asymptotic authors were trying to cut off, but then why not use n <= 20?..

Nevertheless, respect to everybody who suceeded to the onsite finals.

I'm sure that on fast computer my solution could be optimised twice.

Well, I think it can be solved in O(2^n * n) because we always should go to the fastest person on the left or the fastest person on the right

It can be

O(2^{N}·N) (on each step I choose where to go — to the right or to the left). I also return from the function if current answer is worse than current best answer, and it helps a lot.How to solve B?

First of all let's break all temperatures into

kgroups.t_{i}will belong to group`i mod k`

.Then do binary search on the answer

D. Let's say the interval which will fit all temperatures will be [L;L+D]. For every temperaturet_{i}withi<kyou can calculate the range relative toLwheret_{i}might be such that all temperatures from its group will fit into [L;L+D] interval. Let's denote this interval fori-th group as [L+mn_{i};L+mx_{i}]. So you haveksuch intervals, you sum them up and get the final range relative toL, you just need to check if existsLsuch that this interval will includesums_{0}.Better than binary search:

Note that we can find

s_{i + K}-s_{i}=sum_{i + 1}-sum_{i}for any validi; by repeating it, we can finds_{i + nK}-s_{i}. Compute , so that group spans the range [s_{i}+min_{i},s_{i}+max_{i}]. Clearly this also means the minimum difference ismax_{i}-min_{i}.But in fact, this is almost enough; let , then the answer is either

DorD+ 1. To find this, compute and . IfS≤Tthen the answer isD, otherwise the answer isD+ 1.The idea is like this. This might not make sense; I'm not sure how to word it.

We know that each group has a difference of minimum and maximum that we cannot change. However, we can try to arrange the groups so that their minima line up. For example, given

K= 3,sum= (3, 4, 2, 5, 2), we obtain group to haves_{1},s_{4}=s_{1}+ (4 - 3),s_{7}=s_{4}+ (2 - 5), group to haves_{2},s_{5}=s_{2}+ (2 - 4), and group to haves_{3},s_{6}=s_{3}+ (5 - 2). In other words, group spans [s_{1}- 2,s_{1}+ 1], group spans [s_{2}- 2,s_{2}], and group spans [s_{3},s_{3}+ 3].Now, we begin by lining up everything. Let

s_{1}=x_{1}+ 2,s_{2}=x_{2}+ 2,s_{3}=x_{3}, so that our ranges become [x_{1},x_{1}+ 3], [x_{2},x_{2}+ 2], [x_{3},x_{3}+ 3]; this also meansx_{1}+x_{2}+x_{3}= - 1.Now, if we can use fractional temperatures, we can just set and we're done. But this is not the case, so unfortunately we have to fiddle a little. Let's begin with

x_{1}=x_{2}=x_{3}= - 1, and we will increase two of thex_{i}'s (may be the same) so that their sum becomes - 1. Our intervals are [ - 1, 2], [ - 1, 1], [ - 1, 2], and we want to slide two of them to the right, trying to keep the difference between minimum and maximum as small as possible.Unfortunately, this is impossible without making some of the upper bounds to exceed 2 (there is only one move available, the middle one moved to the right once to [ - 1, 2], [0, 2], [ - 1, 2]), so we must necessarily break the upper bound 2. But now this is always possible; after moving the maximum extent possible, we just move as many intervals as necessary (in this case one more, to [0, 3], [0, 2], [ - 1, 2]). This will never reuse the same interval if we take the starting value of

x_{1},x_{2},x_{3}to be ; that is, the largest equal value forx_{1},x_{2},x_{3}so that their sum doesn't exceed the required sum. The difference to the required sum will be strictly smaller thanK, hence why we won't increase the upper bounds. We also won't be able to get rid of the original value - 1, since if we can that means we will increase allKintervals by at least once each, but we don't have that many moves.After setting

x_{1}= 0,x_{2}= 0,x_{3}= - 1, this corresponds to the solutionss_{1}= 2,s_{2}= 2,s_{3}= - 1, and thus followss_{4}= 3,s_{5}= 0,s_{6}= 2,s_{7}= 0, making the sequences= (2, 2, - 1, 3, 0, 2, 0) which can be verified.Had

sum_{5}= 3 instead, we haves_{7}=s_{4}- 2 (and thuss_{7}=s_{1}- 1), making the first interval to be [s_{1}- 1,s_{1}+ 1] instead, so that we obtains_{1}=x_{1}+ 1 andx_{1}+x_{2}+x_{3}= 0. This time we can just setx_{1}=x_{2}=x_{3}= 0, and we're done already, givings= (1, 2, 0, 2, 0, 3, 0).Don't mean to invade privacy of any sort here but, who is user "linguo" ranked 5? Does he compete here on CF or on TC?

It's particularly interesting to me as all his solutions are in python which is very rare among the top participants. :)

https://en.wikipedia.org/wiki/Luke_Pebody

WOAH

And he even won Round3 in 2011 by Python: https://code.google.com/codejam/contest/1158485/scoreboard

Couldn't get his solution of D-large.

Added to the gym — 2015 Google Code Jam Round 3 (GCJ 15 Round 3)

rng_58 tomasz.kociumaka tourist Xhark linguo iwiwi tomek simonlindholm kevinsogo vepifanov bmerry fagu dzhulgakov pashka AngryBacon betaveros izrak yeputons qwerty787788 Merkurev wrong wuzhengkai 0O0o00OO0Oo0o0Oo TankEngineer semiexp Romka

Why did you write handles?