Google Hash Code 2022 : Global #106 (1%) about preparation
To improve my English writing, I will try writing this post in English! (English is not my first language, so please bear with me about cumbersome writingâŠ)
Disclaimer : A large portion of this post is based on my personal opinion :)
We (Team Little Piplup @ SNU) managed to reach world #106 (out of 9000+ teams), Korea #4 at Google Hashcode 2022 Preliminaries.
As I did last year (Link), this post consists of two parts : âOur preparationâ and âDuring the contestâ. This post is the former, which we share what we have prepared and our background. About what we have done during the contest is here
Our team âLittle Piplupâ
There is not much to discuss since no significant changes were made to our team. Most of what I wrote last year (in Korean) remains the same.
To repeat some details (note - we are primarily all CS students from Seoul Natâl Univ. My teammates have software related job as an alternative military service.):
-
Gratus907
(Codeforces :Gratus907
, Atcoder :Gratus
)- This is me and for obvious reasons it is near impossible to discuss my strengths and weaknesses objectivelyâŠ
- I am generally better at mathematical problems (partly due to my background, math double major?) and since I plan to go to grad school studying algorithms, I have strongest theoretical background among us.
- In some contests, I tend to rush some implementation and face horrifying consequences. (SCPCâŠ)
-
Coffeetea
(Codeforces :Coffeetea
)-
Coffeetea
is currently working as a game developer. - He is great at finding âinstinctive insightsâ than rigorous proofs.
- He no longer uses C++ in his daily job, so his implementation skills in CP is not as good as before.
-
-
DHDroid
(Codeforces :Diordhd
(he uses his original handle backwards in CF, for some reason))-
DHDroid
is currently working as a AI engineer. - He is especially good at these kind of heuristic contests and constructive problems.
- His implementation speed is slightly below than what his rating expects.
-
-
Dlwocks31
(Codeforces :Dlwocks31
, Atcoder :Dlwocks31
)-
Dlwocks31
is currently working as a backend developer. - He is more âbalancedâ type with decent programming and solving skills.
- Overall, he had best implementation skills among us, but he also no longer uses C++ in his daily job.
- Still, he tends to write cleaner, understandable code than rest of us.
-
We have about 1900-2100 rating in codeforces. Although this rating is from long time (about an year) ago, I donât think that this would have changed much if we participated several contests right before. Comparing ourselves with last year, we havenât had much time to practice competitive programming. But still everyone has done some form of programming in our daily life.
About HashCode
As we understand, Google Hashcode is somewhat unique in both format and content.
(Competitive) Programming contests (by competitive I mean not including those which we make some kind of application or product) usually have two forms.
- Codeforces, Atcoder, ICPC, IOI all can be considered as âsolving algorithmic problems in short period of time, typically several hoursâ. Here, contestants are asked to write an efficient program which fits in time/memory limit
- Kaggle, TC Marathon matches and some so-called âdata science hackathonsâ can be thought as âsolving somewhat-realistic problem with somewhat-realistic data in longer period of time, typically days or weeksâ
While the former requires knowledge of algorithms, mathematics and fast coding skills, the latter tends to be more focused in data science, and machine learning.
Hashcode is somehow in the middle of these two types of contests, in the sense that :
- Test data is given and we can (actually, we must) exploit specific structure or property of data.
- Which means that our solution do not have to be mathematically provable / generalizable.
- Also, program is not tested against hidden test data, and program does not have to fit in specific time/memory limit
- Problems are (sometimes) algorithmic in nature
- Especially, specific structure such as bipartite graphs, 3-SAT reduction, etc⊠might arise in test data
- Considering short contest time (3.75 hours), problem is very implementation-heavy.
There have been something similar tried in other contests - for example IOI 2013 ARTCLASS. These output-only heuristic problems in olympiads can be (and is) controversial, but as a team competition I personally enjoy these. Solving these problems gives some âincremental enjoymentâ.
Practice Round with AHC 006
For this year, we were unable to allocate lot of time for practice sessions. We managed to arrange a session where we gathered to solve Atcoder Heuristic Contest 006 for 4 hours. Link to Contest we managed to get 2.03M points. While the contest was originally for individual participation and so our results cannot be compared directly to the contestants, we had a lot of fun and quite satisfied with our performance. However, AHC rounds (at least 006) are fundamentally different from Hashcode in three senses
- Inputs are âguaranteed to be randomâ and this makes a big difference.
- Problem statement is not as complicated, and implementation is lot easier than Hashcode.
Little it may look, these two differences make AHC lot more âCP-likeâ than Hashcode is.
In case anyone is interested, the approach we used for AHC 006 is âadaptive greedy pathfinding with randomized starting pointsâ. When âcurrent pathâ consisting of $x$ restaurants and destinations are fixed, we can find a (restaurant, destination) pair and their position in the sequence which minimizes cost of resulting path, greedily. Starting from {INITIAL_POINT, INITIAL_POINT}
, we keep adding locations to our path. This strategy is innately very unstable to the first choice, hence we try several random starting points and take the best.
This is very much a demonstrative example of what we usually expect from a heuristic contest - âdecent greedy-ish strategyâ with ârandom tuning/augmentationâ.
About Hashcode 2022 Prelim
About our strategy and in-contest timeline