< Back to forum

Taxi problem(Codeforces)

I am getting a TLE in the problem- Taxi

problem Link: https://codeforces.com/problemset/problem/158/B

Following is my code:

``` #include

using namespace std;

int main()

{ int n,c,i,j,p;

cin>>n; int car[n],g[n];

for (i=0;i<n;i++)
cin>>g[i];
sort(g,g+n, greater<int>());
c=0;
car[0]=g[0];
for (i=1;i<n;i++)
{
    p=0;
    for (j=0;j<=c;j++)
    {
        if (4-car[j]>=g[i])
        {
            car[j]+=g[i];
            p=1;
            break;
        }
    }
    if (p==0)
    {
        c++;
        car[c]=g[i];
    }       
}
cout<<c+1;
return 0;

} ``` Hope u help, Thanks!!!

Taxi Codeforces

Asked by: Anonymous on Dec. 15, 2020, 11:38 a.m. Last updated on Dec. 15, 2020, 11:47 a.m.

avatar

include

using namespace std;

int main() { int n; cin >> n;

int ele;
unordered_map<int, int> m;
for(int i = 0; i < n; i++) {
    cin >> ele;
    m[ele]++;
}

int ans = m[4];
ans += min(m[1], m[3]);
int val = min(m[1], m[3]);
m[3] -= val;
m[1] -= val;
if(m[3] > 0)
    ans += m[3];
ans += (m[2] / 2);
m[2] %= 2;
ans += m[1] / 4;
m[1] %= 4;

if(m[2] > 0 || m[1] > 0){
    if(m[2] == 1 && m[1] == 3)
        ans += 2;
    else
        ans += 1;
}
cout << ans << "\n";
return 0;

}

Another way to do it.. try it if you want..

aashuu1856 last updated on Dec. 15, 2020, 8:24 p.m.
Enter your answer details below:


Enter your comment details below:




1 Answer(s)

avatar

The reason behind TLE is, that you are iterating over every previous car, (even if that car is already filled). But what I think is, you have missed a crucial point.

The car has a maximum capacity of 4. You want every car(if possible) to be completely filled, in order to use minimum cars. Take an example, you have 3 person, already in the car, so, you need just 1 more person. And, if you have 2 person in the car, you either need 2 more person (in a single group), or 2 groups of single person each.

So, what if you had the count of, "what is the number of groups with x students in it". Here 1<=x<=4. You can easily manipulate this data, to "pair up" groups of x students with groups of 4-x students to make a car seating.

Try to think on this approach now, and ask again, if there is a query. 😃

mahawarvishal10 last updated on Dec. 15, 2020, noon 2    Reply    Upvote   
avatar

Yaa, I did similar.

Supposing G1-(1 member team), G2-(2 member team), G3-(3 member team), G4-(4 member team).

Now I seated each G4 group in separate cars (max. capacity is 4). Each G3 group in separate cars for the time being. Then 2 different G2 teams where seated together in a car. Now the G1 members were seated with G3 member's car having vacancy 1, with G2 member's car (if they have vacant capacity 2) and the rest G1 teams if any amongst themselves.

Its my code:

include

using namespace std;

int main()

{

long long int n,c1,c2,c3,c4,g,car,i;
cin>>n;
c1=c2=c3=c4=0;
for (i=0;i<n;i++)
{
    cin>>g;
    if (g==1)
    c1++;
    else if (g==2)
    c2++;
    else if (g==3)
    c3++;
    else if (g==4)
    c4++;
}   
car=c4+c3+(c2/2)+(c2%2);
c1=c1-c3;
if (c1>0 && c2%2==1)
{
    c1=c1-2;
}
if (c1>0)
{
    if (c1%4==0)
    c1=c1/4;
    else c1=(c1/4)+1;
}
if (c1<0)
c1=0;
car+=c1;
cout<<car;
return 0;

}

Thanks for the suggestion!!!

akshaydgp2015 last updated on Dec. 15, 2020, 8:01 p.m.

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.