All submissions for this problem are available.
Google researchers and academics have today demonstrated it is possible – following years of number crunching – to produce two different documents that have the same SHA-1 hash signature. SHA-1 is supposed and widely used source-code management tool Git. It is possible to create two Git repositories with the same head commit SHA-1 hash and yet the contents of the two repos differ.
In company called Prolexic, every programmer commits the code to their software via Continuous Integration and VCS GitHub. You have commit logs of their recent software. You have to find whether there is a SHA-1 Collision or not. If there is a collision, are there two programmers who will be facing an issue, or the same programmer will face the issue. Or, find whether no programmers will be facing any issue due to it.
The log is of form timestamp username SHA-1 Commit, where you to find programmer(s) with which username will face the issue, where collision happens when there is a SHA-1 repeated for different commits.
First line will contain T the number of test cases. Each test case will start with N the number of commits. Next N lines will have logs in the form mentioned above.
For each test case, print 2 if 2 programmers will face the issue, 1 if only one programmer will face the issue, or print -1 if no programmers will face any issue.
- 1 ≤ T ≤ 20
- 2 ≤ N ≤ 26
- | SHA-1 | = 32
- | timestamp | = 10
- | username | ≤ 64
- All strings are lowercase
Input: 3 3 1400203032 nerdyninja 4e4d6c332b6fe62a63afe56171fd3725 1400233032 adikul30 7320eede6fd68c1d7a28506efbf593e7 1400201232 nerdyninja 4e4d6c332b6fe62a63afe56171fd3725 3 1400203032 nerdyninja 4e4d6c332b6fe62a63afe56171fd3725 1400233032 nerdyninja 7320eede6fd68c1d7a28506efbf593e7 1400201232 adikul30 4e4d6c332b6fe62a63afe56171fd3725 2 1400203032 nerdyninja 4e4d6c332b6fe62a63afe56171fd3725 1400201232 adikul30 7320eede6fd68c1d7a28506efbf593e7 Output: 1 2 -1
Example 1: nerdyninja only faced the SHA-1 collision.
Example 2: adikul30 and nerdyninja faced the SHA-1 collision.
Example 3: There was no SHA-1 collision
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions