153

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

Moderator: Board moderators

Re: 153

Postby Shafaet_du » Fri Jun 24, 2011 1:39 pm

Its easier to write the whole thing in java bigint than trying to optimize the intermediate calculation. some io:

Code: Select all
sdfretf
gggfrtttereee
dfffrrrdfdf
zzffffferrrre
aaseajwelrkjlsdj
ewrwerjwelrjwe
#


output:

Code: Select all
     1826
   1801379
      1130
    535920
1468380809
   3265624
Shafaet_du
Experienced poster
 
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh

Re: 153

Postby ChrisC » Thu Feb 02, 2012 7:58 am

I am currently working on permalex 153 and my c++ code is being rejected for being "wrong/incorrect"
my current guess is that I am not accounting for some fringe cases
I tried most of the strings given in the forum and got correct results

Code: Select all
using namespace std;
#include <iostream>
#include <stdlib.h>
#include <string>
#include <new>
#include <algorithm>
#include <iomanip>

/*
currently suffering the dreaded wrong output
-I know it works for arrays of length 1-5 (regardless of character values)
-I have looked on the help board and tried other peoples input and I have gotten identical output
-I am assuming either I am messing up the output or messing up some fringe cases
*/

int permutations(string);

//finds the permutations of a sorted string (does not double count)
int permutations(string list)
{
   int length=list.length();
   long int sum =1;
   if (length==0)
      return(0);
   if (length == 1)
      return(sum);

   for(int counter=2; counter<=length;counter++)
   {
      sum=sum*counter;
   }
   
   int count=1;
   for(int j=1;j<length;j++)
   {
      if(list[j-1]==list[j])
      {

         count++;
         sum=sum/count;
      }
      else
         count=1;
      
   }
   return(sum);
   
}

//runs the program
int main()
{
   string tested;
   cin>>tested;
   string test="#";
   while( tested!=test)
   {
      int length=tested.length();
      string sorted =tested;
      sort(sorted.begin(), sorted.end());
      long int sum=1;
      
      
      for(length;length>1;length--)
      {
         int i=0;
         while(sorted[i]!=tested[0])   //test for first letter and find its place
         {
            string temp=sorted;
            temp.erase(i,1);
            sum+=permutations(temp);
            while(sorted[i]==sorted[i+1])
            {
               i++;
            }
            i++;
         }
         
         tested.erase(0,1);
         sorted.erase(i,1);
      }
      std::cout << std::right << std::setw(11) << sum << std::endl;

      cin>>tested;
   }
}



any help would be appreciated
ChrisC
New poster
 
Posts: 1
Joined: Thu Feb 02, 2012 7:47 am

Re: 153

Postby brianfry713 » Tue Feb 07, 2012 2:38 am

The width should be 10 not 11.
brianfry713
Guru
 
Posts: 3519
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 153

Postby 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

Postby 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.)
killerwife
New poster
 
Posts: 11
Joined: Tue Jan 28, 2014 2:16 am

Previous

Return to Volume I

Who is online

Users browsing this forum: No registered users and 1 guest