10905 - Children's Game

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

Moderator: Board moderators

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10905 - Children’s Game - WA

Post by DD » Mon Mar 14, 2011 4:13 am

naffi wrote:I need help.

Code: Select all

#include<iostream>

using namespace std;
char arr[9000][9000],tmp[9000];
bool comp_function(int i,int j)
{
	int il = strlen(arr[i]);		
	int jl = strlen(arr[j]);
	if(jl >= il)
	{
		for(int x = 0, y = 0; y < jl; y++, x = (++x)%il)
		{
			if(arr[i][x] > arr[j][y])return true;			
			else if(arr[i][x] < arr[j][y])return false;
		}
		return true;
	}
	else
	{
		for(int x = 0, y = 0; x < il; x++, y = (++y)%jl)
		{
			if(arr[i][x] > arr[j][y])return true;			
			else if(arr[i][x] < arr[j][y])return false;
		}
		return true;
	}
}

main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);	
	freopen("output.txt","w",stdout);
#endif
	int N,i;
	while(scanf("%d",&N) && N)
	{
		i = 0;
		while(N--)
		{
			scanf("%s",arr[i++]);			
		}
		for(int s = 1; s < i; ++s)//Bubble sort in Teach Yourself by Herb. Sch.
		{
			for(int t = i-1; t >= s; --t)
			{
				if(!comp_function(t-1,t))
				{
					strcpy(tmp,arr[t-1]);
					strcpy(arr[t-1],arr[t]);
					strcpy(arr[t],tmp);					
				}
			}
		}
		
		for(int j = 0; j < i; j++)cout<<arr[j];
		cout<<endl; 		
	}
}
I think your sorting is wrong since you should compare the two concatenations of two strings, say (a + b) and (b + a).
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 10905 - Children’s Game

Post by Imti » Tue Aug 02, 2011 5:53 pm

//Got Acc
Last edited by Imti on Fri Nov 11, 2011 7:50 pm, edited 1 time in total.

Garfield
New poster
Posts: 2
Joined: Thu Nov 03, 2011 1:54 pm

Re: 10905 - Children’s Game

Post by Garfield » Thu Nov 10, 2011 4:56 pm

Shafaet_du wrote:See the algorithm described by DAVID in 1st page,that will help you. and try this:

Code: Select all

2
1231231232 123 
0
output:

Code: Select all

1231231232123
you can use bubble sort,it wont give tle.
Got it clearly, thnx for providing help. Like you, cell phone spy software guys, work here.

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 10905 - Children’s Game

Post by Scarecrow » Mon Aug 27, 2012 11:09 pm

getting TLE. someone can help me plz?

Code: Select all

AC
Do or do not. There is no try.

Shihab
New poster
Posts: 33
Joined: Thu Jun 13, 2013 1:19 pm

Re: 10905 - Children's Game

Post by Shihab » Sun Oct 26, 2014 9:09 pm

Ac

Frez
New poster
Posts: 1
Joined: Fri Aug 05, 2016 9:36 pm

Re: 10905 - Children's Game

Post by Frez » Fri Aug 05, 2016 9:44 pm

good CMP function :

Code: Select all

bool CMP(string a,string b)
{
	return (a+b<b+a);
}
use it for sort function ! ;)

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

Re: 10905 - Children's Game

Post by mgavin2 » Thu Sep 22, 2016 6:51 pm

This problem is horribly written and doesn't include bounds on the input.

Read and process everything as strings.
The problem might talk about everything being integers, such as
In next lines there are N positive integers.
So you read and process items as int32s, then int64s...
But the problem never says the integers can't have a leading 0! LOL TRICKED YOU!

TRICKY TEST CASE:
2
01 10
0
1001
Perhaps if we keep instilling the fear of reading numbers as strings because you can't be sure that the numbers will actually be numbers even if you're told they're numbers, then every future DBA will stringize their whole database.
all that matters is AC

Post Reply

Return to “Volume 109 (10900-10999)”