Yearly Archives: 2022

Mentorship and Teamwork

Introduction

Work is so much more fun when we are part of a team! By combining our different skills, we can be more creative, efficient and productive. And more importantly, when working together we share… not only pizzas, but also knowledge. We can learn from each other, improve our own skills and gain experience.

Teamwork is one of the main ingredients of Hash Code, especially in this challenge!

So, are you up for the challenge?

Summary

You are given a list of contributors, who have already mastered various skills, and a list of projects with different skill requirements. Contributors can improve their skills by completing projects and can mentor each other to work is roles in which they couldn’t succeed on their own. Your task is to assign contributors to project roles that fit their qualifications and maximize the score for completed projects.

Problem description

Contributors

There are N contributors. Each contributor has a name and one or more skills at a specific level (0,1,2,…). Not possessing a skill is equivalent to possessing a skill at level 0.

For example, three contributors could have the following skills:

• Anna: Python level 3
• Bob: C++ level 3
• Maria: HTML level 4, CSS level 6

Projects

There are M

projects. Each project is described by:

• its name
• the duration of the project in days (how long it takes to complete a project once it is started)
• the score awarded for completing the project
• the “best before” time in days – if the project last day of work is strictly before the indicated day, it earns the full score. If it’s late (that is, the project is still worked on during or after its “best before day”), it gets one point less for each day it is late, but no less than zero points. See also the example in the “Assignments” section below.
• a list of roles for contributors working on the project

Each project has one or more roles that need to be filled by contributors. Each role requires one skill at a specific level, and can be filled by a single contributor. Each contributor can fill at most one role on a single project.

For example, a project called “WebServer” could have the following roles:

• Role 0 requiring Python level 3
• Role 1 requiring HTML level 1
• Role 2 requiring CSS level 5

Filling roles and mentorship

A contributor can be assigned to a project for a specific role (at most one role in a single project), if they either:

• have the skill at the required level or higher; or
• have the skill at exactly one level below the required level, only if another contributor on the same project (assigned to another role), has this skill at the required level or higher. In this case, the contributor will be mentored by their colleague 🙂

One contributor can mentor multiple people at once, including for the same skill. A contributor can mentor and be mentored by other contributors at the same time.

Not possessing a skill is equivalent to possessing a skill at level 0. So a contributor can work on a project and be assigned to a role with requirement C++ level 1 if they don’t know any C++, provided that somebody else on the team knows C++ at level 1 or higher.

For example:

For the project WebServer above we could make the following assignments:

Role 0 (requires Python level 3) is assigned to Anna (Python level 3).

• ☑️ Anna has the same level in Python as required.

Role 1 (requires HTML level 1) is assigned to Bob (C++ level 3).

• ⚠ Bob has level 0 in HTML. Since his level is only one below required, he can be assigned, but must be mentored by another contributor who knows HTML at level 1 or above.

Role 2 (requires CSS level 5) is assigned to Maria (HTML level 4, CSS level 6)

• ☑️ Maria has a higher level than the one required for CSS.
• ☑️ Maria can mentor Bob on HTML since she has HTML level 4.

Assignments

Each contributor can start working on day 0 and can be working on at most one project at the same time. Once the work on a project starts, its contributors will be working on it the number of days equal to its duration and then become available to work on other projects.

For example, if the project WebServer has duration of 7 days and starts on day 0, the contributors assigned to it will be working on it during: day 0, day 1, day 2, day 3, day 4, day 5 and day 6. On day 7 the project is already completed. Contributors assigned to it can work on another project on day 7.

Learning

Completing a project is a learning opportunity, especially for the contributors working on the edge of their existing abilities! When each project is completed:

• contributors working in roles where the required skill level was equal or higher than their current level improve their skill level by one level
• other contributors keep their skill level

Note that mentoring someone doesn’t increase the level of the skill for the mentor.

For example:

In the assignments above:

• Anna improves Python skill to level 4;
• Bob improves HTML skill to level 1;
• Maria improves neither the CSS skill (because Maria’s CSS is already at a level higher than required) nor the HTML skill (because her role required CSS, not HTML).

Input data sets

File format

Each input data set is provided in a plain text file. The file contains only ASCII characters with lines ending with a single ‘\n’ character (also called “UNIX-style” line endings). When multiple strings and numbers are given in one line, they are separated by a single space between each two elements.

The first line of the data set contains:

• an integer C (1 ≤ C≤ 10^5) – the number of contributors,
• an integer P (1 ≤ P ≤ 10^5) – the number of projects.

This is followed by C sections describing individual contributors. Each contributor is described by the following lines:

• the first line contains:
  • the contributor’s name (ASCII string of at most 20 characters, all of which are lowercase or uppercase English alphabet letters a-z and A-Z, or numbers 0-9),
  • an integer N (1≤ N ≤ 100) – the number of skills of the contributor.
• the next N lines describe individual skills of the contributor. Each such line contains:
  • the name of the skill (ASCII string of at most 20 characters, all of which are lowercase or uppercase English alphabet letters a-z and A-Z, numbers 0-9, dashes ‘-‘ or pluses ‘+’),
  • an integer Li (1≤ Li ≤ 10) – skill level.

This is followed by P sections describing individual projects. Each project is described by the following lines:

• the first line contains:
  • the name of the project (ASCII string of at most 20 characters, all of which are lowercase or uppercase English alphabet letters a-z and A-Z or numbers 0-9),
  • an integer Di (1 ≤Di ≤ 10^5) – the number of days it takes to complete the project,
  • an integer Si (1 ≤ Si ≤ 10^5) – the score awarded for project’s completion,
  • an integer Bi (1 ≤ Bi ≤ 10^5) – the “best before” day for the project,
  • an integer Ri (1 ≤ Ri ≤ 100) – the number of roles in the project.
• the next Ri lines describe the skills in the project:
  • a string Xk – the name of the skill (ASCII string of at most 20 characters, all of which are lowercase or uppercase English alphabet letters a-z and A-Z, numbers 0-9, dashes ‘-‘ or pluses ‘+’),
  • an integer Lk (1≤Lk≤100) – the required skill level.

Example

Submissions

The submission file should be a plaintext file containing only ASCII characters.

File format

Your submission describes which projects each contributor is going to work on and in which role.

The first line should contain the integer E (0≤E≤P)

– the number of executed projects.

This should be followed by E sections each describing one completed project. Each project should be described by two lines:

• A single line containing the name of the project (as it appears in the input file). Each project can be mentioned at most once in the submission file.
• A single line containing the names of the contributors assigned to each of the project roles, separated by single spaces and listed in the same order as the roles appear in the input file.

Example

Scoring

Each contributor can only work on one project at a time. If one contributor is assigned to multiple projects, the contributor will work on them in the same order as they appear in the submission file. Each project starts immediately on the first day on which all the assigned contributors are available.

If some project assignment is invalid because the assigned contributor does not have the required skill level for the project after finishing all previously assigned projects, the submission is considered invalid and will not be scored.

Each project that is completed successfully receives its assigned score, as defined in the input file, minus penalty points for any delay. If a project is completed after its “best before” time, it gets one point less for each day it is late (but no less than zero points). Note that even if a project scores zero points, the assigned contributors will work on it (and may improve their skills thanks to it).

The total score is the sum of scores for all correctly completed projects.

The example submission results in this timeline:

Day 0 to day 6: Bob and Anna are working on project WebServer (they both have the skills required).

• As of project completion, Anna levels up in C++: level 2 → 3;
• Bob doesn’t level up because his HTML skill (level 5) is of a higher level than required for the project (level 3).

Project WebServer’s last day of work is day 6, so it completes strictly before its “best before” day 7 and receives the full score: 10 points.

Day 7 to 11: Anna is working on the project Logging (she has sufficient C++ skill after completing project WebServer).

• As of project completion, Anna levels up in C++: level 3 → 4;

Project Logging’s last day of work is 11 (so it’s completed strictly before day 12), while its “best before” day was 5. It is late by (12−5=) 7 days and receives a score of: (10−7=) 3 points.

Day 7 to 16: Maria and Bob are working on project WebChat

• As of project completion, Maria levels up in Python: level 3 → 4;
• Bob doesn’t level up in HTML because his skills are of a higher level than required for the project (HTML level 5, required 3)

Project WebChat’s last day of work is day 16, while the “best before” day is 20, so it receives the full score: 20 points.

In the end, projects Webserver (10 points), Logging (3 points) and WebChat (20 points) are completed, resulting in a total score of 33 points.

Note that there are multiple data sets representing separate instances of the problem. The final score for your team will be the sum of your best scores for the individual data sets.

—

Past editions

— From https://codingcompetitions.withgoogle.com/hashcode/archive

Hash Code started in 2014 with just 200 participants from France. In 2020, more than 100,000 participants from across Europe, the Middle East, and Africa took part in the competition. You can take a look at the problems and winning teams from past editions of Hash Code below.

Past problem statements

Software engineering at scale

Hash Code 2021, Final Round
[download id=”10690″]
Google stores the vast majority of its code in one monolithic codebase, holding billions of lines of code. As of 2016, more than 25,000 software engineers were contributing to it, improving existing services and adding cool new features to meet the demands of their users.

Traffic Signaling

Hash Code 2021, Online Qualification Round
[download id=”6058″]
Given the description of a city plan and planned paths for all cars in that city, optimize the schedule of traffic lights to minimize the total amount of time spent in traffic and help as many cars as possible reach their destination before a given deadline.

Assembling smartphones

Hash Code 2020, Final Round
[download id=”5932″]
In this problem statement, we will explore the idea of operating an automated assembly line for smartphones.
Building a smartphone is a complex process that involves assembling numerous components, including the screen, multiple cameras, microphones, speakers, a processing unit, and a storage unit.
To automate the building of a smartphone, we will be using robotic arms that can move around the assembly workspace, performing all necessary tasks.

Book scanning

Hash Code 2020, Online Qualification Round
[download id=”5929″]
Books allow us to discover fantasy worlds and better understand the world we live in. They enable us to learn about everything from photography to compilers… and of course, a good book is a great way to relax!
Google Books is a project that embraces the value books bring to our daily lives. It aspires to bring the world’s books online and make them accessible to everyone. In the last 15 years, Google Books has collected digital copies of 40 million books in more than 400 languages, partly by scanning books from libraries and publishers all around the world.
In this competition problem, we will explore the challenges of setting up a scanning process for millions of books stored in libraries around the world and having them scanned at a scanning facility.

Compiling Google

Hash Code 2019, Final Round
[download id=”5927″]
Google has a large codebase, containing billions of lines of code across millions of source files. From these source files, many more compiled files are produced, and some compiled files are then used to produce further compiled files, and so on.
Given then huge number of files, compiling them on a single server would take a long time. To speed it up, Google distributes the compilation steps across multiple servers.
In this problem, we will explore how to effectively use multiple compilation servers to optimize compilation time.

Photo slideshow

Hash Code 2019, Online Qualification Round
[download id=”5925″]
As the saying goes, “a picture is worth a thousand words.” We agree – photos are an important part of contemporary digital and cultural life. Approximately 2.5 billion people around the world carry a camera – in the form of a smart phone – in their pocket every day. We tend to make good use of it, too, taking more photos than ever (back in 2017, Google Photos announced it was backing up more than 1.2 billion photos and videos per day).
The rise of digital photography creates an interesting challenge: what should we do with all of these photos? In this competition problem, we will explore the idea of composing a slideshow out of a photo collection.

City Plan

Hash Code 2018, Final Round
[download id=”5921″]
The population of the world is growing and becoming increasingly concentrated in cities. According to the World Bank, global urbanization (the percentage of the world’s population that lives in cities) crossed 50% in 2008 and reached 54% in 2016.
The growth of urban areas creates interesting architectural challenges. How can city planners make efficient use of urban space? How should residential needs be balanced with access to public utilities, such as schools and parks?

Self-driving rides

Hash Code 2018, Online Qualification Round
[download id=”5917″]
Millions of people commute by car every day; for example, to school or to their workplace.
Self-driving vehicles are an exciting development for transportation. They aim to make traveling by car safer and more available while also saving commuters time.
In this competition problem, we’ll be looking at how a fleet of self-driving vehicles can efficiently get commuters to their destinations in a simulated city.

Router placement

Hash Code 2017, Final Round
[download id=”4175″]
Who doesn’t love wireless Internet? Millions of people rely on it for productivity and fun in countless cafes, railway stations and public areas of all sorts. For many institutions, ensuring wireless Internet access is now almost as important a feature of building facilities as the access to water and electricity. Typically, buildings are connected to the Internet using a fiber backbone. In order to provide wireless Internet access, wireless routers are placed around the building and connected using fiber cables to the backbone. The larger and more complex the building, the harder it is to pick router locations and decide how to lay down the connecting cables.

Streaming videos

Hash Code 2017, Online Qualification Round
[download id=”4178″]
Have you ever wondered what happens behind the scenes when you watch a YouTube video? As more and more people watch online videos (and as the size of these videos increases), it is critical that video-serving infrastructure is optimized to handle requests reliably and quickly. This typically involves putting in place cache servers, which store copies of popular videos. When a user request for a particular video arrives, it can be handled by a cache server close to the user, rather than by a remote data center thousands of kilometers away. Given a description of cache servers, network endpoints and videos, along with predicted requests for individual videos, decide which videos to put in which cache server in order to minimize the average waiting time for all requests.

Schedule Satellite Operations

Hash Code 2016, Final Round
[download id= “2596”]A satellite equipped with a high-resolution camera can be an excellent source of geo imagery. While harder to deploy than a plane or a Street View car, a satellite — once launched — provides a continuous stream of fresh data. Terra Bella is a division within Google that deploys and manages high-resolution imaging satellites in order to capture rapidly-updated imagery and analyze them for commercial customers. With a growing constellation of satellites and a constant need for fresh imagery, distributing the work between the satellites is a major challenge. Given a set of imaging satellites and a list of image collections ordered by customers, schedule satellite operations so that the total value of delivered image collections is as high as possible.

Optimize Drone Deliveries

Hash Code 2016, Online Qualification Round
[download id=”2595″]
The Internet has profoundly changed the way we buy things, but the online shopping of today is likely not the end of that change; after each purchase we still need to wait multiple days for physical goods to be carried to our doorstep. Given a fleet of drones, a list of customer orders and availability of the individual products in warehouses, schedule the drone operations so that the orders are completed as soon as possible.

Route Loon Balloons

Hash Code 2015, Final Round
[download id=”2594″]
Project Loon aims to bring universal Internet access using a fleet of high altitude balloons equipped with LTE transmitters. Circulating around the world, Loon balloons deliver Internet access in areas that lack conventional means of Internet connectivity. Given the wind data at different altitudes, plan altitude adjustments for a fleet of balloons to provide Internet coverage to select locations.

Optimize a Data Center

Hash Code 2015, Online Qualification Round
[download id=”2593″]
For over ten years, Google has been building data centers of its own design, deploying thousands of machines in locations around the globe. In each of these of locations, batteries of servers are at work around the clock, running services we use every day, from Google Search and YouTube to the Judge System of Hash Code. Given a schema of a data center and a list of available servers, your task is to optimize the layout of the data center to maximize its availability.

Street View Routing

Hash Code 2014, Final Round
[download id=”2592″]
The Street View imagery available in Google Maps is captured using specialized vehicles called Street View cars. These cars carry multiple cameras capturing pictures as the car moves around a city. Capturing the imagery of a city poses an optimization problem: the fleet of cars is available for a limited amount of time and we want to cover as much of the city streets as possible.