Internet Problem Solving Contest

IPSC 2018

Problem G – Git gud

We did it! We finally created a fully-functional time machine. It can only send information back and forth, but that’s more than enough if you know how to take advantage of it.

Obviously, the first thing we did was to establish communications with ourselves 50 years in the future, so that future-us can send present-us a copy of all the IPSC problems they made and we won’t have to do any more work. They immediately agreed and sent us 50 years’ worth of problems. And what’s even better, the data was not in some crazy future file format that hasn’t been invented yet. It was just a Git repository.

But when we tried to open it and find out what’s inside, disaster struck. Our computer crashed and the time machine got disconnected. Please help us!

Problem specification

You are given a valid Git repository. Print a checksum of the list of files it contains.

Input specification

The input is a Git repository. Every file and directory in it has a name consisting only of lowercase English letters, numbers, dashes (“-”) and periods (“.”). The repository can be downloaded with this command:

git clone https://ipsc.ksp.sk/2018/real/problems/g.git

The repository has three branches: example, easy and hard. When you clone it, Git will rename them to origin/example, origin/easy and origin/hard in your copy.

Instead of getting the repository from ipsc.ksp.sk, you can use g_local.py from the downloadable archive. This script will start a local server containing the same repository. Use it as follows:

python3 g_local.py                      # (in one window)
git clone http://localhost:8000/g.git   # (in another window while g_local.py is running)

Output specification

Submit a file with a single number: the checksum of the file list, as defined below.

The file list contains one line for each file in the repository. Each file is printed with its full path, using “/” (ASCII code 47) as the directory separator. The lines of the file list are sorted lexicographically and each line is followed by a UNIX newline (ASCII code 10). There is no extra whitespace.

The checksum is produced as follows. Interpret the file list as a sequence of ASCII codes. Multiply each of these ASCII codes by its 1-based position in the sequence. The checksum is their sum modulo 109 + 7. For example, the checksum of “Cat⏎” is $(1\cdot 67+2\cdot 97+3\cdot 116+4\cdot 10)\bmod (10^9+7)=649$.


Sorted file list for the "example" branch: