## 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

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:
Plz do have a look at my code. I cant figure out the bug !

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int N,index;
char bank[55][100],temp[100];
int compare (int a, int b)
{
int i,j,len1,len2,len;
len1=strlen(bank[a]);
len2=strlen(bank[b]);
if(len1>len2)
len=len2;
else
len=len1;

for(i=0;i<len;i++)
{
if(bank[a][i]>bank[b][i]) // return 0 if a is greater
return 0;
else if(bank[a][i]<bank[b][i]) // return 1 if b is greater
return 1;
}
if(abs(len1-len2)==1) // X and XXXXy consideration
{
if(len1>len2)
{
if(bank[a][len1-1]<=bank[b][0])
return 1;
else
return 0;
}
else if(len2>len1)
{
if(bank[b][len2-1]<=bank[a][0])
return 0;
else
return 1;
}
}
else          // X and XXXyz.. consideration
{
if(len2>len1)
return 0;
else
return 1;
}
}
void swap(int i, int j)
{
char dump[100];
strcpy(dump,bank[j]);
strcpy(bank[j],bank[i]);
strcpy(bank[i],dump);
}
void sort(int k)
{
int i,j,dis;
for(i=0;i<k;i++)
{
//strcpy(temp,bank[0]);
index=0;
for(j=0;j<k-i;j++)
{
dis=compare(j,index);
if(dis)
index=j;
}
swap(index,j-1);
}
}
int main()
{
int N,i,j;
while(1)
{
scanf("%d",&N);
if(N==0)
break;
for(i=0;i<N;i++)
scanf("%s",bank[i]);

sort(N);
for(i=0;i<N;i++)
printf("%s",bank[i]);
printf("\n");
}
return 0;
}
``````
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Niaz wrote:I am getting WA again and again ! I cant figure out where is actually my mistake. Would you plz give me some tricky input and output, so that I can find my fault ?
Although I read your post in another thread, I couldn't find what is your algorithm.
So, I give you critical input for your program.
And, there are also some input set in other thread.
Please check.

Code: Select all

``````2
784 78479
2
765 76576579
2
7 778
0
``````
Correct output is :

Code: Select all

``````78479784
76576579765
7787
``````
Best regards.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
ImLazy wrote:i.e. there may be two numbers which are X and XXXXXy.(X has several digits, y is one digit). So you should compare y and the first digit of X.
Although I use this method to get AC, after reading David's algorithm, I have to confess my method is really dull.
I got AC with sorting algorithm same as your explanation.
But I found an incorrect part of my sorting criteria.
Following is critical input which my old code failed.

Code: Select all

``````2
1234123412 1234
0
``````
This answer should be : 12341234123412
After fixed to correspond, I got WA...

Now, I consider the comparison of X with XXXXXY.
I think, if X has several digits and Y has also several digit,
we should check X[0]&Y[0], X[1]&Y[1], X[2]&Y[2], ... so on.
When all Y are equal to X, we seem that X is higher than XXXXXY.
Is my idea correct?

Thank you.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
tan_Yui wrote:When all Y are equal to X, we seem that X is higher than XXXXXY.
Is my idea correct?

Thank you.
No.
4321 and 4321432143.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Thank you, misof.
I'll try to check my algorithm again.

Best regards.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Finally, I could get AC again!
By the way, my old code, which cannot get the correct answer, also got AC judgement.
Of course, I know that the judge data is not perfect,
but I think it is necessary to re-judge this problem.

Thanks.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Niaz wrote:Plz do have a look at my code. I cant figure out the bug !
input:

Code: Select all

``````2
2212 221
0``````
output:

Code: Select all

``2212221``

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:
I have solved this problem. My method was the one stated by David (sorting the strings) But I am curious about the DP solution. Can anyone give some hints bout it ??
Where's the "Any" key?

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
david
223++22 > 22++223
but
22 4 223 > 223 4 22 (if '4' is placed in between 'a' and 'b'), so this is not true for arbitrarily placed pairs.

Porbably it still can be proven via adjacent swaps, but it is not obvious for me how to prove that bubble sort local maximums will yield global maximum (since bubble sort allows selecting which adjacent pair to swap, which in turn affects later comparisons).
To be the best you must become the best!

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
Who can give me some hint of the problem?
Thanks in advance!

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
david
223++22 > 22++223
but
22 4 223 > 223 4 22 (if '4' is placed in between 'a' and 'b'), so this is not true for arbitrarily placed pairs.

Porbably it still can be proven via adjacent swaps, but it is not obvious for me how to prove that bubble sort local maximums will yield global maximum (since bubble sort allows selecting which adjacent pair to swap, which in turn affects later comparisons).
I don't think this invalidates what I said before. I'll try to make myself clearer:
My point was that the relation "a R b iff a ++ b > b ++ a" is an order relation (although this is not completely obvious at first glance), so we can find an ordering, with regard to R, for a given vector of strings, and then take the concatenation. This concatenation is the only one having no "inversions", and since any ordering with inversions can be improved upon by exchanging two of the strings, it follows that it is optimal.
As for your example, we have 4 R 223 and 223 R 22, so the ordered vector would be { 4, 223, 22 } and the result 422322. Any comparison-based sorting algorithm should work here, not just bubble-sort.

So the key is that there is only ONE such ordering (well, there could be several if a++b = b++a for some strings, but the concatenation would be the same anyway), and every other concatenation can be seen not to be optimal (and clearly there exists an optimal solution).

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
david
I understand your way of proving it via "we have the only one possible answer", and then applying this property it to the original data.

What "irritates" me a little is that whenever I tried to solve some other problems this way, I always found a flaw in my decisions like A -> B, and B -> A, so A iff B, so A is true (which isn't necessarily). I see no such a contradiction here with math and strict brain, but I feel there exists one Well, that's phylosophy.

What is currently "not working" is that INVERSION states: a < a[j] when i > j (or a > a[j] if we perform descending sorting). It states 'i > j', but the flaw I have spotted in my previous post states that we have it only for 'j - i = 1'. That's why I was speaking about bubble sort, since it operates at adjacent pairs.

Well, perhaps all my worries arise from still unproven fact that R is indeed an order relation. When I thought of DP approach, I had to prove sub-problem, almost silimar to transitiveness of R you gave. I failed to do so... Can you do it please? Probbly that proof will give more light on internals of this problem.

Another thing that keeps me a little frustrated is that unique resulting string might be completely different ordering of completely different strings. Like 43434343 might be different combinations of "43, 43 and 4343". Of course, under your relation all of these are equal, but there might be some example, for which it isn't.

Perhaps, when I see the proof of R transitiveness, that hypotesis will vanish.

P.S: I don't mean that you are wrong. I've just stated places which do not let me feel "safe" when I try to feel the problem.
To be the best you must become the best!

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
As it turns out, my proof that R is transitive was wrong. I had taked it for granted that a+b > b+a implies a+c+b > b+c+a, which is false as you duly point out.
Anyway, assuming R is transitive (which seems to be harder to prove than one might think, but I think is true), the correctness of the greedy algorithm follows, do you agree? And if the result is obtainable from different orderings, it must be due to there being two strings such that a+b = b+a (since the only way for an ordering to be optimal is not to have adjacent strings such that a+b < b+a, and this determines a unique sequence if we consider two strings equivalent whenever a+b = b+a). So the optimal string is unique.

I would like to know what solution the problemsetter had in mind when posing the problem, and if someone has found an easy proof that R is transitive.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
david
Most probably - yes. I think that the proof that R is indeed transitive will solve everything, once internals of this proof are given.

Another noted thing which makes me feeling "unsafe" is that "unique resulting string means unique ordering of pieces". 123456 can be 123+456 or 12+34+56. Some playing with these might break one-to-one relation, and thus the whole proof, even given R is transitive.

Though, for the largest possible string, probably there is no such case possible. I "feel" that R transitiveness is somewhat correlated with this how-to-split trouble, that's why I seek for this proof. It appears to resolve both doubts at once.
To be the best you must become the best!

ferrizzi
New poster
Posts: 23
Joined: Thu Mar 30, 2006 5:42 pm
Location: Brazil
I solved this problem by not using string comparison. I used digit by digit comparison..
Regards,
[]'s
Andre