As the highest non-red, non-alt-account person in the round, I feel it is my duty to supply the community with an editorial.
2168A1 - Encode and Decode (Easy Version)
Since $$$1 ≤ a_i ≤ 26$$$, we can assign each value from $$$1$$$ to $$$26$$$ to a letter a-z.
2168A2 - Encode and Decode (Hard Version)
Using $$$7$$$ characters, we can encode $$$26^7 \approx 8 \cdot 10^9$$$ possibilities. For each number in the array, encode into a $$$7$$$-digit base-$$$26$$$ number. It is important to make sure each number takes up the same number of characters.
2168B - Locate
Let's try to solve the problem player B has to solve.
Let the range of a subarray be $$$max(p_l, p_{l+1}, ..., p_r) - min(p_l, p_{l+1}, ..., p_r)$$$. A subarray has range $$$n-1$$$ iff it contains both $$$1$$$ and $$$n$$$. We can binary search on the shortest prefix with range $$$n-1$$$, this will find the latter position of $$$1$$$ or $$$n$$$. Also binary search on the shortest suffix with range $$$n-1$$$, this will find the former position of $$$1$$$ or $$$n$$$. Now we've found the position of $$$1$$$ and $$$n$$$, but we don't know which is which.
This is where player A comes in. If $$$1$$$ appears before $$$n$$$, he will send $$$0$$$; otherwise, he will send $$$1$$$. Now player B can figure out which is which.
2168C - Intercepting Butterflies
Let's phrase the problem slightly differently.
- Player A has a binary string of length $$$15$$$, and he will send a binary string of length $$$20$$$.
- On the way, none or one of the bits get flipped.
- Given the altered string, $$$B$$$ must find the original binary string of length $$$15$$$.
The first $$$15$$$ bits ($$$s_{1..15}$$$) will be allocated for the original string, and the remaining $$$5$$$ bits will be used to reconstruct where the flip happened.
The next $$$4$$$ ($$$s_{15..19}$$$) will house the bitwise XOR of the all the positions in the original string that are 1. The last bit ($$$s_{20}$$$) will be the number of bits in previous $$$4$$$ bits mod $$$2$$$.
Now there are $$$2$$$ cases:
Case 1: A flip happens in $$$s_{16..20}$$$
We can detect this case by checking if the last bit matches what it's supposed to be. If it doesn't, a flip has happened somewhere in the last $$$5$$$ bits. In this case, the original $$$15$$$ are completely untouched.
Case 2: A flip doesn't happen or happens in $$$s_{1..15}$$$
Here, we calculate the bitwise XOR of all the 1 in $$$s_{1..15}$$$. Let $$$x$$$ be this value and $$$y$$$ be the number stored in $$$s_{16..19}$$$. The cool thing is: $$$x \bigoplus y$$$ will be the position of the flipped bit, or $$$0$$$ if no flip occurred. This is because if a flip occured at position $$$k$$$, $$$x$$$ becomes $$$x \bigoplus k$$$.
nice, I'll link this in the contest
Thanks, I'll change the title
An official one will be coming soon so you can keep the old title.
Or... name yours (unofficial)
It's still not here yet...
Auto comment: topic has been updated by Sul_A. (previous revision, new revision, compare).
Auto comment: topic has been updated by Sul_A. (previous revision, new revision, compare).
For A2, you can just use 10 characters to encode each number since $$$n\leq 10^4$$$ and $$$|s|\leq 10^5$$$. Each number $$$|a_i|\leq 10$$$ since the max number $$$10^9$$$ is 10 characters.
yes , i done the same , but is there any other method to do it ?
nice contest,in the a2 i use a to k with map for number form 0 to 9.
For the last problem, a following greedy also work: firstly, we notice that is suffices that the players A and B agree on a function $$$f: 0, 1]^{15} \to [0, 1]^{20}$$$ that have the following property:
In fact, the encoding from the editorial satisfies this property (this is easy to check).
This is because if the player B recieves some bitmask from $$${0, 1}^{20}$$$, he will be able to loop through all the possible inputs and see which differs at at most a single position and it will be unambigusly the correct input. In fact, the construction from the tutorial allows B to compute the input directly, without looping.
But we can do something much simpler: just assign values to all $$$f(i)$$$ s one by one with a greedy approach: take the first allowed bitmask and mark all other bitmasks in the popcount distance of $$$ \leq 2$$$ as unavailable. It turns out that $$$2^{20}$$$ is enough of a set size for this greedy to work.
Code: 347305056
How do you know if assignment order is actually optimal, and maybe some better order exists that does the job in 19 bits or lower?
I don't and I doubt it actually is optimal. I implemented the simplest greedy that came to my mind and it turned out it was sufficient. If this simple greedy had failed, I would probably then try additional heuristics, for example picking the available bitmask that has the most overlap with unavailable masks (to minimize waste). If several heuristics had failed, I would try to search for structured approach.
Also, in this particular problem we have a ratio of $$$2^{20}/2^{15}=32$$$, so if each bitmask has 190 neighbors within distance of 2, we need to reuse each unavailable bitmask about 6 times, which seems doable for a simple greedy.
Fun fact: the approach used for problem C described in the editorial has a well known name: Hamming codes. I'm unsure why the authors chose to leave this out. Anyway, there's also an awesome 3b1b video that describes the exact algorithm needed to solve this. Here's my code for reference.
Also, a very similar idea shows up in this CSES problem, this EGOI problem, and the first suubtask of this CEOI problem.
Does your approach for problem C have a name? It is quite similar to Hamming code and almost as efficient as it (requires at most 1 more bit than Hamming codes).
I believe it is basically Hamming codes, in the way it detect errors. In addition, $$$19$$$ bits is actually possible if we just ignore the last bit $$$s_{20}$$$ (because we know that there is at most one bit swapped, and usually error-detection (in this case) in Hamming codes doesn't require this bit afaik). My solution for this problem uses $$$19$$$ bits also.
I've looked at your code and it seems using 20 bits.
19 bits should be theoretically impossible because if you need to choose numbers $$$x_1, \ldots, x_{2^{15}}$$$ from a total of $$$2^{19}$$$ numbers s. t. their $$$f(x_i)$$$ are pairwise non-intersecting ($$$f(x)$$$ is the set of all numbers that differ from $$$x$$$ in at most 1 bit) you need at least $$$\sum\limits_{i=1}^{2^{15}}{|f(x_i)|} = \sum\limits_{i=1}^{2^{15}}{20} = 655360$$$ numbers to do so which is larger than $$$2^{19}$$$.
Communication Problems are very fun. Hope to see them in official contests.
For Problem A2, we can encode every number with its number of digits $$$+$$$ that number in string.
Like for example, $$$9999$$$ would be encoded as $$$49999$$$ $$$\rightarrow$$$ $$$ejjjj$$$.
This would work for $$$n \lt 10^9$$$, since for $$$10^9$$$ we would have ten digits, for $$$n=10^9$$$ we can just use some unused character like $$$z$$$ to represent it.
I came to the same conclusion but after the contest tho.
I thought of this idea and the base changing idea as well, but another similar approach could also be using some unused random character $$$( \gt j)$$$ in between converted numbers. This should give a similar effect but the result will be one character shorter.
We could also combine this idea with the change of base approach, having start and end/length determining characters and using a lower base than 26. This might be overkill though. (Sorry for somewhat redundant reply, just wanted to share)
In the problem B, we actually only need to binary search once. Because it doesn't matter if we know the location of $$$1$$$, we only need to do one search to find the location of $$$n$$$, given $$$x$$$.
The minimal prefix will always contain $$$1$$$ but end in $$$n$$$ if $$$n$$$ is later in the permutation. The minimal suffix will always contain $$$1$$$ but begin with $$$n$$$ if $$$n$$$ is earlier in the permutation.
I wrote my code on the problem a2 and i encoded the numbers of 1234567890 to qwertyuiop and for each stopping a 'g' my code ran and the a1 was accepted but on a2 it said wrong awnser on test 9, what could be the reason for this? Is it because it ran out of memory or what im very confused
If the array is all $$$10^9$$$, then your code will output a string with more than $$$10^5$$$ characters.
Can you please suggest why my code got a WA?
Code: 347275534
I did it the same way as CaptainMayer, but actually, why would it give a WA? I’m just confused.
Same issue
did u get it same issue i am facing code
this got AC
You can check whether the number you are encoding contains 10 digits; if it does, there is no need to use the stopper 'g.' Then, while you decode, you will know that the number is finished if you find your stopper 'g' or find 10 consecutive characters (non 'g' chars).
what could be the rating of A2? (if it was in a rated contest)
1100 — 1200
For problem rating predictions, you can use Clist which is usually accurate. However, this contest is special so they might be somewhat inaccurate.
For B, we can run binary search only once. If the permutation has $$$1$$$ earlier than $$$n$$$, the shortest prefix that returns $$$n-1$$$ will have $$$n$$$ at its end. But what if not? Well, if not, no worries. Player B will only find shortest suffix instead of prefix and the $$$n$$$ will be at the beginning. So player A needs to only tell if $$$1$$$ comes before $$$n$$$ or not.
For problem B, I think it should be emphasized that $$$x$$$ is meant to help player B solve the problem.
For problem C I was trying the following approach: - always use 20 numbers so butterflies can't add - use 10 and 20 as flags for the start of a valid signal - if we find 9 numbers between start flags / after second start flag then that's our valid signal - map each n to the nth permutation of {1, 2, 3 ... 9} or {11, 12, 13, ... 19}
For some reason my code RTE's because it seems like I'm being given 2 inputs per test case 348270329 ...
Maybe I'm misreading the submission info tho idk
EDIT: nvm I just re-read the problem statement and realised that they sort the set before giving it back to you lol
Hello, I am interested in run-twice (communicative) problems and would like to create my own tasks in Polygon. Could you please publish a detailed guide on how to set up this type of problem, or share an example project in Polygon? Thank you.
Personally I followed this when creating the communication problem for my round
Thanks
Thanks you