110 - Meta-Loopless Sorts

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

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

You're my hero :-) After your last remark it was enough to skip the first number to have my solution accepted. Actually, I still have PE, but I don't care.
Thank you very much :-)

svelasqu
New poster
Posts: 2
Joined: Mon Dec 01, 2003 4:37 pm
Contact:

110: What the h.. is wrong about this answer?

Post by svelasqu »

this is the answer i got for 5, it's fine to me but it got WA.

program sort(input,output);
var
a,b,c,d,e : integer;
begin
readln(a,b,c,d,e);
if a < b then
if b < c then
if c < d then
if d < e then
writeln(a,b,c,d,e)
else if c < e then
writeln(a,b,c,e,d)
else if b < e then
writeln(a,b,e,c,d)
else if a < e then
writeln(a,e,b,c,d)
else
writeln(e,a,b,c,d)
else if b < d then
if c < e then
writeln(a,b,d,c,e)
else if d < e then
writeln(a,b,d,e,c)
else if b < e then
writeln(a,b,e,d,c)
else if a < e then
writeln(a,e,b,d,c)
else
writeln(e,a,b,d,c)
else if a < d then
if c < e then
writeln(a,d,b,c,e)
else if b < e then
writeln(a,d,b,e,c)
else if d < e then
writeln(a,d,e,b,c)
else if a < e then
writeln(a,e,d,b,c)
else
writeln(e,a,d,b,c)
else
if c < e then
writeln(d,a,b,c,e)
else if b < e then
writeln(d,a,b,e,c)
else if a < e then
writeln(d,a,e,b,c)
else if d < e then
writeln(d,e,a,b,c)
else
writeln(e,d,a,b,c)
else if a < c then
if b < d then
if d < e then
writeln(a,c,b,d,e)
else if b < e then
writeln(a,c,b,e,d)
else if c < e then
writeln(a,c,e,b,d)
else if a < e then
writeln(a,e,c,b,d)
else
writeln(e,a,c,b,d)
else if c < d then
if b < e then
writeln(a,c,d,b,e)
else if d < e then
writeln(a,c,d,e,b)
else if c < e then
writeln(a,c,e,d,b)
else if a < e then
writeln(a,e,c,d,b)
else
writeln(e,a,c,d,b)
else if a < d then
if b < e then
writeln(a,d,c,b,e)
else if c < e then
writeln(a,d,c,e,b)
else if d < e then
writeln(a,d,e,c,b)
else if a < e then
writeln(a,e,d,c,b)
else
writeln(e,a,d,c,b)
else
if b < e then
writeln(d,a,c,b,e)
else if c < e then
writeln(d,a,c,e,b)
else if a < e then
writeln(d,a,e,c,b)
else if d < e then
writeln(d,e,a,c,b)
else
writeln(e,d,a,c,b)
else
if b < d then
if d < e then
writeln(c,a,b,d,e)
else if b < e then
writeln(c,a,b,e,d)
else if a < e then
writeln(c,a,e,b,d)
else if c < e then
writeln(c,e,a,b,d)
else
writeln(e,c,a,b,d)
else if a < d then
if b < e then
writeln(c,a,d,b,e)
else if d < e then
writeln(c,a,d,e,b)
else if a < e then
writeln(c,a,e,d,b)
else if c < e then
writeln(c,e,a,d,b)
else
writeln(e,c,a,d,b)
else if c < d then
if b < e then
writeln(c,d,a,b,e)
else if a < e then
writeln(c,d,a,e,b)
else if d < e then
writeln(c,d,e,a,b)
else if c < e then
writeln(c,e,d,a,b)
else
writeln(e,c,d,a,b)
else
if b < e then
writeln(d,c,a,b,e)
else if a < e then
writeln(d,c,a,e,b)
else if c < e then
writeln(d,c,e,a,b)
else if d < e then
writeln(d,e,c,a,b)
else
writeln(e,d,c,a,b)
else
if a < c then
if c < d then
if d < e then
writeln(b,a,c,d,e)
else if c < e then
writeln(b,a,c,e,d)
else if a < e then
writeln(b,a,e,c,d)
else if b < e then
writeln(b,e,a,c,d)
else
writeln(e,b,a,c,d)
else if a < d then
if c < e then
writeln(b,a,d,c,e)
else if d < e then
writeln(b,a,d,e,c)
else if a < e then
writeln(b,a,e,d,c)
else if b < e then
writeln(b,e,a,d,c)
else
writeln(e,b,a,d,c)
else if b < d then
if c < e then
writeln(b,d,a,c,e)
else if a < e then
writeln(b,d,a,e,c)
else if d < e then
writeln(b,d,e,a,c)
else if b < e then
writeln(b,e,d,a,c)
else
writeln(e,b,d,a,c)
else
if c < e then
writeln(d,b,a,c,e)
else if a < e then
writeln(d,b,a,e,c)
else if b < e then
writeln(d,b,e,a,c)
else if d < e then
writeln(d,e,b,a,c)
else
writeln(e,d,b,a,c)
else if b < c then
if a < d then
if d < e then
writeln(b,c,a,d,e)
else if a < e then
writeln(b,c,a,e,d)
else if c < e then
writeln(b,c,e,a,d)
else if b < e then
writeln(b,e,c,a,d)
else
writeln(e,b,c,a,d)
else if c < d then
if a < e then
writeln(b,c,d,a,e)
else if d < e then
writeln(b,c,d,e,a)
else if c < e then
writeln(b,c,e,d,a)
else if b < e then
writeln(b,e,c,d,a)
else
writeln(e,b,c,d,a)
else if b < d then
if a < e then
writeln(b,d,c,a,e)
else if c < e then
writeln(b,d,c,e,a)
else if d < e then
writeln(b,d,e,c,a)
else if b < e then
writeln(b,e,d,c,a)
else
writeln(e,b,d,c,a)
else
if a < e then
writeln(d,b,c,a,e)
else if c < e then
writeln(d,b,c,e,a)
else if b < e then
writeln(d,b,e,c,a)
else if d < e then
writeln(d,e,b,c,a)
else
writeln(e,d,b,c,a)
else
if a < d then
if d < e then
writeln(c,b,a,d,e)
else if a < e then
writeln(c,b,a,e,d)
else if b < e then
writeln(c,b,e,a,d)
else if c < e then
writeln(c,e,b,a,d)
else
writeln(e,c,b,a,d)
else if b < d then
if a < e then
writeln(c,b,d,a,e)
else if d < e then
writeln(c,b,d,e,a)
else if b < e then
writeln(c,b,e,d,a)
else if c < e then
writeln(c,e,b,d,a)
else
writeln(e,c,b,d,a)
else if c < d then
if a < e then
writeln(c,d,b,a,e)
else if b < e then
writeln(c,d,b,e,a)
else if d < e then
writeln(c,d,e,b,a)
else if c < e then
writeln(c,e,d,b,a)
else
writeln(e,c,d,b,a)
else
if a < e then
writeln(d,c,b,a,e)
else if b < e then
writeln(d,c,b,e,a)
else if c < e then
writeln(d,c,e,b,a)
else if d < e then
writeln(d,e,c,b,a)
else
writeln(e,d,c,b,a)
end.

skeeve
New poster
Posts: 6
Joined: Sun Apr 18, 2004 4:17 pm

110 (meta loopless sorts): WA

Post by skeeve »

Hi, I have tried to submit problem 110 but got WA
I have tested my program, compiled pascal outputs, tried whether they work on all permutations (and they do), I have exactly n! writeln statements in my outputted program and exactly n!-i if statements. Could anyone help me find what's wrong ?
My code tries to optimize the "decision tree" a bit and so it is compicated (and slow) but I think it should work ..

Code: Select all

/* @JUDGE_ID: <MY_ID> 110 C */

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

#define MAXV          8
#define MAXPERM   65536
#define UNDEF        -1
#define DEBUG         0

#define MIN(a,b)  (((a) < (b)) ? (a) : (b))
#define MAX(a,b)  (((a) > (b)) ? (a) : (b))

struct comp {
  int va, vb;  /* compare values */
  int poffs;   /* offset of perms in array */
  int tc, fc;  /* comparsion entries for sons */
  int tp, fp;  /* counts of "true" and "false" perms */
} comps[MAXPERM];

struct perm {
  int p[MAXV];
} perms[MAXPERM];

int V, nperms, ncomps, gap, tab, ep;

void
genperm(int depth, int *actperm, int *used)
{
  int i;

  if (depth == V) {
    for (i = 0; i < V; i++)
      perms[nperms].p[i] = actperm[i];
    nperms++;
    return ;
  }
  for (i = 0; i < V; i++)
    if (!used[i]) {
      used[i] = 1;
      actperm[depth] = i;
      genperm (depth+1, actperm, used);
      used[i] = 0;
    }
  return ;
}

void
findcomp (int offs, int permno, int *ca, int *cb)
{
  int va, vb, van, vbn, optv = 0, opta = 0, optb = 0, m;
  int i, j;

  for (va = 0; va < V; va++)
    for (vb = 0; vb < V; vb++)
      if (va != vb) {
	van = 0;
	vbn = 0;
	for (i = 0; i < permno; i++)
	  {
	    if (MAX(van, vbn) >= permno - optv)
	      goto noupdate;
	    for (j = 0; j < V; j++)
	      if (perms[offs+i].p[j] == va) {
		van++;
		break;
	      } else if (perms[offs+i].p[j] == vb) {
		vbn++;
		break;
	      }
	  }
	m = MIN(van, vbn);
	if (m > optv) {
	  optv = m;
	  opta = va;
	  optb = vb;
	}
      noupdate:
      }
  *ca = opta;
  *cb = optb;
  return ;
}

int
order (struct perm *p, int a, int b)
{
  int i;

  for (i = 0; i < V; i++)
    if (p->p[i] == a)
      return 1;
    else if (p->p[i] == b)
      return 0;
  return 0;
}

int
maketree (int offs, int permno)
{
  int ca, cb, i, j, n, p;
  struct perm actp;

  findcomp (offs, permno, &ca, &cb);
  i = 0; j = permno - 1;
  n = 0;
  while (i < j)
    {
      while (i < j && (order (&(perms[offs+i]), ca, cb)))
	i++;
      while (j > i && (! order (&(perms[offs+j]), ca, cb)))
	j--;
      if (i == j)
	break;
      actp = perms[offs+i];
      perms[offs+i] = perms[offs+j];
      perms[offs+j] = actp;
    }
  if (!order (&(perms[offs+i]), ca, cb))
    n = i;
  else
    n = i+1;
      
#if DEBUG
  if (order (&(perms[offs+n]), ca, cb) || !order (&(perms[offs+n-1]), ca, cb))
    fprintf (stderr, "N (%d) counted inproperly\n", n);
  if (n == 0 || n == permno)
    fprintf (stderr, "Redundant comparsion \n");
#endif
  comps[ncomps].va = ca;
  comps[ncomps].vb = cb;
  comps[ncomps].poffs = offs;
  comps[ncomps].tp = n;
  comps[ncomps].fp = permno - n;
  comps[ncomps].tc = -1;
  comps[ncomps].fc = -1;
  p = ncomps;
  ncomps++;
  if (n > 1)
    comps[p].tc = maketree (offs, n);
  if (permno - n > 1)
    comps[p].fc = maketree (offs + n, permno - n);

  return p;
}

void
gencomptree (void)
{
  int ap[MAXV], use[MAXV];
  int i;

  nperms = 0;
  ncomps = 0;
  for (i = 0; i < V; i++)
    use[i] = 0;
  genperm (0, ap, use);
  maketree (0, nperms);
}

void
printhead (void)
{
  int i;

  printf ("program sort(input,output);\n");
  printf ("var\n");
  for (i = 0; i < V; i++)
    printf("%c%c", 'a'+i, (i == V-1) ? ' ' : ',');
  printf (": integer;\n");
  printf ("begin\n");
  for (i = 0; i < gap; i++)
    printf (" ");
  printf ("readln(");
  for (i = 0; i < V; i++)
    printf ("%c%c", 'a'+i, (i==V-1) ? ')' : ',');
  printf(";\n");
}

void
parsetree (int cnode)
{
  int i;

  if (!ep)
    for (i = 0; i < gap; i++)
      printf (" ");
  ep = 0;
  printf ("if %c < %c then\n", comps[cnode].va+'a', comps[cnode].vb+'a');
  gap += tab;
  if (comps[cnode].tp == 1) {
    for (i = 0; i < gap; i++)
      printf (" ");
    printf ("writeln(");
    for (i = 0; i < V; i++)
      printf ("%c%c", perms[comps[cnode].poffs].p[i]+'a', (i == V-1) ? ')' : ',');
    printf ("\n");
  } else {
    parsetree (comps[cnode].tc);
  }
  gap -= tab;
  for (i = 0; i < gap; i++)
    printf (" ");
  printf ("else");

  if (comps[cnode].fp == 1) {
    gap += tab;
    printf ("\n");
    for (i = 0; i < gap; i++)
      printf (" ");
    printf ("writeln(");
    for (i = 0; i < V; i++)
      printf ("%c%c", perms[comps[cnode].poffs + comps[cnode].tp].p[i]+'a',
	      (i == V-1) ? ')' : ',');
    printf ("\n");
    gap -= tab;
  } else {
    printf (" ");
    ep = 1;
    parsetree (comps[cnode].fc);
  }

}

void
printtail (void)
{
  printf ("end.\n");
}

int
main (void)
{
  int i, j, k;

  scanf ("%d", &k);
  for (i = 0; i < k; i++)
    {
      if (i > 0)
	printf ("\n");
      scanf ("%d", &V);
      gap = 2;
      tab = 2;
      printhead ();
      if (V == 1) {
	for (j = 0; j < gap; j++)
	  printf (" ");
	printf ("writeln(a);\n");
      } else {
	gencomptree ();
	parsetree (0);
      }
      printtail ();
    }
  return EXIT_SUCCESS;
}
[/c]

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

For the input

Code: Select all

1

1

3
Your program produces:

Code: Select all

program sort(input,output);
var
a : integer;
begin
  readln(a);
  writeln(a);     { there should be no semicolon here }
end.

program sort(input,output);
var
a,b,c : integer;
begin
  readln(a,b,c);
  if a < b then
    if a < c then
      if b < c then
        writeln(a,b,c)
      else
        writeln(a,c,b)
    else
      writeln(c,a,b)
  else if a < c then   { not correct, see problem description }
    writeln(b,a,c)
  else if b < c then
    writeln(b,c,a)
  else
    writeln(c,b,a)
end.

skeeve
New poster
Posts: 6
Joined: Sun Apr 18, 2004 4:17 pm

Post by skeeve »

I have also tried submitting without semicolon after writeln in n=1 case. But what is wrong with the a < c compartion? I have read problem again and again and I don't see it.

It is not redundant (I only did a < b comparsion which failed ....) so what did you mean ?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

You should spread the else and if over two lines and use extra indentation:

Code: Select all

program sort(input,output);
var
a,b,c : integer;
begin
  readln(a,b,c);
  if a < b then
    if b < c then
      writeln(a,b,c)
    else if a < c then
      writeln(a,c,b)
    else
      writeln(c,a,b)
  else
    if a < c then
      writeln(b,a,c)
    else if b < c then
      writeln(b,c,a)
    else
      writeln(c,b,a)
end.
Look at the sample output.
Same for n>3.

skeeve
New poster
Posts: 6
Joined: Sun Apr 18, 2004 4:17 pm

Post by skeeve »

So how do I recognize whether to write "else if" on one line or else and if on separate lines ?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

I'm terribly sorry. It's been too long ago that I solved this problem and simply compared your output with mine and noticed the difference. But on further inspection of the problem description, I can't find anything that prescribes the way the output should be formatted.
Your formatting is as good as mine...
I don't see why your code gets WA, but I will look into it when I have more time.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

Here is the correct output for n = 4 (no indentation, so it gets PE):
program sort(input,output);
var
a,b,c,d : integer;
begin
readln(a,b,c,d);
if a < b then
if b < c then
if c < d then
writeln(a,b,c,d)
else if b < d then
writeln(a,b,d,c)
else if a < d then
writeln(a,d,b,c)
else
writeln(d,a,b,c)
else if a < c then
if b < d then
writeln(a,c,b,d)
else if c < d then
writeln(a,c,d,b)
else if a < d then
writeln(a,d,c,b)
else
writeln(d,a,c,b)
else
if b < d then
writeln(c,a,b,d)
else if a < d then
writeln(c,a,d,b)
else if c < d then
writeln(c,d,a,b)
else
writeln(d,c,a,b)
else
if a < c then
if c < d then
writeln(b,a,c,d)
else if a < d then
writeln(b,a,d,c)
else if b < d then
writeln(b,d,a,c)
else
writeln(d,b,a,c)
else if b < c then
if a < d then
writeln(b,c,a,d)
else if c < d then
writeln(b,c,d,a)
else if b < d then
writeln(b,d,c,a)
else
writeln(d,b,c,a)
else
if a < d then
writeln(c,b,a,d)
else if b < d then
writeln(c,b,d,a)
else if c < d then
writeln(c,d,b,a)
else
writeln(d,c,b,a)
end.
Hope this helps.

youhas
New poster
Posts: 2
Joined: Thu Oct 21, 2004 4:34 am

110 Meta Loopless Sorts WA! what wrong with my code?

Post by youhas »

I have no idea why it's still WA!
Thanks for your help!!
[c]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char var[10]={'a','b','c','d','e','f','g','h','i','j'};
char Sorted[10];
int iArrayNum;
void fnSort(int now);
void fnPrintOut();
void fnIns(int i,char now_char);
void fnRestore(int i);
int n;
int main()
{
int j,M;
scanf("%d",&M);
for(j=0;j<M;++j)
{
scanf("%d",&n);
if(j!=0)
printf("\n");
fnPrintOut();
}
return 0;
}
void fnPrintOut()
{
int i;
printf("program sort(input,output);\n");
printf("var\n");

printf("%c",var[0]);
for(i=1;i<n;++i)
printf(",%c",var);
printf(" : integer;\n");

printf("begin\n");

printf(" readln(");
printf("%c",var[0]);
for(i=1;i<n;++i)
printf(",%c",var);
printf(");\n");

iArrayNum=1;
Sorted[0]='a';
if(n==1)
printf(" writenln(a)\n");
else
fnSort(1);
printf("end.\n");
}
void fnSort(int now)
{
char szSpace[100],now_char=var[now];
int i,j;

szSpace[0]='\0';
for(i=0;i<now;++i)
strcat(szSpace," ");

for(i=now-1;i>=0;--i)
{
if(i==now-1)
printf("%sif %c < %c then\n",szSpace,Sorted,now_char);
else
printf("%selse if %c < %c then\n",szSpace,Sorted,now_char);
fnIns(i,now_char);
if(now==n-1)
{
printf("%s writeln(%c",szSpace,Sorted[0]);
for(j=1;j<iArrayNum;++j)
printf(",%c",Sorted[j]);
printf(")\n");
}
else
fnSort(now+1);
fnRestore(i);

}
printf("%selse\n",szSpace);
fnIns(-1,now_char);
if(now==n-1)
{
printf("%s writeln(%c",szSpace,Sorted[0]);
for(j=1;j<iArrayNum;++j)
printf(",%c",Sorted[j]);
printf(")\n");
}
else
fnSort(now+1);
fnRestore(-1);
}
void fnRestore(int i)
{
int j;

++i;
for(j=i;j<iArrayNum;++j)
Sorted[j]=Sorted[j+1];
--iArrayNum;
}
void fnIns(int i,char now_char)
{
int j;

++i;
for(j=iArrayNum-1;j>=i;--j)
Sorted[j+1]=Sorted[j];
Sorted=now_char;
++iArrayNum;
}
[/c]

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:

Post by Zuza »

You were this close to solving this problem... Look at your excetion check (if(n==1e)). Remove the "writenln" and replace it with the writeln, that should do the trick (I hope so). :wink:

youhas
New poster
Posts: 2
Joined: Thu Oct 21, 2004 4:34 am

Post by youhas »

Thank you very much!!
I made a stupid mistake!! :-?

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

I have a question about problem 110.

Post by ImLazy »

I know nothing about Pascal's format, so I have a question:
The sample output is:

Code: Select all

begin
  readln(a,b,c);
  if a < b then
    if b < c then
      writeln(a,b,c)
    else if a < c then
      writeln(a,c,b)
    else
      writeln(c,a,b)
  else
    if a < c then
      writeln(b,a,c)
    else if b < c then
      writeln(b,c,a)
    else
      writeln(c,b,a)
end.
Then can I write in this way?:

Code: Select all

begin
readln(a,b,c);
if a < b then
if b < c then
writeln(a,b,c)
else if a < c then
writeln(a,c,b)
else
writeln(c,a,b)
else
if a < c then
writeln(b,a,c)
else if b < c then
writeln(b,c,a)
else
writeln(c,b,a)
end.
I mean deleting the spaces at the beginning of each line. Can that be all right? please tell me. Thank you.
I stay home. Don't call me out.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

...

Post by ImLazy »

I'm sorry. I have realized it is a so stupid question. Now I have got AC in this problem.
I stay home. Don't call me out.

dnh_2005
New poster
Posts: 1
Joined: Sun Aug 07, 2005 6:53 am

Accepted

Post by dnh_2005 »

Whew. After changing everything in sight, I think the judge didn't like the empty line at the end of my output. I only changed two things since getting PE:
1)remove trailing empty line. Now empty lines only appear between programs
2) else if always appears on the same line instead of as else\nif


My program is correctly formatted and indented, but I'm not sure if this is necessary.

Post Reply

Return to “Volume 1 (100-199)”