Esab Atad
Problem
Last year, a research consortium had some trouble with a distributed database system that sometimes lost pieces of the data. You do not need to read or understand that problem in order to solve this one!
The consortium has decided that distributed systems are too complicated, so they are storing B bits of important information in a single array on one awesome machine. As an additional layer of security, they have made it difficult to obtain the information quickly; the user must query for a bit position between 1 and B, and then they receive that bit of the stored array as a response.
Unfortunately, this ultra-modern machine is subject to random quantum fluctuations! Specifically, after every 1st, 11th, 21st, 31st... etc. query is sent, but before the response is given, quantum fluctuation causes exactly one of the following four effects, with equal probability:
25% of the time, the array is complemented: every 0 becomes a 1, and vice versa.
25% of the time, the array is reversed: the first bit swaps with the last bit, the second bit swaps with the second-to-last bit, and so on.
25% of the time, both of the things above (complementation and reversal) happen to the array. (Notice that the order in which they happen does not matter.)
25% of the time, nothing happens to the array.
Moreover, there is no indication of what effect the quantum fluctuation has had each time. The consortium is now concerned, and it has hired you to get its precious data back, in whatever form it is in! Can you find the entire array, such that your answer is accurate as of the time that you give it? Answering does not count as a query, so if you answer after your 30th query, for example, the array will be the same as it was after your 21st through 30th queries.
Input and output
This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.
Initially, your program should read a single line containing two integers T and B: the number of test cases and the number of bits in the array, respectively. Note that B is the same for every test case.
Then, you need to process T test cases. In each case, the judge begins with a predetermined B-bit array; note that this array can vary from test case to test case, and is not necessarily chosen at random. Then, you may make up to 150 queries of the following form:
Your program outputs one line containing a single integer P between 1 and B, inclusive, indicating which position in the array you wish to look at.
If the number of queries you have made so far ends with a 1, the judge chooses one of the four possibilities described above (complementation, reversal, complementation + reversal, or nothing), uniformly at random and independently of all other choices, and alters the stored array accordingly. (Notice that this will happen on the very first query you make.)
The judge responds with one line containing a single character 0 or 1, the value it currently has stored at bit position P, or N if you provided a malformed line (e.g., an invalid position).
Then, after you have made as many of the 150 queries above as you want, you must make one more exchange of the following form:
Your program outputs one line containing a string of B characters, each of which is 0 or 1, representing the bits currently stored in the array (which will not necessarily match the bits that were initially present!)
The judge responds with one line containing a single letter: uppercase Y if your answer was correct, and uppercase N if it was not (or you provided a malformed line). If you receive Y, you should begin the next test case, or stop sending input if there are no more test cases.
After the judge sends N to your input stream, it will not send any other output. If your program continues to wait for the judge after receiving N, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error. As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment.
Limits
Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
Test set 1 (Visible Verdict)
B = 10.
Test set 2 (Visible Verdict)
B = 20.
Test set 3 (Hidden Verdict)
B = 100.
Testing Tool
You can use this testing tool to test locally or on our servers. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. The interactive runner was changed after the 2019 contest. Be sure to download the latest version. For more information, read the Interactive Problems section of the FAQ.
Local Testing Tool
To better facilitate local testing, we provide you the following script. Instructions are included inside. You are encouraged to add more test cases for better testing. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently.
If your code passes the testing tool but fails the real judge, please check the Coding section of our FAQ to make sure that you are using the same compiler as us.
Sample Interaction
The following interaction corresponds to Test Set 1.
t, b = readline_int_list() // reads 100 into t and 10 into b.
// The judge starts with the predetermined array for this test case:
// 0001101111. (Note: the actual Test Set 1 will not necessarily
// use this array.)
printline 1 to stdout // we ask about position 1.
flush stdout
// Since this is our 1st query, and 1 is 1 mod 10, the judge secretly and
// randomly chooses one of the four possible quantum fluctuation effects, as
// described above. It happens to choose complementation + reversal, so now
// the stored value is 0000100111.
r = readline_chr() // reads 0.
printline 6 to stdout // we ask about position 6.
flush stdout
// Since this is our 2nd query, and 2 is 2 mod 10, the judge does not choose
// a quantum fluctuation effect.
r = readline_chr() // reads 0.
...
// We have omitted the third through tenth queries in this example.
...
printline 1 to stdout // we decide to ask about position 1 again.
flush stdout
// Since this is our 11th query, and 11 is 1 mod 10, the judge secretly and
// randomly chooses a quantum fluctuation effect, and happens to get
// reversal, so now the stored value is 1110010000.
r = readline_chr() // reads 1.
printline 1110110000 to stdout // we try to answer. why?!?!
flush stdout
ok = readline_chr() // reads N -- we have made a mistake!
exit // exits to avoid an ambiguous TLE error
Analysis
Test Set 1
In Test Set 1, there are only 10 positions in the string. We can query for each of them and then submit the complete string, without having to worry about any quantum fluctuations (which would only happen if we submitted an 11th query).
Test Set 2
Here is one of various ways to solve the second test set. We begin by querying for the first ten positions in the real string, then create a "possibility set" containing all 1024 20-character strings that begin with those 10 characters. Then we update our "possibility set" to contain all strings that could have arisen from those strings after the next quantum fluctuation. The correct answer is in here somewhere — now we need to narrow the set down!
Before making each subsequent query, we first find the string index (between 1 and 20) at which the proportion of 0s and 1s among the strings in our possibility set is most nearly even. Then we query the real string at that index, and eliminate from the possibility set any strings that are not consistent with that information. Whenever we can indeed find a position with even proportions, we are guaranteed to cut the size of the set in half, but if there is no such position, we may not be able to eliminate that many possibilities. We can continue in this way, remembering to expand the possibility set every time there is a quantum fluctuation, until only one possibility remains, which must be the answer.
It is not easy to prove that this strategy will converge upon an answer. Intuitively, we can observe that a quantum fluctuation increases the size of the possibility set by at most 4, and even if we somehow only cut the possiblity set by 20% with each pruning, we would still easily beat that factor-of-4 increase and make enough progress to finish within 150 queries. Moreover, it would not be possible for the strings in the possibility set to all be distinct while being so similar at every individual position (recall that we always pick the position that will be most useful to us in the worst case). Also, Test Set 2 is a Visible Verdict set, so we might as well just submit our answer and see.
Test Set 3
The above strategy will not work for 100-character strings, since the possibility set would be astronomically huge. Fortunately, there is a much simpler approach.
Observe that if we can find two positions that are equidistant from the center of the string and have the same value, we can use them to detect when a quantum fluctuation has included a complementation (with or without a reversal). Suppose, for example, that the two ends of the string are 0 just before a quantum fluctuation. After the fluctuation, we can check the first one. If it is 1, then there was a complementation; if not, there wasn't one. This is true regardless of whether that quantum fluctuation included a reversal.
Now suppose that we continue to check pairs of positions in this way, moving inward one step at a time. After every quantum fluctuation, we must spend one query to check for complementation so we can update our existing knowledge about the string if there has been one. If every pair turns out to be a "same pair" like the first pair, then we never needed to care about reversals anyway (since the string is palindromic), and we are done.
But what if, in the course of this, we find a "different pair"? Such pairs are helpful in their own way! If we query the first position of a "different pair" after a quantum fluctuation and we find that that bit has changed, then we know that either a complementation or reversal has happened, but not both.
Once we have such a "different pair", we can use it in conjunction with the "same pair", spending 2 out of every 10 queries to learn exactly what happened in each quantum fluctuation. For example, if the first position of our "same pair" stayed the same but the first position of our "different pair" did not, we know that the quantum fluctuation included a reversal but no complementation.
In the above analysis, we assumed we would encounter a "same pair" first. If the first pair is different, though, we can proceed until we encounter a "same pair"; if we never encounter one, then we do not care about the distinction between complementation and reversal, because the operations are equivalent for that particular string. If we do encounter a "same pair", though, then we can proceed as above.
How many queries will we need in the worst case? We can use all of our first 10 to gather data, since whatever happened in the quantum fluctuation at the start of the problem is unknowable and does not matter. After that, we may need to use up to 2 out of every 10 queries to reorient ourselves before spending the remaining 8 gathering data. So, to be sure we can find the entire string, we will need 10 queries, plus 11 more sets of 10 queries in which we learn 8 positions each time, (to get us to 98 positions known), plus 2 more queries for a final reorientation, plus 2 more to get the last two positions. That is a total of 124, which is well within the allowed limit of 150.
Regarding the name...
Last year, we had the Dat Bae problem about deletions from a string in a database; the name was Data Base, altered in a way that reflected the theme. ESAb ATAd is similar, with case change serving as a rough equivalent of complementation. (Imagine how much the Code Jam team has enjoyed trying to type the name correctly each time!)
Recommended: Please try your approach on your integrated development environment (IDE) first, before moving on to the solution.
Few words from CodingHumans : Don't Just copy paste the solution, try to analyze the problem and solve it without looking by taking the the solution as a hint or a reference . Your understanding of the solution matters.
HAVE A GOOD DAY 😁
Solution:
( java )
import java.util.BitSet;
import java.util.Scanner;
public class EsabAtad {
private static String stringify(BitSet bitset, int bitCount) {
StringBuilder sb = new StringBuilder(bitCount);
for (int i = 0; i < bitCount; i++) {
sb.append(bitset.get(i) ? '1' : '0');
}
return sb.toString();
}
private static BitSet flip(BitSet bitset, int bitCount) {
BitSet result = new BitSet(bitCount);
for (int i = 0; i < bitCount; i++) {
result.set(i, !bitset.get(i));
}
return result;
}
private static BitSet reverse(BitSet bitset, int bitCount) {
BitSet result = new BitSet(bitCount);
for (int i = 0; i < bitCount; i++) {
result.set(bitCount - i - 1, bitset.get(i));
}
return result;
}
private static boolean readBit(Scanner scanner, int bitIndex) {
System.out.println(bitIndex + 1);
System.out.flush();
return scanner.next().charAt(0) == '1';
}
private static boolean runTest(int bitCount, Scanner scanner) {
BitSet bitset = new BitSet(bitCount);
int oppositeBitIndex = -1;
int specularBitIndex = -1;
int bitIndex = 0;
int queryIndex = 0;
while (bitIndex < bitCount / 2) {
if (queryIndex > 0 && queryIndex % 10 == 0) {
boolean oppositeChanged = false;
boolean specularChanged = false;
if (oppositeBitIndex >= 0) {
boolean bit = readBit(scanner, oppositeBitIndex);
oppositeChanged = bit != bitset.get(oppositeBitIndex);
} else {
readBit(scanner, 0);
}
if (specularBitIndex >= 0) {
boolean bit = readBit(scanner, specularBitIndex);
specularChanged = bit != bitset.get(specularBitIndex);
} else {
readBit(scanner, 0);
}
if (oppositeChanged && !specularChanged) {
bitset = reverse(bitset, bitCount);
} else if (!oppositeChanged && specularChanged) {
bitset = flip(reverse(bitset, bitCount), bitCount);
} else if (oppositeChanged && specularChanged) {
bitset = flip(bitset, bitCount);
}
} else {
boolean leftBit = readBit(scanner, bitIndex);
boolean rightBit = readBit(scanner, bitCount - bitIndex - 1);
if (leftBit != rightBit && oppositeBitIndex < 0)
oppositeBitIndex = bitIndex;
if (leftBit == rightBit && specularBitIndex < 0)
specularBitIndex = bitIndex;
bitset.set(bitIndex, leftBit);
bitset.set(bitCount - bitIndex - 1, rightBit);
bitIndex++;
}
queryIndex += 2;
}
String stringResult = stringify(bitset, bitCount);
System.out.println(stringResult);
System.out.flush();
char response = scanner.next().charAt(0);
if (response == 'Y') {
System.err.println("Correct: " + stringResult);
return true;
} else {
System.err.println("Wrong: " + stringResult);
return false;
}
}
public static void main(String[] args) {
long beginTime = System.nanoTime();
try (Scanner scanner = new Scanner(System.in)) {
int testCount = scanner.nextInt();
int bitCount = scanner.nextInt();
for (int testNumber = 1; testNumber <= testCount; testNumber++) {
if (!runTest(bitCount, scanner)) break;
}
}
System.err.println( "Done in " + ((System.nanoTime() - beginTime) / 1e9) + " seconds.");
}
}
