AnandOza's blog

By AnandOza, history, 19 months ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +256
  • Vote: I do not like it

»
19 months ago, # |
  Vote: I like it -13 Vote: I do not like it

my bad I solved question C after the contest ends and 3 questions in the contest (A, B, D)

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C is a standard code, already available on geeksforgeeks, interviewbit and maybe somewhere else too.

»
19 months ago, # |
  Vote: I like it +2 Vote: I do not like it

"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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

what makes problem C different from decimal to base26 conversion? can you explain please? thank you

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because in the base26 the numbers are from 0 — 25 but here the count is from 1-26.

»
19 months ago, # |
  Vote: I like it +15 Vote: I do not like it

F:Strivore

"The remaining characters have Z-1 choices".

Couldn't understand this part.

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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, # ^ |
        Vote: I like it +12 Vote: I do not like it

      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   Vote: I like it +1 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I didnt get the reason,Can anyone elaborate more ?

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Same doubt !

        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The explanation above by @BigPolandBro seems very helpful, it may help you as well!

»
19 months ago, # |
  Vote: I like it +8 Vote: I do not like it

not all heroes wear capes, thanks for the quick and detailed editorial! keep it coming!

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    My Atcoder rating is back below 2000, so I guess I will be doing more ABCs!

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's good news for us. Happy to see your approach and explanation :)

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Your color edited T-shirt at atcoder is also quite cool.

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        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, # |
  Vote: I like it +16 Vote: I do not like it

Solution for F is cool. Thank you for writing the editorial.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sir can you explain me Task F with example .

Your's all solutions are awesome.

Thanks for solutions.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

what do you mean by (indices where it increases) in problem F ?

»
19 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Very brief explanations, also thanks for explaining problem C it was quite interesting.

»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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, # |
  Vote: I like it -8 Vote: I do not like it

Helps a lot, thanks so much.

»
19 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    Probably it is work for the casework of 'Z', is it?

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like 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 .

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

clever F , amazing solution

»
19 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Try it with $$$S =$$$ "a" and $$$k=1$$$.

    • »
      »
      »
      19 months ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      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 .

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Feel free to explain what you learned for anyone else who reads this thread and has the same question!

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.