Cranium 2013 'The lost number'

general
, , ,
1

I tested my code fr several inputs like
592 593 0 59 592 7
n I’m getting right answer fr these…can someone who solved the problem tell me wt’s wrong with my code ? ?

Problem - http://www.codechef.com/CRNM2013/problems/CRNM1301

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

bool myfun(string x, string y)
{
    for(int i=0;i<x.length()&&i<y.length();i++)
    {
        if(x[i]==y[i])
        continue;
        else
        return(x[i]>y[i]);
    }
    if(x.length()<y.length())
    return(1);
    else
    return(0);
}

int main()
{
    int T,N;
    string s[100];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            cin>>s[i];
            //cout<<"s[i]"<<s[i]<<endl;
        }
        sort(s,s+N,myfun);
        //sort(v.begin(),v.end(),std::greater<long long int>());
        for(int i=0;i<N;i++)
        cout<<s[i];
        printf("\n");      
    }
    return 0;
}
2

did you try cases like:

2 & 21 (ans= 221)
56 & 561 (ans=56561)

1 Like
3

The correct solution is to sort strings using comparator

bool cmp(string a, string b) {
    return a+b > b+a;
}

Here a+b is the concatenation of strings. The intuitive proof: if we put numbers in some order and a and b some two consecutive strings in the list then if a+b < b+a it is advantageous to swap them. Indeed, if we swap them we exactly change substring a+b by b+a in the result.

But to get a complete proof one should prove that cmp is indeed the correct ordering. In particular one should prove transitivity property:

If a+b > b+a and b+c > c+b then a+c > c+a

Several years ago I spent several hours for this and wrote several pages of calculations to prove this :slight_smile:

As @vidhant noted the trickiest cases are when some strings are prefixes of other strings.

It is possible to create even trickier test:

3 31 314

The optimal answer is 331431. So we take the shortest string then the largest and then the middle one.

5 Likes
4

@Vidhant yes I did !

n I gt my missing case in a lecture today :stuck_out_tongue:
56 569 should be 56956 n 56569…so I had to compare larger string’s next digit with the short one’s 1st digit…missed that one…

@anton_lunyov thnxxx that’s probably the best solution…

5

Some test cases for the problem and their correct answers. You can check your answers against these.

8
2
5555 55557
2
3649908 364990
2
875897986678 875897986678333
3
67793 6779388111 6779323999
2
5555 555555555599
2
5555 555555555512
3
7866456786645612 7866456 786645679
3
4348 434843 48

555575555
3649908364990
875897986678875897986678333
6779388111677936779323999
5555555555995555
5555555555555512
78664567978664567866456786645612
484348434843
6

// Hi try this code…
#include
#include
#include
#include
using namespace std;
int mycompare(string x, string y)
{
string xy = x.append(y);
string yx = y.append(x);
return xy.compare(yx) > 0 ? 1 : 0;
}
int main()
{
int t,n,num,i;
string s;
cin>>t;
while(t–)
{
cin>>n;
vector myvector;
for(i=0;i<n;i++)
{
cin>>num;
ostringstream convert;
convert<<num;
s=convert.str();
myvector.push_back(s);
}
sort(myvector.begin(),myvector.end(),mycompare);
for(i=0;i<n;i++)
cout<<myvector[i];
cout<<endl;
}
return 0;
}