110 - Meta-Loopless Sorts

[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]

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]

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]

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]

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]

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]

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

[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]

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]

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]

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).

[youhas]

Thank you very much!!
I made a stupid mistake!!

[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.

[ImLazy]

I'm sorry. I have realized it is a so stupid question. Now I have got AC in this problem.

[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.