Back to : cp-rounds

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 :)

Contents

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