153 - Permalex

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

killerwife
New poster
Posts: 11
Joined: Tue Jan 28, 2014 2:16 am

Re: 153

Post by killerwife » Mon Jun 30, 2014 12:26 pm

I am getting WA for unknown reasons.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int combinations(int size,int letterCounters[30])
{
    int i;
    int max=-1;
    long long numerator=1;
    long long denominator=1;
    long long factorials[20];
    factorials[0]=1;
    for(i=1;i<20;i++)
    {
        denominator*=i;
        factorials[i]=denominator;
    }
    denominator=1;
    for(i=0;i<30;i++)
    {
        if(letterCounters[i]>max)
        {
            max=letterCounters[i];
        }
    }
    for(i=size;i>max;i--)
    {
        numerator*=i;
    }
    for(i=0;i<30;i++)
    {
        if(letterCounters[i]!=0)
        {
            if(letterCounters[i]==max)
            {
                max=-1;
                i++;
            }
            else
            {
                numerator/=factorials[letterCounters[i]];
            }
        }
    }
    return (int) numerator;
}

int permsUpTo(char word[32],int size,int letterCounters[30])
{
    int i=0;
    int result=0;
    char temp[32];
    while(i+'a'<word[0])
    {
        if(letterCounters[i]!=0)
        {
            letterCounters[i]--;
            result+=combinations(size-1,letterCounters);
            letterCounters[i]++;
        }
        i++;
    }
    letterCounters[i]--;
    for(i=1;i<size;i++)
    {
        temp[i-1]=word[i];
    }
    if(size-1>0)
    {result+=permsUpTo(temp,size-1,letterCounters);}
    return result;
}

int main()
{
    char input[32];
    int size=0;
    fgets(input,32,stdin);
    do
    {
        int i;
        int letterCounters[30];
        size=0;
        for(i=0;input[i]!='\0';i++)
        {
            if(input[i]!=' ')
            {
                size++;
            }
        }
        size-=1;
        for(i=0;i<30;i++)
        {
            letterCounters[i]=0;
        }
        for(i=0;i<size;i++)
        {
            letterCounters[input[i]-'a']++;
        }
        i=permsUpTo(input,size,letterCounters);
        if(size>0)
        {printf("%10d\n",i+1);}
        fgets(input,31,stdin);
    }
    while(input[0]!='#');
    return 0;
}

I am using the posted Nikolay Archak algorithm, but i have no clue why wa.

killerwife
New poster
Posts: 11
Joined: Tue Jan 28, 2014 2:16 am

Re: 153

Post by killerwife » Mon Jun 30, 2014 12:38 pm

Got ac, my optimized combination number calculation was skipping over one additional lettertype when i encountered the one i should skip over.(30!/15!=30*29...*16, and i did this, but if it was A, i would skip over Bs bcs of one mistakenly placed iteration.)

alexiago
New poster
Posts: 14
Joined: Thu Jan 24, 2008 6:34 pm

Re: 153 - Permalex

Post by alexiago » Fri Oct 02, 2015 9:00 pm

I have tested every input I found for this problem but I'm still getting WA. Anyone has any idea what's wrong?

Code: Select all

Removed after ACC
I was computing a straight factorial and I figured the problem requires a little tuning to avoid an overflow.

Post Reply

Return to “Volume 1 (100-199)”