Codejam Round 1A Append Sort

help
1

Append Sort - Code Jam (codingcompetitions.withgoogle.com)

#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define lld long double

//-4%3=-1]
//.size() return unsigned int so never use i<v.size()-1 in loop
int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll T;
    cin>>T;
    for(int t=1;t<=T;t++)
    {
        int n;
        cin>>n;
        
        vector <ll> v2;
        
        for(int i=0;i<n;i++)
        {
            int num;
            cin>>num;
            //v1.push_back(to_string(num));
            v2.push_back(num);
        }
        
        int ans=0;
        
        for(int i=1;i<n;i++)
        {
            //cout<<i<<"\n";
            
            if(v2[i]>v2[i-1])
            {}
            
            else if(v2[i]==v2[i-1])
            {
                ans++;
                v2[i]*=10;
            }
            else
            {
                int val1=v2[i-1];
                val1++;
                
                int val2=v2[i],cnt=0;
                
                while(val2<=v2[i-1])
                {
                    val2*=10;
                    cnt++;
                }
                
                string s1=to_string(v2[i]);
                string s2=to_string(val1);
                int ptr=0;
                
                for(int j=0;j<s1.size();j++)
                if(s1[j]!=s2[j])
                {
                    ptr=1;
                    break;
                }
                
                if(ptr)
                {
                    v2[i]=val2;
                    ans+=cnt;
                }
                else
                {
                    v2[i]=val1;
                    ans+=s2.size()-s1.size();
                }
            }
        }
            
        
        cout<<"Case #"<<t<<": "<<ans<<"\n";
       
        // for(int i=0;i<n;i++)
        // cout<<v2[i]<<" ";
        // cout<<"\n";
    }
}

Why this is giving TLE for 2nd part ? Any TC for that?
@ssjgz

2

Dunno - you’ve got signed integer overflow for e.g.

1                                                             
2
1000000000 899900000

which is undefined behaviour, but I can’t come up with a test case where this causes an infinite loop, which is what I suspect is happening here.

1 Like
3

for these ?

ll val1=v2[i-1];
val1++;
                
ll val2=v2[i],cnt=0;
4 
                while(val2<=v2[i-1])
                {
                    val2*=10; // <-- overflow with the given test input.
                    std::cout << "val2: " << val2 << std::endl;
                    cnt++;
                }

Edit:

This is if you use:

                int val1=v2[i-1];
                val1++;
                
                int val2=v2[i],cnt=0;

as in your original code.

5

But if I declare val2 with long long then it should be fine?

#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define lld long double

//-4%3=-1]
//.size() return unsigned int so never use i<v.size()-1 in loop
int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll T;
    cin>>T;
    for(int t=1;t<=T;t++)
    {
        int n;
        cin>>n;
        
        vector <ll> v2;
        
        for(int i=0;i<n;i++)
        {
            int num;
            cin>>num;
            //v1.push_back(to_string(num));
            v2.push_back(num);
        }
        
        int ans=0;
        
        for(int i=1;i<n;i++)
        {
            //cout<<i<<"\n";
            
            if(v2[i]>v2[i-1])
            {}
            
            else if(v2[i]==v2[i-1])
            {
                ans++;
                v2[i]*=10;
            }
            else
            {
                ll val1=v2[i-1];
                val1++;
                
                ll val2=v2[i],cnt=0;
                
                while(val2<=v2[i-1])
                {
                    val2*=10;
                    cnt++;
                }
                
                string s1=to_string(v2[i]);
                string s2=to_string(val1);
                int ptr=0;
                
                for(int j=0;j<s1.size();j++)
                if(s1[j]!=s2[j])
                {
                    ptr=1;
                    break;
                }
                
                if(ptr)
                {
                    v2[i]=val2;
                    ans+=cnt;
                }
                else
                {
                    v2[i]=val1;
                    ans+=s2.size()-s1.size();
                }
            }
        }
            
        
        cout<<"Case #"<<t<<": "<<ans<<"\n";
       
        // for(int i=0;i<n;i++)
        // cout<<v2[i]<<" ";
        // cout<<"\n";
    }
}

This is also giving TLE

6

That was hard work :slight_smile:

1
50
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
2 Likes
7

Sigh - note to self - next time, instead of analysing the program and meticulously trying to come up with a testcase that exploits the flaws, just throw any old testcase at it and see what happens!

It turns out that if you just generate a random testcase with N=100 and each X_i small-ish, you have to be very unlucky not to make your solution go into an infinite loop XD

2 Likes
8

Thanks a lot :bowing_man:

1 Like