[C/C++] BOJ #1036 - Base 36

The problem “Baekjoon #1036 - Base 36” requires converting and maximizing a numerical value in base 36.

In base 36, the digits range from 0-9 and A-Z, where ‘A’ represents 10, ‘B’ represents 11, …, and ‘Z’ represents 35. The input consists of several numbers written in base 36, and the task is to maximize the sum of these numbers by replacing at most one character (‘0’-‘Z’) with ‘Z’ (35) in all occurrences within the given numbers.

To solve this, you must first compute the original sum of all given numbers in base 36. Then, analyze how much each digit (‘0’-‘Y’) would contribute to increasing the sum if it were globally replaced with ‘Z’. The goal is to pick the most beneficial replacement that leads to the highest possible sum. Finally, convert the resulting sum back into base 36 and output it.

This problem requires efficient handling of base conversions, sorting based on impact, and maximizing the value using a single character substitution.

 

---

This problem is quite challenging. As of today’s date, 143 people have solved it, and the correct answer rate is 16.7%. I also got a wrong answer (WA) once.

Of course, if you break it down, it doesn’t involve a particularly complex algorithm. It’s one of those problems where, after solving it, you realize the approach was obvious, yet it’s easy to make mistakes.

Base 36 consists of numbers from 0 to 9 and letters from A to Z. While it’s not a numeral system commonly used in practice, Python actually supports base 36 conversions, so solving this problem in Python might make it easier.

 

This problem requires considering sorting, string processing, and handling large numbers.

The problem statement is as follows:
You are given N base-36 strings, and you can replace K digits (0-9, A-Z) with ‘Z’ to maximize the total sum. The task is to output the maximum possible sum in base-36.

My Algorithm Approach:
1. Create an array to store the base-36 values for each digit and initialize it with zeros.
2. Read the N base-36 strings as input.
3. For each digit in each string, update the array to track how many times each digit appears at each position.
4. Calculate the impact of converting each digit ‘c’ to ‘Z’ using the formula:

\[ (\text{Current value of c in base-36}) \times (\text{frequency}) - (\text{value of Z} \times \text{frequency}) \]

This gives the increase in value when replacing c with Z.
5. Sort the digits in descending order based on this impact value.
• Since we only need the top K replacements, we don’t need a full sort.
• A selection sort could work, but since K can be as large as 36, a faster sorting algorithm would be better.
6. Replace the top K digits with ‘Z’ in all occurrences.
7. Compute the final sum in base-36 and output it.

Considerations:
• Handling base-36 arithmetic properly was a bit tricky.
• Using a char[] array to store values was useful.
• The maximum length of a number is 50, and there can be 50 numbers,cso the maximum possible sum length is around 52

\[35 \times 50 < 36 \times 36 \times 36\]

which ensures we stay within safe bounds.

This approach ensures efficient computation while handling large numbers and base conversions properly.

 

I will share the answers I obtained for some test inputs.

5
0
0
0
0
0
0
---------------
0

10
ASDFJH
ADSFKAF
DSJFFD
23JH4
2J4H32 
23JH   
LK65
L6KN3
LKN22
LKN 
7
---------------
132ZAQA5

4
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJKLM
QWQWQWFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
1234567890ZZZZZZZZZZZZZZZZZZZZ
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ567890
2
---------------
1ZZD4B6D8EZ012345678ACEGIKLNPIIJKLMNPFERSTUV2468A0

 

Here is the code I wrote. I wanted to make it simpler and more intuitive, but implementing base-36 arithmetic turned out to be quite tedious.

If I had written it in Python, which supports large numbers and base-36 conversion, the code would have been much more concise.

---

base conversion

Please consider this code as a reference only.

//----------------------------------------------------------
//    baekjoon #1036 - Base 36
//        - by Aubrey Choi
//        - created at 2019-12-26
//----------------------------------------------------------
#include <stdio.h>
#include <algorithm>

struct Base36 { int c, d[52]; } base[36], r;
void Mul(Base36 &r, const Base36 &a, int m)
{
    for(int i=0,c=0;i<52;i++)
    {
        r.d[i]=a.d[i]*m+c;
        c=r.d[i]/36; r.d[i]%=36;
    }
}
bool cmp(int a, int b)
{
    Base36 ta, tb;
    Mul(ta, base[a], 35-base[a].c);
    Mul(tb, base[b], 35-base[b].c);
    for(int i=51;i>=0;i--)
    {
        if(ta.d[i]>tb.d[i]) return true;
        if(ta.d[i]<tb.d[i]) return false;
    }
    return false;
}
int main()
{
    int i, j, n, k, t, c, idx[36];
    for(i=0;i<36;i++) base[i].c=i, idx[i]=i;
    scanf("%d",&n);
    while(n--)
    {
        char s[56];
        scanf("%s",s);
        for(k=0;s[k];k++) s[k]=(s[k]<'A')?s[k]-'0':s[k]-'A'+10;
        for(t=0,i=k-1;i>=0;i--,t++) base[s[i]].d[t]++;
    }
    std::sort(idx,idx+35,cmp);
    scanf("%d",&k);
    for(i=0;i<k;i++) base[idx[i]].c=35;
    for(i=0,c=0;i<52;i++)
    {
        for(j=0,t=c;j<36;j++) t+=base[j].c*base[j].d[i];
        r.d[i]=t%36; c=t/36;
    }
    for(i=51,t=0;i>=0;i--)
    {
        if(t||r.d[i]||!i) putchar(r.d[i]<10?r.d[i]+'0':r.d[i]+'A'-10),t=1;
    }
    putchar('\n');
}