Our solution for Google HashCode 2021 Online Qualifications
You can find the problem statements here.
The code for the solution is in src.cpp. Our approach was a greedy algorithm.
The solution follows these steps:
-
Read the inputs
-
Duration of green light:
-
Count the number of vehicles passing through the each street.
-
Divide the counts by the weight. (The weight for each file was found by grid search)
-
-
Order of green light:
- Sort by the number of vehicles at the beginning.
| File | Score |
|---|---|
| a.txt (input | output) | 2,002 |
| b.txt (input | output) | 4,566,011 |
| c.txt (input | output) | 1,299,333 |
| d.txt (input | output) | 1,606,638 |
| e.txt (input | output) | 728,661 |
| f.txt (input | output) | 1,411,047 |
| Total | 9,613,692 |