Hello there, here's an unofficial editorial for 1136D. Yui and Mahjong Set by a tester PinkRabbitAFO.
Observation: Focus on the differential of triplets/straights before and after an operation.
By doing an operation on $$$a_i$$$, you'll find that the differential of triplets equals $$$x (x - 1) / 2$$$, where $$$x$$$ equals $$$a_i$$$ before the operation.
So if we did a single operation on $$$a_i$$$, we can get the exact value of initial $$$a_i$$$ iff initial $$$a_i \ge 2$$$, otherwise initial $$$a_i$$$ must be equal to $$$0$$$ or $$$1$$$.
If we did two (or more, but unnecessary?) operation on $$$a_i$$$, we can now get the exact value of initial $$$a_i$$$ no matter whether $$$a_i$$$ is less than $$$2$$$ or not.
One of the most natural ideas is to perform operation in the order of $$$1, 2, \ldots, n$$$, it works like this:
Now, assume we get the exact value of $$$a_1 \sim a_i$$$, and we want to determine $$$a_{i + 1}$$$.
If $$$a_{i + 1} \ge 2$$$, done. Just consider the case $$$a_{i + 1} = 0$$$ or $$$1$$$.
Consider the differential of straights when doing the operation on $$$a_i$$$, let it be $$$d_i$$$ for convenience.
We have $$$d_i = [(a_{i - 2} + 1) (a_{i - 1} + 1) + (a_{i - 1} + 1) a_{i + 1} + a_{i + 1} a_{i + 2}]$$$ (if any indices out of bounds, just ignore that term).
If $$$a_{i + 1} = 0$$$, then $$$d_i = (a_{i - 2} + 1) (a_{i - 1} + 1)$$$.
If $$$a_{i + 1} = 1$$$, then $$$d_i = [(a_{i - 2} + 1) (a_{i - 1} + 1) + (a_{i - 1} + 1) + a_{i + 2}] > (a_{i - 2} + 1) (a_{i - 1} + 1)$$$ (because $$$a_{i - 1} + 1 > 0$$$).
So we can determine $$$a_{i + 1}$$$ by comparing $$$d_i$$$ and $$$(a_{i - 2} + 1) (a_{i - 1} + 1)$$$.
Note that you cannot use $$$d_{i - 1} = [(a_{i - 3} + 1) (a_{i - 2} + 1) + (a_{i - 2} + 1) * a_i + a_i * a_{i + 1}]$$$, because when $$$a_i = 0$$$ it's impossible to solve $$$a_{i + 1}$$$ (dividing by zero).
It's easy to see that only when $$$i \ge 2$$$, the method will work, so we need to get $$$a_1$$$ and $$$a_2$$$.
But it seems so hard to get any information of them.
Why not brute force? Try all possibilities of $$$a_1$$$ and $$$a_2$$$ (not many, $$$2^2 = 4$$$ at most) and run solution above.
I came up with this idea when testing the round, and got a verdict of WA on test 11.
Unfortunately, it cannot distinguish between $$$a = [1, 0, 0, 0]$$$ and $$$a = [0, 0, 0, 1]$$$.
More optimization needed.
First, notice that we don't need to do an operation on $$$a_n$$$. Why?
When $$$i = n - 1$$$, $$$d_i = [(a_{n - 3} + 1) (a_{n - 2} + 1) + (a_{n - 2} + 1)a_ n]$$$, thanks to the disappearance of the third term, and the coefficient $$$(a_{n - 2} + 1) \ne 0$$$, now can use division to solve $$$a_n$$$.
So we saved a move, where can it be added to?
It turns out if you add the operation to $$$a_1$$$ once more, you'll have a chance to find the correct solution.
That is, ask $$$1, 2, \ldots, (n - 1)$$$ and then $$$1$$$, in total $$$n$$$ operations.
Focus on the new operation, from it we can get $$$a_1$$$ at once.
Don't forget to use $$$d$$$, here $$$d = (a_2 + 1) (a_3 + 1)$$$.
Compare with the first $$$d_1 = a_2 a_3$$$, do a subtraction, we can get the value of $$$a_2 + a_3$$$.
Now the classification comes:
If $$$a_2 \ge 2$$$ or $$$a_3 \ge 2$$$, we can immediately get both $$$a_2$$$ and $$$a_3$$$.
Else if $$$a_2 + a_3 = 0$$$, $$$a_2 = a_3 = 0$$$.
Else if $$$a_2 + a_3 = 2$$$, $$$a_2 = a_3 = 1$$$.
Now exactly one of $$$a_2$$$ and $$$a_3$$$ is $$$1$$$ and the other is $$$0$$$.
Consider $$$d_2 = (a_1 + 1) a_3 + a_3 a_4$$$.
If $$$a_3 = 0$$$, then $$$d_2 = 0$$$.
If $$$a_3 = 1$$$, then $$$d_2 > 0$$$.
So, just check whether $$$d_2$$$ is equal to $$$0$$$ or not.
Now $$$a_{1, 2, 3}$$$ are known, use the method above, problem solved.
As I mentioned before, until the contest ends (tester round), I didn't realize "$$$1, 2, \ldots, n$$$" is not gonna work.
After communicating with Sulfox about the main solution, I made up my mind to discover a different solution.
After hours of "thinking" (chatting online) I found this solution.
Coincidentally, many participants came up with the same idea, and I'm very glad to see that.
Said too much.
Sorry for bad English expression (didn't check) (hopefully ouuan and Sulfox will fix them in the official editorial).
Questions welcomed.
Gonna sleep (almost 6 AM here).
btw, Sooke's solution is $$$(n-1), (n-2), \ldots , 4, 3, 1, 2, 1$$$.
I think some people didn't even try proving anything here, just used backtrack and kept fingers crossed it will work fast. Backtrack may seem very suspicious, but by keeping fingers crossed I meant I though "I think it can be somehow proven that we can uniquely determine some values based on gotten info, hence my backtrack will have O(n) nodes" (which is more or less what you did), not anything like "oh, maybe they have shitty tests and I can push through some exponential solution".
My solution was $$$1,1,3, 2,4,5,6,..,n-1$$$ if $$$n \geq 5$$$ and a brute force for $$$n=4$$$(76903850) . Figuring out the first $$$4$$$ elements given the results of the first $$$4$$$ queries took me a really long time, I think that if I thought of $$$1,2,3,4,...,n-1,1$$$ maybe I would've finished coding it before the contest ended.
The way I came up with $$$1,1,3, 2,4,5,6,..,n-1$$$ was by making a brute force which checks which moves make each starting position give a different set of answers and i saw that, for example, for $$$n=6$$$ that was the lexicographically smallest set of moves which works.
Well, my solution is the same as yours until the point
Compare with the first d_1=a_2a_3, do a subtraction, we can get the value of a_2+a_3.. Actually we know the value of $$$a_3$$$ already so thats no need to do lots of casework for $$$a_2$$$ and $$$a_3$$$ :thinking:hmm, yeah a little complicated there. but it's always better when considering only 0/1.
In short, Thank you :)
Isn't the statement bit ambiguous?
At first, Yui gives you the number of triplet subsets and straight subsets of the initial set respectively. After that, you can insert a tile with an integer value between 1 and n into the set at most n times
shouldn't it mean that any integer $$$i$$$ can be queried not more than $$$n$$$ times. Thus total number of queries can be more than $$$n$$$. I tried it solving (for practice) where total number of queries exceeds $$$n$$$ but not the sum of $$$i$$$ and it gives me verdict
wrong answer you inserted more than n tiles
Please can someone clarify about this constraint on number of queries.
Kaavi and Magic Spell
We will first make a dp[i][j] $$$\rightarrow$$$ No of ways to make the last j words of the prefix T using the first i letters of S.
Now it is clear , $$$dp[i][j] = 0$$$ if $$$i<j$$$
Let's think about the other states.
if we have the ith element from S , that will either go to the front or to the back of A , Now if if matches the jth letter from the end of T , then we can do that. The other thing we can do, is send to the back. Now here arises a problem , on sending it to the back there can arise two possibilities , it is counted in the prefix T or it is not. Now we can see it will be counted as the last letter of the Prefix T $$$\text{iff}$$$ $$$i=j$$$ , else we can freely put it on the back.
So now we have
So the only state we have a Problem in Calculating is $$$dp[i][i]$$$
To Calculate that , let's define another dp $$$dp2[i][point]$$$ = No of ways to make $$$\text{T[point point+1 .... point+i-1]}$$$ (Basically the $$$i$$$ length substring of $$$T$$$ starting from Point) using the first $$$i$$$ letters of S.
$$$dp2[i][point] = dp2[i-1][point]\text{ (if S[i] matches the T[i+point-1] ) }+ dp[i][point+1]\text{ (if s[i] matches the T[point] )}$$$
So now we can easily say $$$dp[i][i] = dp2[i][m-i+1]$$$ , and we have calculated our answer.
Solution