### AnandOza's blog

By AnandOza, history, 19 months ago,

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)$.

Sample code

### 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)$.

Sample code

### 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.

Sample code

### 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.

Sample code

### 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)$.

Sample code

### 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|)$.

Sample code

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.

• +256

 » 19 months ago, # |   -13 my bad I solved question C after the contest ends and 3 questions in the contest (A, B, D)
•  » » 19 months ago, # ^ |   0 C is a standard code, already available on geeksforgeeks, interviewbit and maybe somewhere else too.
 » 19 months ago, # |   +2 "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?
•  » » 19 months ago, # ^ |   +3 The longest prefix. For example, if $T$ is axbycz and $S$ is abcdef, the longest prefix of $S$ that's a subsequence of $T$ is abc.$T$ is just the final string we're looking for.
 » 19 months ago, # |   0 what makes problem C different from decimal to base26 conversion? can you explain please? thank you
•  » » 19 months ago, # ^ |   0 Because in the base26 the numbers are from 0 — 25 but here the count is from 1-26.
 » 19 months ago, # |   +15 F:Strivore"The remaining characters have Z-1 choices".Couldn't understand this part.
•  » » 19 months ago, # ^ |   +9 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.
•  » » » 19 months ago, # ^ |   +12 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.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » » » 19 months ago, # ^ |   0 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.
•  » » » » » 19 months ago, # ^ |   0 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").
•  » » » » » » 19 months ago, # ^ |   0 I didnt get the reason,Can anyone elaborate more ?
•  » » » » 19 months ago, # ^ |   0 Same doubt !
•  » » » » » 19 months ago, # ^ |   0 The explanation above by @BigPolandBro seems very helpful, it may help you as well!
 » 19 months ago, # |   +8 not all heroes wear capes, thanks for the quick and detailed editorial! keep it coming!
•  » » 19 months ago, # ^ |   +12 My Atcoder rating is back below 2000, so I guess I will be doing more ABCs!
•  » » » 19 months ago, # ^ |   0 That's good news for us. Happy to see your approach and explanation :)
•  » » » 19 months ago, # ^ |   +1 Your color edited T-shirt at atcoder is also quite cool.
•  » » » » 19 months ago, # ^ |   +11 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.
 » 19 months ago, # |   +16 Solution for F is cool. Thank you for writing the editorial.
•  » » 19 months ago, # ^ |   +14 Thanks! Always happy to meet a fan. :)
 » 19 months ago, # |   0 Sir can you explain me Task F with example .Your's all solutions are awesome.Thanks for solutions.
 » 19 months ago, # |   0 Ah alas.....I have solved the first problem.....But I had not understand the other problems(B,C,D,E,F).....what I should do?
 » 19 months ago, # | ← Rev. 2 →   0 what do you mean by (indices where it increases) in problem F ?
 » 19 months ago, # |   +6 Very brief explanations, also thanks for explaining problem C it was quite interesting.
 » 19 months ago, # |   +3 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
 » 19 months ago, # | ← Rev. 2 →   0 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!
•  » » 19 months ago, # ^ |   +3 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.
•  » » » 19 months ago, # ^ |   +8 thank you! Had some trouble with the indexing at first, but think I got it down pat now. Thanks again for great post!
•  » » » » 19 months ago, # ^ |   0 Happy to hear it!
 » 19 months ago, # |   -8 Helps a lot, thanks so much.
 » 19 months ago, # | ← Rev. 3 →   0 what is wrong in this implementation of C long n = in.nextLong(); StringBuilder res = new StringBuilder(); while (n>0){ char c = (char) (n%26 + 96); res.append(c); n = n/26; } System.out.println(res.reverse()); as this was working on all the test cases
 » 19 months ago, # |   0 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.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Probably it is work for the casework of 'Z', is it?
•  » » » 19 months ago, # ^ |   -8 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 .
 » 19 months ago, # |   0 clever F , amazing solution
 » 19 months ago, # |   -8 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 ..
•  » » 19 months ago, # ^ |   +3 Try it with $S =$ "a" and $k=1$.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +8 Got it . Thanks . Here is what I understood . We have two options to put a new character1. $*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 .
•  » » » » 19 months ago, # ^ |   +6 Feel free to explain what you learned for anyone else who reads this thread and has the same question!
•  » » » » » 19 months ago, # ^ |   +8 Updated :)
•  » » » » 19 months ago, # ^ |   0 I tried the same thing but I tried to subtract extra cases. Turns it gets worse because if you make "aaab" and you add anything other then "a" between the a's it will split the aa into two and counting these cases seems impossible to me.