PROBLEM LINKSDIFFICULTYCAKEWALK PREREQUISITESSimple Math PROBLEMThere 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 EXPLANATIONIntuitively, 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. EXPLANATIONSuppose 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:
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 SOLUTIONCan be found here TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 24 Sep '12, 00:50 ![]()
|
we don't even need arrays!! http://www.codechef.com/viewsolution/1364489 answered 24 Sep '12, 00:54 ![]()
|
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) answered 24 Sep '12, 00:57 ![]()
why this shows time limit exceed?
(24 Sep '12, 02:26)
2
Use scanf, printf instead of cin, cout.
(24 Sep '12, 02:31)
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 ...you're right, corrected those. Got a correct one ! thanks
(24 Sep '12, 02:53)
Did you even run the program on local machine and test? its full of errors!
(24 Sep '12, 03:05)
Sorry. This was my advise. Second while really should have --W. I didn't see the scanf before :)
(24 Sep '12, 03:09)
showing 5 of 6
show all
|
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. answered 26 Sep '12, 04:02 ![]()
|
Why am i getting a WA here ? http://www.codechef.com/viewsolution/4375902 answered 25 Jul '14, 12:18 ![]()
|
http://ideone.com/9RxEMi please figure out where i am wrong.... answered 07 Oct '14, 19:10 ![]()
|
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); } } answered 16 Jan '15, 12:19 ![]()
|
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 answered 06 Mar '15, 01:17 ![]()
|
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 ![]()
|
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];
}
link
This answer is marked "community wiki".
answered 04 Nov '16, 02:56 ![]()
|
"""This approach works too ,and is faster than other appraoches mentioned above""" """AC in one go"""
answered 08 Jan '17, 23:11 ![]()
|
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); } } } answered 27 Mar '17, 23:17 ![]()
|
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); }
} answered 19 May '17, 14:27 ![]()
|
Does Input to this problem is in file? Am i need to take input from files? answered 15 Jul '17, 18:10 ![]()
|
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.
By the way, why 4MB is 4,000,000,000 bytes :)
It is mentioned in three problems CARVANS, PPERM and COALSCAM.
Yes. All three of us missed that :P Will fix it for the problems in the practice section.