BugCrush 2 Question 6 - BUGC206 - EDITORIAL

editorial
,
1

BugCrush 2 Question 6 - BUGC206 - EDITORIAL

PROBLEM LINK

Practice
Contest

Author: codechefsrm
Editorialist : codechefsrm

DIFFICULTY

HARD

PREREQUISITES

String, Permutation, Factorial

PROBLEM

Problem Description:
Program to find the rank of a name if the permutation of characters in the name are arranged in alphabetical order.

Input:
krishna

Output:
The rank is 2710

Rules:
Bugs will be mainly logical errors, syntax errors etc. They are specific to C++ language.
Since it is a debugging contest, you will be provided with a bugged solution below the Constraints section.
Please, see that you must adhere to the problem code provided, make changes only where necessary.
Participants can copy the code and compile it using an online compiler (Eg. CodeChef IDE).
Once the bugs are eliminated from the code, the clean code should be submitted by using the “Submit” button on the top-right corner.
Participants will be penalised for changing the entire problem solution or writing their own solution, completely different from the buggy code as provided in the
problem statement as our main intention is to test the debugging abilities of the participants.

Buggy Code in C++

Please copy the following code and paste it into your compiler for debugging.

#include <bits/stdc++.h>
#include <string.h>
using namespace std;
int fact(int n)
{
            return (n <= 1) ? 1 : n * fact(n - 1);
}
 
int findSmallerInRight(char* str, int low, int high)
{
            int countRight = 0, i;
 
            for (i = low + 1; i <= high; ++i)
                        if (str[i] < str[low])
                                    ++countRight;
 
            return countRight;
}
 
int findRank(char* str)
{
            int len = strlen(str);
            int mul = fact(len);
            int rank = 1;
            int countRight;
 
            int i;
            for (i = 0; i < len; ++i) {
                        mul /= len - i;
 
                        countRight = findSmallerInRight(str, i, len - 1);
 
                        rank += countRight * mul;
            }
 
            return rank;
}
 
int main()
{
            char str[20];
              cin>>str;
            cout << findRank(str);
            return 0;
}

Solution:

#include <bits/stdc++.h>
using namespace std;
#define MAX_CHAR 256
 
int fact(int n)
{
    return (n <= 1) ? 1 : n * fact(n - 1);
}
 
void populateAndIncreaseCount(int* count, char* str)
{
    int i;
 
    for (i = 0; str[i]; ++i)
        ++count[str[i]];
 
    for (i = 1; i < MAX_CHAR; ++i)
        count[i] += count[i - 1];
}
 
 
void updatecount(int* count, char ch)
{
    int i;
    for (i = ch; i < MAX_CHAR; ++i)
        --count[i];
}
 
int findRank(char* str)
{
    int len = strlen(str);
    int mul = fact(len);
    int rank = 1, i;
    int count[MAX_CHAR] = { 0 };
    populateAndIncreaseCount(count, str);
 
    for (i = 0; i < len; ++i) {
        mul /= len - i;
        rank += count[str[i] - 1] * mul;
        updatecount(count, str[i]);
    }
 
    return rank;
}
 
int main()
{
    char str[20];
    cin>>str;
    cout << findRank(str);
    return 0;
}

EXPLANATION

a. Initialize rank = 1.

b. Traverse in the string, for every char find the characters less than it.

c. Add all possible permutations with smaller characters to the rank and return the final rank.
Do this by,

  1. Create an auxiliary count array, and store the count of smaller characters in the whole string.
  2. For every character count number of characters smaller than string[i] from string[i+1] to string[len-1]
  3. After adding it to rank.
  4. Reduce count of characters greater than string[i], by removing the current character.

d. Return the final rank.