153 - Permalex

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

Postby Jan » Mon Jan 09, 2006 6:06 pm

Read the post given by Nikolay Archak in the following forum...

http://online-judge.uva.es/board/viewtopic.php?t=3422&highlight=153

If you are still facing problems, I will help you.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru
 
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

153 help....(WA)

Postby IRA » Thu Feb 16, 2006 4:17 am

I don't know why do I got WA!?
Please give me some input and output data to test my program.
Or help me to find the mistake.....Please
Thanks in advance...

Code: Select all
Acc
IRA
Learning poster
 
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Postby ImLazy » Sat Feb 25, 2006 9:34 am

Maybe you didn't deal with the empty lines.
I've just solved this problem. Try this testcase. I generated it randomly.
Input:
Code: Select all
h
ghum
aylnlfdx
ircvs
xg
bw
fnqduxwf
fozvsrtkj
r
pggxrpnr
ystmwcysy
cqpe
ikeffmzni
kkas
w
renz
ycxfxtls
ypsf
dpooef
zbcoeju
pvabo


o
ylfpbn
ljvrvip
amyehwqn
rq
mxujjloov
owuxwh
sncbxcok
fzkvatxd

lyjyhfi
jswnkkufn
xx
rzb
nmgq
oketlyhn
oa
gz

cddiute
ojwa
yz
vsc
psajlf
gubfaao
lzy
n
#

Output:
Code: Select all
         1
         2
      2367
        32
         2
         1
      4212
     15090
         1
      1947
     23846
         6
     40332
         6
         1
        13
     17903
        22
        59
      4333
        91
         1
         1
         1
       659
       833
      2046
         2
     39961
        96
     16640
     14716
         1
      1773
     17573
         1
         4
        15
     26723
         2
         1
         1
        12
        16
         1
         6
       580
      1771
         2
         1
I stay home. Don't call me out.
User avatar
ImLazy
Experienced poster
 
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Postby sds1100 » Fri Mar 03, 2006 8:30 am

kind imlazy
사실은 짱꺠 ㅋㅋ
sds1100
Learning poster
 
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

153 Permalex TLE

Postby gradientcurl » Sun Dec 10, 2006 6:13 am

hello have tried permalex. my method is to sort the initial string and permutate till a match is found (using strcmp)
any other shorter way? can't seem to figure out the trick (especially those who manage to have 0 CPU time)
Code: Select all
#include <cstdio>
#include <cstring>
#define MAXLENGTH 32
using namespace std;

bool nextPer(char a[],int length)
{
   register int index,next_min;
   char tmp;
   for(index=length-2;index>=0;index--)
      if(a[index]<a[index+1])
         break;
   if(index<0)
      return false;
   next_min=index+1;
   for(int i=index+1;i<length;i++)
      if(a[i]>a[index]&&a[i]<a[next_min])
         next_min=i;
   tmp = a[index];
   a[index] = a[next_min];
   a[next_min] = tmp;
   
   for(int i=index+1;i<length-1;i++)
   {
      next_min = i;
      for(register int j=i+1;j<length;j++)
         if(a[j]<a[next_min])
            next_min=j;
      tmp = a[i];
      a[i] = a[next_min];
      a[next_min] = tmp;
   }
   return true;
}

int main()
{
   char string[MAXLENGTH],orig[MAXLENGTH],tmp;
   int index,length;

   while(scanf("%s",string),*string!='#')
   {
      length = strlen(string);
      strcpy(orig,string);
      for(int i=0;i<length-1;i++)
      {
         index = i;
         for(int j=i+1;j<length;j++)
            if(string[j]<string[index])
               index = j;
         tmp = string[index];
         string[index] = string[i];
         string[i] = tmp;
      }
      index = 1;
      do
      {
         if(!strcmp(string,orig))
            break;
         index++;
      }while(nextPer(string,length));

      printf("%10d\n",index);
   }   
   return 0;
}
User avatar
gradientcurl
New poster
 
Posts: 16
Joined: Mon Jun 26, 2006 9:33 am

Postby Jan » Sun Dec 10, 2006 6:21 am

Search your problem first. And dont open a new thread if there is one already.
Read the post given by Nikolay Archak in the following thread...
http://online-judge.uva.es/board/viewtopic.php?t=3422&highlight=153
Ami ekhono shopno dekhi...
HomePage
Jan
Guru
 
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

Postby sabir » Thu Jun 14, 2007 8:58 am

i solve this problem by counting.my algo is follow.
get input;copy to another,sort 2nd one,then compare if 1st elements in
2nd str is smaller then 1st elements in 1st str then get rest of data from 2nd str,again sort and compare as before and did it recursevely.
i have passed all sample input in board but wrong answer.
give some critical input.

sorry for my poor english.
thnx.
sabir
New poster
 
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am

Postby nymo » Wed Jun 27, 2007 6:36 pm

Thanks Nikolay Archak ! Your explanation helps :)
regards,
nymo
nymo
Experienced poster
 
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Strange problem!!!

Postby soddy » Wed Jul 11, 2007 1:20 am

I am having a strange kind of problem...n i have no clue :roll:

if the input is
Code: Select all
xzbcoeju
aboygp
eylfp
npljvrvi


my output is correct
Code: Select all
     34573
        11
        21
      8782


but if i change the first input like this
Code: Select all
xzbcoejuvp
aboygp
eylfp
npljvrvi

then my output for last value goes wrong
Code: Select all
   3225844
        11
        21
      2930


i dont understand why....i m not using any global variable so different inputs are independent of each other

Code: Select all
Code Removed
Last edited by soddy on Wed Jan 30, 2008 7:02 pm, edited 1 time in total.
I am not selfish, I just want everything.
soddy
New poster
 
Posts: 23
Joined: Tue May 29, 2007 1:39 am

Postby mmonish » Wed Jul 11, 2007 3:29 am

>>soddy
I compile ur code on my MSVC++ compiler & test those 2 sets of input & i get the correct output;
Here u use string & vector type variable. After each test case u should clear each variable.

Hope this helps.
mmonish
Experienced poster
 
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Postby soddy » Wed Jul 11, 2007 5:23 am

i already tried clearing each variable before a new test case....but still the problem persists.....i dont think clearing variables is the problem since i am initializing new variables for every test case
n i dont know y its working fine on VC++.....i am using cygwin compiler and getting wrong n i hv also tried submitting to online judge and got WA

problem is occuring for very few test cases....i tried a set of 500 test cases and got 3 results wrong but if i try those 3 test cases individually, i am getting correct result.....and i am not using any variable wid previously stored value....dont know y is it happening :(
I am not selfish, I just want everything.
soddy
New poster
 
Posts: 23
Joined: Tue May 29, 2007 1:39 am

Got Accepted

Postby soddy » Wed Jan 30, 2008 7:05 pm

I had left the problem and after a few months i tried again and got Accepted in 0.00 time(14th rank) :D ...things change with time :wink:
I am not selfish, I just want everything.
soddy
New poster
 
Posts: 23
Joined: Tue May 29, 2007 1:39 am

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.
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5409
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

PreviousNext

Return to Volume I

Who is online

Users browsing this forum: Yahoo [Bot] and 2 guests