Official

C - abc285_brutmhyhiizp Editorial by en_translator


First of all, notice that there are \(26^k\) IDs of length \(k\).
Also, there are \((26^1+26^2+\dots+26^k)\) IDs of length at most \(k\).

Now, let us find the index of the problem whose ID is a \(l\)-letter string \(S\).
In fact, it can be found as follows.

Initialize the answer with \(26^1 + 26^2 + \dots + 26^{l-1}\).

  • Repeat the following for each \(i = 1,2,\dots,l\):
    • add \((x-1) \times 26^{l-i}\) to the answer, if the \(i\)-th character of \(S\) is the \(x\)-th letter in the alphabet.

Print \(1\) to the answer and print it. (It shifts the \(0\)-based indexing to \(1\)-based.)


This solution can be interpreted in several ways.
For example, when the ID is QWERTY, we can find the answer as follows.

Counting successively
  • There are \((26^1 + 26^2 + \dots + 26^5)\) IDs of length at most \(5\).
  • There are \(26^5\) IDs A????? of length \(6\) starting with A.
  • There are \(26^5\) IDs B????? of length \(6\) starting with B.
  • \(\vdots\)
  • There are \(26^5\) IDs P????? of length \(6\) starting with P.
  • There are \(26^4\) IDs QA???? of length \(6\) starting with QA.
  • There are \(26^4\) IDs QB???? of length \(6\) starting with QB.
  • \(\vdots\)
  • There are \(26^3\) IDs QWA??? of length \(6\) starting with QWA.
  • \(\vdots\)
  • There are \(26^2\) IDs QWEA?? of length \(6\) starting with QWEA.
  • \(\vdots\)
  • There are \(26^1\) IDs QWERA? of length \(6\) starting with QWERA.
  • \(\vdots\)
  • There are \(26^0\) IDs QWERTA of length \(6\) starting with QWERTA.
  • \(\vdots\)
Interpret it as base-\(26\) number
  • There are \((26^1 + 26^2 + \dots + 26^5)\) IDs of length at most \(5\).

So far so good. Now let us interpret QWERTY as a base-\(26\) number. If we correspond AAAAAA to \(0\), AAAAAB to \(1\), \(\dots\), AAAAAZ to \(25\), AAAABA to \(26\), \(\dots\), we can treat the string just like a base-\(26\) integer by corresponding each uppercase English letter to \(0,1,\dots,25\). Thus, regard the input as a base-\(26\) number and reconstruct it to a decimal.


Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  string s;
  cin >> s;
  int l=s.size();
  long long res=0,add=26;
  for(int i=1;i<=l-1;i++){res+=add;add*=26;}
  long long num=0;
  for(int i=0;i<l;i++){
    num*=26;
    num+=(s[i]-'A');
  }
  cout << res+num+1 << "\n";
  return 0;
}

posted:
last update: