- 34
Learning Opportunities
This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.
Statement
Goal
Some top secret information has been shared between Her Majesty's double-zero agents. Time has come to reveal it! But in order to avoid the secret to fall too easily into the hands of the enemy, a deeply thought process has been used to share it.First, each of the nine double-zero agents (from 001 to 009) only carries a distinct "part" of the secret.
Also, there is a threshold k (
Finally, the knowledge of less than k parts does not allow to derive any information about the secret! (There might be some statistical biases for some poorly chosen parameters, but in general there is none.) The enemy has to capture or hire at least k agents to learn anything.
Your task is to figure out how to reveal the secret given at least k parts.
The following describes the secret sharing process in details.
First of all, the secret message S is written using the following alphabet of
where each character is identified by its index from
Given a threshold k ≥ 2, the secret sharing process is the following:
For each index i of S, a polynomial
P[i] = A[i,k-1]⋅X^(k-1) + A[i,k-2]⋅X^(k-2) + ... + A[i,1]⋅X + S[i]is defined where the coefficients A[..] are chosen randomly between
Each agent 00
Example: Consider k = 2 and S = "SIS" = [44, 34, 44].
For each character we pick a random polynomial of degree 1 with the corresponding character as constant coefficient:
P0 = 41X + 44, P1 = 8X + 34, P2 = 2X + 44Agent 001 receives [P0(1)%53, P1(1)%53, P2(1)%53] = [32, 42, 46] = GQU;
Agent 002 receives [P0(2)%53, P1(2)%53, P2(2)%53] = [20, 50, 48] = uYW;
...
Input
Line 1: An integer N, the number of parts gathered.
Next N lines: The code number Ci of an agent followed by his part Si of the secret. All the Si have the same size.
Next N lines: The code number Ci of an agent followed by his part Si of the secret. All the Si have the same size.
Output
One single string corresponding to the revealed secret.
Constraints
It is guaranteed that N ≥ k the threshold that was used to share the secret.
All the Si have the same length <
Example
Input
2 005 Lvb 004 Xn_
Output
SIS
A higher resolution is required to access the IDE