Hi all, Atcoder Beginner Contest 171 was today. I wrote an unofficial English editorial. Hope it helps!
A: αlphabet
We simply write an if statement.
Runtime: $$$\mathcal{O}(1)$$$.
B: Mix Juice
We want to buy the cheapest fruits, so we can sort the array and then pick the first $$$K$$$ fruits.
Runtime: $$$\mathcal{O}(N \log N)$$$.
C: One Quadrillion and One Dalmatians
The trick is to look at the letters starting from the end of the names. You can see the last letter repeats every $$$26$$$ names. The second-to-last letter repeats every $$$26^2$$$ names (after you skip the first $$$26$$$ names that are too short). The third-to-last letter repeats every $$$26^3$$$ names (after you skip the first $$$26 + 26^2$$$ names that are too short).
This gives rise to a solution where we extract the last letter first by setting $$$N = N-1$$$, then looking at the value modulo $$$26$$$. Then to shift everything over, we divide by $$$26$$$, and repeat the whole process as necessary. The subtraction of $$$1$$$ at the beginning of the loop accounts for skipping all the necessary shorter strings.
Take care to reverse the string.
Runtime: $$$\mathcal{O}(\log_{26} N)$$$, or equivalently $$$\mathcal{O}(L)$$$ where $$$L$$$ is the length of the answer.
D: Replacing
A few quick observations:
- The order of $$$A$$$ doesn't matter.
- Once two elements of $$$A$$$ are equal, they will never diverge.
This motivates us to think about the counts of each element in $$$A$$$, rather than the elements themselves. Because the elements are small (less than $$$10^5$$$), we can easily store the counts in an array.
In order to process a query, we move everything from $$$B_i$$$ to $$$C_i$$$ and update our sum appropriately. This means adding $$$\mathrm{count}[B_i]$$$ to $$$\mathrm{count}[C_i]$$$ and setting $$$\mathrm{count}[B_i]$$$ to zero, as well as changing our running sum by $$$\mathrm{count}[B_i] (C_i - B_i)$$$.
Take care to use $$$\mathrm{count}[B_i]$$$ before you set it to zero.
Runtime: $$$\mathcal{O}(N + Q + M)$$$, where $$$M = 10^5$$$, the largest possible element value.
E: Red Scarf
The key observation (and super useful fact about xor in general) is that $$$x \oplus x = 0$$$ for any $$$x$$$. This means a lot cancels out.
Let $$$c_i$$$ be a valid original array of cats (so, this is our answer we want to output).
Let's first rewrite $$$a_i$$$ using our observation above. Let $$$X$$$ be the xor of all elements in $$$c$$$. Then $$$a_i = X \oplus c_i$$$.
So, we can simply compute $$$c_i = X \oplus a_i$$$ and we are done.
Runtime: $$$\mathcal{O}(N)$$$.
F: Strivore
Let's consider the end result of this process and what it can look like. It will be a string (let's call it $$$T$$$) of length $$$N = K + |S|$$$ that contains $$$S$$$ as a subsequence.
We'll use $$$Z = 26$$$ for readability.
In order to count these, let's first note that there are $$$Z^N$$$ total strings of length $$$N$$$, and we want to remove all the strings that don't contain $$$S$$$ as a subsequence (this is a bit easier than counting the strings that do contain $$$S$$$, because a string could contain $$$S$$$ multiple times and be overcounted).
Let's consider the length of the maximum prefix of $$$S$$$ that's a subsequence of our string $$$T$$$. Going from left to right within $$$T$$$, we can check when this increases -- it increases from $$$X$$$ to $$$X+1$$$ when our current character is $$$S_{X+1}$$$. In order for it to not increase, we need our current character to not be $$$S_{X+1}$$$.
So let's say this length is exactly $$$M$$$. Then it must have increased from $$$0$$$ to $$$M$$$ (one at a time, of course), so we pick $$$M$$$ indices in $$$T$$$ to be the indices where it increases, and those have only one choice of character. The remaining characters have $$$Z-1$$$ choices. So for length $$$M$$$, we have $$$\binom{N}{M} (Z-1)^{N-M}$$$ possibilities.
In order to not contain $$$S$$$ as a subsequence, $$$M$$$ can be anything from $$$0$$$ to $$$|S| - 1$$$. Now, recall these are the strings we don't want, so we subtract them from the total.
Therefore, our final answer is $$$\displaystyle Z^N - \left[\sum_{M=0}^{|S|-1} \binom{N}{M} (Z-1)^{N-M}\right]$$$.
Runtime: $$$\mathcal{O}(K + |S|)$$$.
You can see my submissions here as well, if you prefer that to reading the code in the blog.
Thanks for reading! Let me know if you have any questions or feedback for me.
my bad I solved question C after the contest ends and 3 questions in the contest (A, B, D)
C is a standard code, already available on geeksforgeeks, interviewbit and maybe somewhere else too.
"the length of the maximum prefix of S that's a subsequence of our string T"
What is a maximum prefix, and what is T here?
The longest prefix. For example, if $$$T$$$ is
axbycz
and $$$S$$$ isabcdef
, the longest prefix of $$$S$$$ that's a subsequence of $$$T$$$ isabc
.$$$T$$$ is just the final string we're looking for.
what makes problem C different from decimal to base26 conversion? can you explain please? thank you
Because in the base26 the numbers are from 0 — 25 but here the count is from 1-26.
F:Strivore
"The remaining characters have Z-1 choices".
Couldn't understand this part.
In order to not increase the maximum-prefix-length, you need to not provide the appropriate next character of $$$S$$$, which is $$$Z-1$$$ choices.
Suppose S="abc", and K=2, then N=3+2=5 Now, if we are looking at say M=2, then let T be "_ a _ b _", then why the first and second blanks need to have 25 choices, since if 'a' comes at first blank or 'b' comes at second blank, then also M=2 holds.
I could not understand it too. But it seems that I understand what's the matter now. Lets consider your example S = "abc", K=2, N = 5, T = "_a_b_".
If we can put 'a' in first blank and 'b' in second it means, that we can get T = "abaxbx" 2 or more times. For example, first time from your pattern T = "_a_b_" and second time from pattern T = "ab___". So it means that you can subtract string T = "abaxbx" 2 or more times that is not correct. So maybe the solution means that you should fix FIRST ENTRANCE OF PREFIX "ab" in T. So if in pattern T = "_ a _ b _" it is the first entrance of "ab", so you SHOULD NOT put 'a' in first blank and 'b' in second blank and 'c' in third. This way we consider one string only one time, so we subtract only unique strings T, and all this strings T do not contain S as subseq, that is correct. So it is the explanation why it is only 25 choice in each blank. Hope I explained my thoughts correctly.
Thank you so much! I got your point, it was really helpful. So, that means the case I was saying of T="aabb_" has already been counted when we chose positions first and third, so we need not consider it while chosing the positions 2nd and 4th, i.e. when we chose T="a_b__", then we are allowing "a" at first blank but not "b", and we are allowing "b" at second blank but not "c". So, yeah we should be considering only first occurrence to prevent counting the same sequence multiple times.
Yes, that's right.
If your "template" is
??a???b??
and $$$S$$$ =abcdef
, the first two blanks can be anything except "a", the middle 3 blanks can be anything except "b", and the last ones can be anything except "c".For example, if you had the string
axaxxxbcx
then that would actually correspond to a different template:a?????bc?
(where the first block of question marks can be anything except "b" and the second block can be anything except "d").Same doubt !
The explanation above by @BigPolandBro seems very helpful, it may help you as well!
not all heroes wear capes, thanks for the quick and detailed editorial! keep it coming!
My Atcoder rating is back below 2000, so I guess I will be doing more ABCs!
Your color edited T-shirt at atcoder is also quite cool.
Ah shoot, I should update it to blue to match my rating. :)
I didn't bother to change it to blue after yesterday's AGC because I thought maybe I'd just go back to yellow after today's ABC.
Solution for F is cool. Thank you for writing the editorial.
Thanks! Always happy to meet a fan. :)
Very brief explanations, also thanks for explaining problem C it was quite interesting.
ur solution for F is correct but i am not able to understand why it is correct. in my opinion when we select M position in T then at at some position we can put 26 letter but at other we can only 25 i.e Z-1 but you took Z-1 at all the remaining places why that is working
can someone elaborate on why N = N-1 is needed for C? Still don't quite understand how that will skip the shorter strings...an edge case example of this concept would also be very helpful. Thank you and much appreciated in advance!
Try tracing through it, it will be instructive. You can also read about standard algorithm to convert between bases (for example, learn how to convert between base 7 and base 10 by hand & by writing code). I think understanding that on your own will help explain more than other people writing more about this problem.
thank you! Had some trouble with the indexing at first, but think I got it down pat now. Thanks again for great post!
Happy to hear it!
Helps a lot, thanks so much.
Thanks a lot for your effort. But I can't understand the subtraction of 1 in each calculation in Problem C. Why do we do that ? The rest is ok, but I can't get through that.
Probably it is work for the casework of 'Z', is it?
Not necessarily if you see we are adding
n%26
to'a'
so when n=1 the answer should be 'a' and not 'b' hence we need to subtract one from n in each iteration. You can refer to this Video Editorial if you like .AnandOza Why my this idea for F would not work .
In the first example $$$k = 5$$$ and $$$S = off$$$ . Now if we want to add $$$1$$$ character then there are $$$4$$$ options . and we can add that $$$1$$$ character in $$$26*4$$$ ways and the length of string becomes $$$4$$$ now . and for another character there are $$$5$$$ options and we can add them in $$$26*5$$$ ways and so on ..
Try it with $$$S =$$$ "a" and $$$k=1$$$.
Got it . Thanks . Here is what I understood . We have two options to put a new character
1. $$$*a$$$
2. $$$a*$$$
if we are going to put the new character in the first option then we'll get string like this $$$aa , ba , ca , da .... za$$$ .
Now if we are going to put the new character in the second option then we'll get string like this $$$aa , ab , ac , ad .... az$$$ .
We can clearly see the problem with this idea is we are counting $$$aa$$$ twice .
Feel free to explain what you learned for anyone else who reads this thread and has the same question!
Updated :)
atcoder beginner contest is like div3 in code forces ?
div 2.2 in my opinion. A is much simpler than div2 A, but usually H is harder than div2 F.