110 - Meta-Loopless Sorts

[coldfire]

Hello, what is the correct tabbing for the sort program ? The only information we have is that "writeln" should be on a line by itself.

I get WA with the following answer for 3.

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
writeln(b,a,c)
else
if b < c then
writeln(b,c,a)
else
writeln(c,b,a)
end.

[coldfire]

Now i get Presentation Error. Any ideas ?

[rk]

kindly give me test cases that give WA in 110.

code is

Code: Select all

# include <iostream.h>
# include <string.h>
void sort(char *X,char *Y,int t);
int main()
	{int n2,a,n,d;char b,c[9],e;
	 cin>>n2;
	 for(a=1;a<=n2;a++)
		{cin>>n;
		 cout<<"\nprogram sort(input,output);\nvar\na";
		 for(b='b';b<'a'+n;b++)
			cout<<","<<b;
		 cout<<" : integer;\nbegin\n  readln(a";
		 for(b='b';b<'a'+n;b++)
			cout<<","<<b;
		 cout<<");\n";
		 for(b=1;b<n;b++)
			c[b-1]='a'+b;
		 c[b-1]='\0';
		 for(d=0;d<(b-1)/2;d++) {e=c[d];c[d]=c[b-2-d];c[b-2-d]=e;}
		 sort("a",c,1);cout<<"end.\n";
		}
	 return 0;
	}
void sort(char *X,char *Y,int n)
	{int a,b;char Z[9],c[9];
	 if(Y[0]=='\0')
		{for(a=1;a<n+1;a++) cout<<"  ";
		 cout<<"writeln("<<X[0];
		 for(a=1;X[a]!='\0';a++)
			cout<<","<<X[a];
		 cout<<")\n";
		}
	 else
		{for(a=strlen(X);a>=0;a--)
			{for(b=1;b<=n;b++) cout<<"  ";
			 if(a==strlen(X)) cout<<"if "<<X[a-1]<<" < "<<Y[strlen(Y)-1]<<" then";
			 else if(a==0) cout<<"else";
			 else cout<<"else if "<<X[a-1]<<" < "<<Y[strlen(Y-1)]<<" then";
			 for(b=0;b<a;b++) Z[b]=X[b];
			 Z[b]=Y[strlen(Y)-1];strcpy(c,Y);c[strlen(c)-1]='\0';
			 for(b=b+1;X[b-1]!='\0';b++) Z[b]=X[b-1];
			 Z[b]='\0';cout<<"\n";
			 sort(Z,c,n+1);
			}
		}
	}

[LithiumDex]

Well, since each n is in the range 1 <= n <= 8, then you could make the dataset:

Code: Select all

8

1
2
3
4
5
6
7
8

redirect console output too a file, and then check each one manually for errors (shouldn't be hard)... I havn't read your code, but my suspision (if not some sort of presentation error), is that your code might not work properly for even n's

side note though, this problem looks like fun, I'm going to try to solve it, and i'll post my code when I do.

[EDIT] Special case for 1?
"No redundant comparisons of integer variables should be made. ..."

[shaform]

10/13 Updated:
Well......
My program prints " writeln(a,b,c); ", and it should be " writeln(a,b,c) ".
Why didn't I find it?

-----------------------------------------------------
There must be some stupid mistakes in my code, but I can't find it.
Can anyone tell me what's wrong with my code?
Thanks for your help.

Code: Select all

removed after accepted

[fpavetic]

can someone please confirm that these are correct outputs for 1,2, 3 and 4. i constantly get output limit exceeded. and if i get rid of indentation, i get wa

Code: Select all

program sort(input,output);
var
a : integer;
begin
  readln(a);
  writeln(a)
end.

program sort(input,output);
var
a,b : integer;
begin
  readln(a,b);
  if a < b then
    writeln(a,b)
  else
    writeln(b,a)
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
      writeln(b,a,c)
    else
      if b < c then
        writeln(b,c,a)
      else
        writeln(c,b,a)
end.

program sort(input,output);
var
a,b,c,d : integer;
begin
  readln(a,b,c,d);
  if a < b then
    if a < c then
      if a < d then
        if b < c then
          if b < d then
            if c < d then
              writeln(a,b,c,d)
            else
              writeln(a,b,d,c)
          else
            writeln(a,d,b,c)
        else
          if b < d then
            writeln(a,c,b,d)
          else
            if c < d then
              writeln(a,c,d,b)
            else
              writeln(a,d,c,b)
      else
        if b < c then
          writeln(d,a,b,c)
        else
          writeln(d,a,c,b)
    else
      if a < d then
        if b < c then
        else
          if b < d then
            writeln(c,a,b,d)
          else
            writeln(c,a,d,b)
      else
        if b < c then
        else
          if b < d then
          else
            if c < d then
              writeln(c,d,a,b)
            else
              writeln(d,c,a,b)
  else
    if a < c then
      if a < d then
        if b < c then
          if b < d then
            if c < d then
              writeln(b,a,c,d)
            else
              writeln(b,a,d,c)
      else
        if b < c then
          if b < d then
            writeln(b,d,a,c)
          else
            writeln(d,b,a,c)
    else
      if a < d then
        if b < c then
          writeln(b,c,a,d)
        else
          writeln(c,b,a,d)
      else
        if b < c then
          if b < d then
            if c < d then
              writeln(b,c,d,a)
            else
              writeln(b,d,c,a)
          else
            writeln(d,b,c,a)
        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.

[Darko]

I don't know if this will help at all, but here's my output:

Code: Select all

program sort(input,output);
var
a : integer;
begin
  readln(a);
  writeln(a)
end.

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

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.

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.

[fpavetic]

thank you. i rewrote my solution and i found that a correct solution should contain exactly n!-1 comparisons

[Vexorian]

Hello, I am getting TLE in the 110 problem, which is odd nonetheless since this is how my algorithm works:
- generate solutions for 1->8 cases and store in array
- for each input output value in array,

The solution generation takes 1 second in my computer, so it is quite unbelievable to think it is taking 10 seconds in the online judge... so should I guess the judge is actually running the program multiple times? That sounds odd since there already is a way in the i/o specs to do multiple test cases...

my computer is 4 years old so I don't think that it would outperform the judge so hard...

[Jan]

I dont think so. Could you PM me the code.

[Vexorian]

I think my method that involved stringstreams and std::strings was too much overhead for the extended amounts of things to do, I changed it to use C strings and it no longer times out, it gives WA but that's something I'll have to deal with.

[sohel]

I faced a similar problem with stringstream recently. It was with the problem 'Australian Voting'. I thought the reason for TLE was due to the high complexity of my algorithm. But, later, commenting out the main part and submitting with just reading the input resulted in TLE as well.

Switching to strtok() brought down the time significantly and the code got AC in about 5 seconds.

[fanglon]

I recently got my code accepted, but it gives me a Presentation Error and I just can't see what is wrong with the output. I was hoping that somebody could look at the code and find the error. I do not output a empty line after the last program, so that can't be the problem.

Code: Select all

//110 - Meta - Loopless Sorts
#include <iostream>
#include <vector>
#include <fstream>
#include <cctype>

using namespace std;

//#define DEBUG

//the recursive function that outputs the ifs
void ifer(string finished, string unchecked, string reminder, bool after)
{
	
#ifdef DEBUG
	//cout <<"## "<<finished.c_str()<<" | "<<unchecked.c_str()<<" | "<<reminder.c_str()<<" ##"<<endl;
#endif

	//--if nothing is left to check, then write answer and end
	if( unchecked.empty() )
	{
		
		finished.append(reminder);

		cout<<endl;

		for(int a = 0 ; a < finished.size() ; a++) cout<<"  ";

		cout<<"writeln(";
		for(int a = 0 ; a < finished.size() ; a++)
		{
			if(a != 0)cout<<",";
			cout<<finished[a];
		}
		cout<<")";
	}
	else // else continue
	{
		//if the finished is empty
		if( finished.empty() )
		{
			finished += unchecked[0];
			finished.append( reminder );
			
			reminder.clear();
			unchecked.erase(0,1);

			ifer(finished, unchecked, reminder, false);
		}
		else
		{
			if(after)
			{
				cout<<" if ";
			}
			else 
			{
				cout<<endl;
				for(int a = 0 ; a < finished.size() + reminder.size() ; a++) cout<<"  ";	
				cout<<"if ";
			}
			
			cout<<finished[ finished.size() - 1 ]<<" < "<<unchecked[0]<<" then";

			string copy = unchecked;
			copy.erase(0, 1);
			string a,b,c;

			a = finished;
			a += unchecked[0];
			a += reminder;
			b = copy;
			//c = "";
			ifer( a, b, "", false);

			cout<<endl;
			for(int a = 0 ; a < finished.size() + reminder.size() ; a++) cout<<"  ";
			cout<<"else";

			string copy2 = finished;
			copy2.erase(copy2.size() - 1);

			a = copy2;
			b = unchecked;
			c = finished[ finished.size() - 1 ];
			c += reminder;

			ifer(a, b, c, true);
		}
	}
}
int main()
{
	int programs;	//the amount of programs to make
	int variables;

	cin >> programs;

	for(int a = 0 ; a < programs ; a++)
	{
		//read the amount of variables
		cin >> variables;

		if(a != 0)cout<<endl<<endl;

		//output the program
		cout<<"program sort(input,output);"<<endl;
		cout<<"var"<<endl;
		for(int b = 0 ; b < variables ; b++)
		{
			if(b != 0)cout<<",";
			cout<< char('a' + b);
		}
		cout<<" : integer;"<<endl;
		cout<<"begin"<<endl;
		cout<<"  readln(";
		for(int b = 0 ; b < variables ; b++)
		{
			if(b != 0)cout<<",";
			cout<< char('a' + b);
		}
		cout<<");";
			

		string reminder;
		for(int b = 1 ; b < variables ; b++) 
		{
			reminder += char('a' + b);
		}

		ifer("a",reminder,"",false);
		
		cout<<endl<<"end.";
	}
	#ifdef DEBUG
	system("pause");
	#endif
	return 0;
}

[GRAJAM]

Hi, change this line

cout<<endl<<"end.";
for
cout<<endl<<"end."<<endl;

and
if(a != 0)cout<<endl<<endl;
for
if(a != 0)cout<<endl;

[fanglon]

Thank you for the help, it worked.