You are not logged in. Please login at www.codechef.com to post your questions!

×

CARVANS - Editorial

5
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

CAKEWALK

PREREQUISITES

Simple Math

PROBLEM

There are N cars on a narrow road that are moving in the same direction. Each car has maximum speed. No car can overtake other cars on this road. Each car will move at the maximum possible speed while avoiding any collisions. Count the number of cars which are moving at their maximum speeds.

QUICK EXPLANATION

Intuitively, a car is moving at its maximum speed if and only if all cars in front of it are moving at greater speeds (otherwise it will overtake the slower car). Therefore, the answer is the number of such cars.

EXPLANATION

Suppose that the cars are numbered 1 through N from front to back, and the maximum speed of the i-th car is maxSpeed[i]. From the intuitive observation above, we can directly come up with this naive solution:

answer = 0
for i = 1; i <= N; i++:
    allGreater = true
    for j = 1; j <= i-1; j++:
        if maxSpeed[j] < maxSpeed[i]:
            allGreater = false
    if allGreater:
        answer = answer + 1

Unfortunately, this solution runs in O(N^2) time, which will surely time out. We will need other observations.

Consider each car. From the problem statement, each car will:

  • Avoid any collisions. Since the road is narrow, therefore, it will not move at greater speed than the car directly in front of it (if any).
  • Move at the maximum possible speed. Therefore, it will move at speed of exactly min(the maximum speed of the car, the speed of the car directly in front of it).

From those observations, we can calculate the speed of each car in O(1) time. When calculating the speed of the i-th car, we have to know the speed of the (i-1)st car. Therefore, we must calculate the speeds in the right order (i.e., from the first car to the last car on the road). After that, we compare the speed of each car with its maximum speed.

A direct implementation of the above solution is as follows. This solution runs in O(N) time, which will pass the time limit.

answer = 0

speed[1] = maxSpeed[1]
for i = 2; i <= N; i++:
    speed[i] = min(maxSpeed[i], speed[i-1])

for i = 1; i <= N; i++:
    if speed[i] == maxSpeed[i]:
        answer = answer + 1

Exercise

Try to solve this problem without creating the additional speed[]/maxSpeed[] array. Hint: we can always store only the speed of the last car we consider instead of storing all speeds in speed[] array.

SETTER'S SOLUTION

Can be found here

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 24 Sep '12, 00:50

fushar's gravatar image

3★fushar ♦♦
16345853
accept rate: 0%

edited 25 Dec '12, 13:34

admin's gravatar image

0★admin ♦♦
14.9k347484503

the obvious/funny thing is :since at anytime we are dealing with two consecutive cars only, problem can be solved without the need of an array.

(24 Sep '12, 01:22) kunalkrishna852★

By the way, why 4MB is 4,000,000,000 bytes :)

It is mentioned in three problems CARVANS, PPERM and COALSCAM.

(24 Sep '12, 02:33) anton_lunyov ♦♦6★

Yes. All three of us missed that :P Will fix it for the problems in the practice section.

(24 Sep '12, 09:54) gamabunta ♦♦1★

we don't even need arrays!! http://www.codechef.com/viewsolution/1364489

link

answered 24 Sep '12, 00:54

abhinav1592's gravatar image

2★abhinav1592
4572713
accept rate: 0%

The problem can be solved even without creating an array maxSpeed[]. We can do all calculations during input stage:

answer := 1
read(speed)
for i:=2 to N do
  read(maxSpeed)
  if speed >= maxSpeed
    then answer := answer + 1
  speed = max(speed, maxSpeed)

link

answered 24 Sep '12, 00:57

anton_lunyov's gravatar image

6★anton_lunyov ♦♦
6.6k62119138
accept rate: 12%

why this shows time limit exceed?

http://www.codechef.com/viewsolution/1370908

(24 Sep '12, 02:26) ak11111110★
2

Use scanf, printf instead of cin, cout.

(24 Sep '12, 02:31) anton_lunyov ♦♦6★
1

if W==1 you still need to input speed of the only car of this test. Otherwise you consider its speed as a number of cars for the next test. Also while(--N) as well as while(--W) is wrong. By this you miss the last test case, last car respectively. Use while(N--) and while(W--) instead.

(24 Sep '12, 02:43) anton_lunyov ♦♦6★

@anton_lunyov ...you're right, corrected those.

Got a correct one ! thanks

(24 Sep '12, 02:53) ak11111110★

Did you even run the program on local machine and test? its full of errors!

printf("1\n");    // this was using front slash
while(--W)        // --W and not W-- this was causing TLE
printf("%d\n",counter); // reference was passed here!
(24 Sep '12, 03:05) kriateive5★

Sorry. This was my advise. Second while really should have --W. I didn't see the scanf before :)

(24 Sep '12, 03:09) anton_lunyov ♦♦6★
showing 5 of 6 show all

I wanted to know what would be the output for the following test case 8 4 6 5 Would it be 3 or 2? I read abhinav1592's solution and it gives the answer as 2 I think the answer should be 3 because in the problem it is clearly mentioned that cars cannot overtake as the track is not wide enough. So the first car is travelling at max speed. The second one is also travelling at max speed since its speed is less than 8. The third one is not at max speed. The fourth one is travelling at max speed. We just have to compare the speeds of consecutive cars right??? and not with all the cars.. as cars cannot overtake.. Please help me understand the problem..

link

answered 03 Oct '12, 01:02

mancoolgunda's gravatar image

1★mancoolgunda
615613
accept rate: 0%

edited 03 Oct '12, 01:06

The third car also moves with speed 4 since it can not overtake the second car. So yes, we should compare only consecutive cars but the speed of each car may change.

(03 Oct '12, 17:43) anton_adm ♦♦2★

solved - http://www.codechef.com/viewsolution/1374650 but have a question.

Can anyone point out (line 29 - commented out) why do we get "Runtime Error" if I do a br.close (closing the BufferedReader). I thought closing the BufferedReader was a good practice.

Once I commented it out, the submission was accepted.

link

answered 26 Sep '12, 04:02

ujjalcal's gravatar image

0★ujjalcal
1112
accept rate: 0%

Why am i getting a WA here ? http://www.codechef.com/viewsolution/4375902

link

answered 25 Jul '14, 12:18

ak795's gravatar image

4★ak795
11
accept rate: 0%

http://ideone.com/9RxEMi please figure out where i am wrong....

link

answered 07 Oct '14, 19:10

vickycod's gravatar image

2★vickycod
21112
accept rate: 6%

Sir, may i know why this is giving worng answer? thanks

include<stdio.h>

int main(){ int t,n,count; long long int a[10000]; scanf("%d",&t); while(t--){ count=1; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); if(a[i]<=a[i-1] &&i !=0){ count++; } } printf("%d\n",count); } }

link

answered 16 Jan '15, 12:19

nischitpra's gravatar image

2★nischitpra
1
accept rate: 0%

Even this problem can be solved without the help of any array : in o(n-1)time sol is:http://www.codechef.com/viewsolution/6400303

link

answered 06 Mar '15, 01:17

ritwikenator's gravatar image

2★ritwikenator
4614
accept rate: 16%

include<iostream>

using namespace std; int main() { int t,n; cin>>t; while(t--) { cin>>n; int a[n],i,count=1; for(i=0;i<n;i++) cin="">>a[i]; for(i=1;i<n;i++) { if(a[i]<a[i-1]) count++; } cout<<count<<"\n"; } return(0); }

link
This answer is marked "community wiki".

answered 08 Jul '16, 14:14

ny826's gravatar image

1★ny826
1
accept rate: 0%

what is wrong in this question

(08 Jul '16, 14:14) ny8261★

please help me

(08 Jul '16, 14:15) ny8261★

include<iostream>

using namespace std;

int main() { int t; cin>>t; while(t--){ int n; cin>>n; int a[n+1]; for(int i=1;i<=n;i++){ cin>>a[i];

    }
    int ans=0;
    a[0]=-1;
    for(int i=1;i<=n;i++){
        if(a[i]<a[i-1]) ans++;
    }
    cout<<ans<<endl;
}
return 0;

}

link
This answer is marked "community wiki".

answered 04 Nov '16, 02:56

rrishabh's gravatar image

2★rrishabh
1
accept rate: 0%

"""This approach works too ,and is faster than other appraoches mentioned above""" """AC in one go"""

test=int(raw_input())
for _ in range(test):
N=int(raw_input())
count=1
arr=list()
arr=[int(i) for i in raw_input().split()]
for i in range(len(arr)-1):
    if(arr[i+1]>arr[i]):
        arr[i+1]=arr[i]
    else:
        count+=1
print count
link

answered 08 Jan, 23:11

rohithrajr's gravatar image

0★rohithrajr
1
accept rate: 0%

edited 08 Jan, 23:13

can some one find mistake in this code

import java.util.; import java.lang.; import java.io.*; class klf { public static void main(String[]args) throws Exception { Scanner cin=new Scanner(System.in); Stack<integer>st; int t=cin.nextInt(); while(t-->0) { st=new Stack<integer>(); int n=cin.nextInt(); int a[]=new int[n]; for(int i=0;i<n;i++) { a[i]=cin.nextInt(); } int count=0; for(int i=0;i<n;i++) { if(st.empty()) { st.push(a[i]); count++; } else if(a[i]<st.peek()) { st.push(a[i]); count++; } else { st.push(a[i]); } } while(!st.empty()) st.pop(); System.out.println(count); } } }

link

answered 27 Mar, 23:17

ajit_yadav's gravatar image

0★ajit_yadav
1
accept rate: 0%

strong text Can anybody please let me know what is wrong with my code.. strong text

include<stdio.h>

int main(){ int rounds,cars,speed,count=0; for(scanf("%d",&rounds);rounds;rounds--){ int min=10000; count=0; for(scanf("%d",&cars);cars;cars--){ scanf("%d",&speed); if(speed<=min){ count++; min=speed; } } printf("%d\n",count);

}

return 0;

}

link

answered 19 May, 14:27

ktsindav's gravatar image

0★ktsindav
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×10,491
×954
×242
×8
×5

Asked: 24 Sep '12, 00:50

Seen: 7,637 times

Last updated: 19 May, 14:27