Motorbike Racing

i didn't get the difference between index number and ranking list.

Initially the motorcyclist is arranged through index wise or ranking wise ??

i don't understand how to resolve, when 2 r at same position

If two are the same position, the one that comes first in the input is earlier in the rank list.

example shows 4 motorcyclists but ranks are given as 2 3 4 5 .

why not as 1 2 3 4?

i guess

index no is the order in which motorcyclists are given in the input

and rank is calculated with respect to their position ie higher the position lower(numerically) the rank and when positions are same lower the index lower(numerically) is the rank.

current position means ranking or coordinate of the biker

@ Dinesh Salve

2,3,4,5 are the speeds not the ranks

@ankit

wat is meaning of current position ith m.cyclist  .

2 100

hw is this for 4 mcyclists?

what is current position, can somoone help me.

for velocity and position, are they real numbers or integers?

Submissions aren't appearing in recent activity... anyone else submitted yet?

@shashi..same here..

same here!!

can somebody explain the condition when both the motor cyclist are at same position........... what is meant by the word "Placed"..... does it mean ranked ?????

Is there any limit on max value of v? the conditions says v >=1 but no upper limit?

@pawan When v, x appears in the middle of a bound like that, it means that the bounds apply to both v and x, i.e. 1 <= v <= 100,000 and 1 <= x <= 100,000.

I have some questions regarding the input:

1) "The i-th line in the next N lines contains two numbers, v and x, which are the velocity and the current position of the i-th motorcyclist (1 <= v, x <= 100,000)."

The inputs given in the test case are :

2 100
3 50
4 60
5 1

Is the first number x and the second number v? This would be contrary to the statement mentioned above.

2) If there are only 4 motorcyclists, why is no one placed first and why is at least one placed fifth?

3) Does position mean rank of the motorcyclist or does it refer to distance/displacement form the starting line ?

It says it will be v followed by x. Therefore it will be v followed by x.

The person at position 100 is in first place. Nobody is in 5th place.

Position means position, not rank.

@Abhijit In this case, if you swap v and x, the output changes. If your output does not match the sample output, you are doing something wrong! Why would you think the first number was x anyway?

Can we get Mustafa and Shashi's questions answered (particularly Mustafa's question about whether the inputs are integers or real numbers)? I'm not seeing any rankings, recent activity or successful submissions in the sidebar, but I am seeing updates in the problem list on the main contest page.

can you give some idea of how many calculations the judge performs per second?

encountered a problem for the first time........

i am using gcc of ubuntu..... have written a code for the above problem..... in order to troubleshoot my code i wrote some printf statements to see the control flow..... now i am getting the output but there is this mysterious printf("n") statement which i inserted to have line gap between the output.... now whenever i comment out this statement, the program crashes and it shows segmentation fault..... and if i don't there is unwanted gap between the given input and produced output, which is what i suspect is the reason of getting a WA every time i submit the code......

Can anybody suggest something why commenting a printf("n") is causing program to fail.........

@admins

I have a question.

If the submission gives error "Time Limit Exceeded".

Then is it confirm that it is giving correct output for all the test cases but only the time limit is exceeding.

@Rahul No.

@Rahul The FAQ says that the answer is "no", as confirmed by Aniruddha above. I believe the way it works is, once the time limit is up, the judge stops running your program.

with 20000 motorcyclists ,it sure will be one hell of a race.

Hi Admin,

will the value of time t in the query be unique?

@legilimen There is nothing to suggest that the time values will be unique. I think we should assume that they may or may not be unique.

Hi Admin, I am getting a "time limit exceeded error" ( using C ).

The FAQ section doesnot mention in detail about it.  I feel my code is optimised and works well for large input sizes efficiently.

What is the time limit for C ?

C#2 solutions are now accepted.

are the time queries in ascending order or any order?

I have tried several techniques for this problem and all of them give time limit exceeds !!

I even tried an empty loop just read the input and write -1 as output and also it gives time limit exceeds !!!!!

i solved motorbike race problem using the minimum data.but igot run time error. what is the problem???

I am getting a time limit exceeded on my solutions in Ruby.. Shame because I'm pretty sure what I'm doing is correct. Is the time appropriately adjusted for the Ruby language?

@Admin

c#2 is working now.. however my doubt is still not clear.. Does Visual C# 2008 Express Edition come under C# or C#2 ?? Kindly Reply.. Thanks..

I am getting a run time error. I have written my code in Python. And its working fine on my system. Strange. I dont really see an error in my code

How can i get input? i am using php.. and assigning all values using randomn values (as per the given scope)... Is it ok? .. If the N & Q get max value on randomn, it takes more time.

Whats the memory limit on this one? I think I am running out of memory. My code looks error free but it gives runtime error. I am consuming 4.5M on each run. Please help

@Sandip The FAQ says that 64 MB is guaranteed, so unless you are allocating a huge amount of memory in a single operation, your idea is probably wrong.

@ balavignesh - read the FAQ.

Admin kindly clarify whether the values of V and X are integers or numbers.. thanks..

Even after so much optimizing Time Exceeded error.. :(

Any chance of there being given an extension?? :)

Also recent activity thingy isnt working...

What recent activity are you talking about? click the all submissions button on the top of the page. The sidebar shows the successful submissions.

oh yes.. sorry.. there are 0 successful submissions for this question hence the "no recent activity".

Sorry..

I am getting wrong answer as a result. I dont know what is wrong in my logic. Following are my inputs and outputs.. Please someone tell me, whether my input are correct.. (also the output..)

input

2
4
2 100
3 50
4 60
5 1
4
1 1
50 2
60 4
100 1
5
6 34
7 5
5 1
3 10
2 23
2
50 1
500 1

output

1
4
1
4

2
2

I solved the problem but getting time exceeded. My logic is really simple and it wroks fine. Will the judge increase the time limit for this program ???

@balavignesh Anyone discussing test cases here risks disqualification, as this is a contest. There have been numerous comments at Soccer League about this.

@admin Ahmed said above that they tried submitting a program that just reads the input and it still gives Time Limit Exceeded! I also notice that there have not been any successful submissions yet. Can you confirm that the time limit is correct?

@ admin

since1<=x<=100000

so it means that at 100000 the race ends?

so after that riders will stop instead of going farther

@ admin

since1<=x<=100000

so it means that at 100000 the race ends?

so after that riders will stop instead of going farther

Please read the problem statement. Those are the constraints for the value of 'x'.

@Aashish The important point is the definition of x. This variable is carefully defined in the problem statement.

Does judge's compiler use optimization flags?

@admin :I am getting the output on my system.But here it shows run-time error(sigsegv).PLS HELP

The wording is very confusing.

Velocity, "distance traveled" and "position" would be better. Position is too ambiguous.

Is it possible to access the ONLINE_JUDGE property from Python? I tried accessing it as an environment variable using os.getenv(), but no joy.

@ admin please clarify whether the input velocity will be given in sorted manner or not????

and also about the time for which we have to find the rank will be given in sorted manner??????

It clearly doesn't say they will be sorted, so you have no reason to believe so.

The time limit on this problem is pretty hard. I doubt whether anyone can solve 10 test cases of 20000 queries of 20000 racers within 2.5 seconds.

My solution took 25 seconds for 1 test case of 20000 racers with 1000 queries.

And I can't seem to improve it other than optimising the data storage.

I brought the time down to 17 seconds by using a dynamic new techinue to store and process data. But to no avail.... :(

Even my quantum computing solution got Time Limit Exceeded... :)

Hey guys.. I have a doubt.. The position 'x' was noted for all bikes at time0 right. (i.e.) Position = velocity*time0.

But if you go by the above formula and calculate time0, it is different for each bike. How?

Is there a flaw in the question?

For example

2 100 -- > time0 = 100/2 = 50
3 50  -- > time0 = 50/3 

x is the position at time 0. So for v=2 and x=100, at time 0 the bike is at 100, at time 1 the bike is at 102, and so on. I don't know where you get 50 from.

Yes, But the time0 should be unique for all bikes..

time is essentialy distance/velocity..

so if u put this formula for each bike in the testcase u should get the same value..

which is not the case right now isn't it.. Or have a missed something here

@Srinivasan, @Stephen It seems like Srinivasan thinks that there is a variable called "time0" and the positions for each bike was noted at time = time0, where position = 0 at time = 0. If that were the case, then Srinivasan's calculations would make sense. In fact, the position for each bike was noted at time = 0.

How come CodeChef's site keep showing this message when I open the contest page :

warning: ksort() expects parameter 1 to be array, null given in /var/www/codechef/sites/all/modules/contest_page/contest_page.module on line 279.

Well... 0.15 sec for 2.9 Mb mem. So it's possible.

hi, all the number are integer?

is v and x are integers????????????

m newbie here

its my first time

can u please tell me how to take input

whether as .txt file or somhw else???

I am starting to give up on this. I dont know where I am going wrong but the following solution runs perfectly fine for any imaginable test case possible on mine but gives wrong answer here. Please show me some ight and tell me is it because of the compiler difference because I am working on Turbo c and here it is gcc or something wrong in my code

Here's my soln : http://www.codechef.com/viewsolution/185888

Just tell me this: Are all the x and v integers or should I expect floating point? I dont see anything in the question that suggests that they should be integers. I wrote my code for integers and its giving me a runtime error which I think is because a floating point value is being sent as input. Please clarify

I agree this really should have been clarified a long time ago. I'm guessing they are always integers.

Admin, Why cant problem statement be more clear. It always has some issues. We all know that if v and x are real numbers , that would have been mentioned. So I find they are integers as nothing is mentioned.

Why cant this datatype information be specified explicitly. There is fun involved in guessing corner test cases and its a part of the competition , but there is no fun in finding the datatype. Why do you guys still dont explicitly make somethings clear. Everybody who have seen this problem must have got this doubt once. It made me write some sample program to really find the datatype. This is unnecessary.

What does it take to mention that it is integer. May be I should not ask this question , as efforts were not taken to assert the problem statement, test cases and even timings for all problems. Why should you worry about explicitly specifying the datatype :)

Can somebody please put me out of my misery and give me some hint as to the approach? Can't think of anything better than O(N) per query (quickselect).

My approach was pretty messy, but the basic idea was to partition the competitors into m groups, where you can pick m as you like. Inside each group we keep track of a sorted list of these competitors according to their rank within this group as the race proceeds. This is done by precomputing all events inside a group (i.e. the times when two riders change rank). When we come to a query at time t, we first process all events that have happened since the time of the last query (queries are processed in order of time), so that the sorted list of ranks inside each group is correct.

Given a query, the problem is now to select the k'th overall smallest (or largest) from these sorted lists. This has been solved by Frederickson and Johnson in 1982 in their paper The Complexity of Selection and Ranking in X+Y and Matrices with Sorted Columns in time O(m + plog(k/p)) with p = min(k,m) per query. I didn't implement this approach, since I found it to be a bit too complicated. Instead I answered queries using something very similar to quickselect. Pick a random element from these lists, and compute using a binary search in each list the rank of the element we picked. From this we can decide exactly as in quickselect which part to recurse in. Once we are down to only a few competitors left as candidates for the k'th element, just do a standard quickselect on these.

Great win, congratulations Mark!

These were good problems.

@Mark Greve: That was interesting approach.Better than finding product of time velocity of order 1000000000.

I would really like to know what other approaches were used.

Thanks Tomek! I had the network for n = 20 with 93 gates ready for a few days. I knew this would improve my score by maybe 3-5 points, but I didn't want to submit it until the very last moment. When you hit 149, I knew I could beat it, but when you got 146.9 I wasn't sure at all. So with 20 minutes to go and my first submission using this network not beating your score, I was a bit disappointed. Luckily the optimization I had just tried out shortly before, which didn't give anything turned out to work very well with the new network for n = 20...

1. //{{{
2. #include <algorithm>
3. #include <cassert>
4. #include <cstdio>
5. #include <cstdlib>
6. #include <cctype>
7. #include <cmath>
8. #include <iostream>
9. #include <sstream>
10. #include <string>
11. #include <utility>
12. #include <vector>
13. #include <cassert>
14. #include <ctime>
15. #include <queue>
16. using namespace std;
17. #define VAR(a,b) __typeof(b) a=(b)
18. #define REP(i,n) for(int _n=n, i=0;i<_n;++i)
19. #define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
20. #define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
21. #define FOREACH(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
22. #define ALL(c) (c).begin(),(c).end()
23. #define TRACE(x) cerr << "TRACE(" #x ")" << endl;
24. #define DEBUG(x) cerr << #x << " = " << x << endl;
26. template<class T>
27. ostream& operator<<(ostream&o, const vector<T>&v) {
28. o<<'{';
29. FOREACH(it,v) o<<*it<<',';
30. return o<<'}';
31. }
32. typedef long long LL;
33. const int INF = 1000000000; const LL INFLL = LL(INF) * LL(INF);
34. typedef vector<int> VI; typedef vector<string> VS; typedef vector<VI> VVI;
35. template<class T> inline int size(const T&c) { return c.size(); }
37. class INPUT {
38. static const int BUFSIZE = 1<<16;
39. static char buffer[];
40. char *bufpos;
41. char *bufend;
42. void grabBuffer();
43. public:
44. INPUT() { grabBuffer(); }
45. bool eof() { return bufend==buffer; }
46. char nextChar() { return *bufpos; }
47. inline char readChar();
48. inline void skipWS();
49. inline unsigned readUnsigned();
50. inline int readInt();
51. };
53. char INPUT::buffer[INPUT::BUFSIZE];
55. void INPUT::grabBuffer() {
56. bufpos = buffer;
57. bufend = buffer + read(0, buffer, BUFSIZE);
58. }
60. char INPUT::readChar() {
61. char res = *bufpos++;
62. if(bufpos==bufend) grabBuffer();
63. return res;
64. }
66. inline bool myisspace(char c) { return c<=' '; }
68. void INPUT::skipWS() {
69. while(!eof() && myisspace(nextChar())) readChar();
70. }
72. unsigned INPUT::readUnsigned() {
73. skipWS();
74. unsigned res = 0;
75. while(!eof() && isdigit(nextChar())) {
76. res = 10u * res + (readChar()-'0');
77. }
78. return res;
79. }
81. int INPUT::readInt() {
82. skipWS();
83. bool neg = false;
84. if(!eof() && nextChar()=='-') { neg=true; readChar(); }
85. int res = static_cast<int>(readUnsigned());
86. if(neg) res = -res;
87. return res;
88. }
90. class OUTPUT {
91. static const int BUFSIZE = 1<<16;
92. static char buffer[];
93. char *bufpos;
94. char *BUFLIMIT;
95. public:
96. void flushBuffer();
97. OUTPUT():bufpos(buffer),BUFLIMIT(buffer+BUFSIZE-100) {}
98. ~OUTPUT() { flushBuffer(); }
99. inline void operator()(char c);
100. inline void operator()(unsigned x);
101. inline void operator()(int x);
102. inline void operator()(const char*s);
103. void operator()(const string&s) { operator()(s.c_str()); }
104. template<class A,class B>
105. void operator()(const A& a,const B& b) {
106. operator()(a); operator()(b);
107. }
108. template<class A,class B,class C>
109. void operator()(const A& a,const B& b,const C&c) {
110. operator()(a); operator()(b); operator()(c);
111. }
112. template<class A,class B,class C,class D>
113. void operator()(const A& a,const B& b,const C&c,const D&d) {
114. operator()(a); operator()(b); operator()(c); operator()(d);
115. }
116. template<class A,class B,class C,class D,class E>
117. void operator()(const A& a,const B& b,const C&c,const D&d,const E&e) {
118. operator()(a); operator()(b); operator()(c); operator()(d); operator()(e);
119. }
120. template<class A,class B,class C,class D,class E,class F>
121. void operator()(const A& a,const B& b,const C&c,const D&d,const E&e,const F&f) {
122. operator()(a); operator()(b); operator()(c); operator()(d); operator()(e); operator()(f);
123. }
124. };
126. char OUTPUT::buffer[OUTPUT::BUFSIZE];
128. void OUTPUT::flushBuffer() {
129. char *p = buffer;
130. while(p < bufpos) {
131. p += write(1, p, bufpos-p);
132. }
133. bufpos = buffer;
134. }
136. void OUTPUT::operator()(char c) {
137. *bufpos = c;
138. ++bufpos;
139. if(bufpos >= BUFLIMIT) flushBuffer();
140. }
142. void OUTPUT::operator()(unsigned x) {
143. char *old = bufpos;
144. do {
145. *bufpos = char('0' + x % 10u);
146. x /= 10u;
147. ++bufpos;
148. } while(x);
149. reverse(old, bufpos);
150. if(bufpos >= BUFLIMIT) flushBuffer();
151. }
153. void OUTPUT::operator()(int x) {
154. if(x<0) { operator()('-'); x = -x; }
155. operator()(static_cast<unsigned>(x));
156. }
158. void OUTPUT::operator()(const char*s) {
159. while(*s) operator()(*s++);
160. }
162. INPUT input;
163. OUTPUT output;
165. //}}}
167. const int TIME_SWITCH = 50;
168. const int SORT_THRESHOLD = 6;
169. const int MAX_DISTANCE = 100000;
171. struct Player {
172. int id;
173. int x0,v;
174. LL curPos;
175. };
177. struct Query {
178. int id;
179. int t,pos;
180. int answer;
181. };
183. vector<Player> players;
184. vector<Query> queries;
185. int nextQueryNr;
187. inline bool operator<(const Player &a, const Player &b) {
188. if(a.curPos != b.curPos) return a.curPos > b.curPos;
189. return a.id < b.id;
190. }
192. void readInput() {
193. int n = input.readInt();
194. players.resize(n);
195. REP(i,n) {
196. Player &p = players[i];
197. p.id = i;
198. p.v = input.readInt();
199. p.x0 = input.readInt();
200. }
201. int nq = input.readInt();
202. queries.resize(nq);
203. REP(i,nq) {
204. Query &q = queries[i];
205. q.id = i;
206. q.t = input.readInt();
207. q.pos = input.readInt()-1;
208. q.answer = -1;
209. }
210. }
212. struct cmpQueryTime {
213. inline bool operator()(const Query&a, const Query&b) const {
214. return a.t < b.t;
215. }
216. };
219. void sortQueries() {
220. sort(queries.begin(), queries.end(), cmpQueryTime());
221. nextQueryNr = 0;
222. }
224. void positionPlayers(int t) {
225. FOREACH(it, players) {
226. Player &p = *it;
227. p.curPos = p.x0 + LL(t) * LL(p.v);
228. }
229. }
232. void phase0() {
233. while(nextQueryNr < size(queries)) {
234. int t = queries[nextQueryNr].t;
235. if(t >= TIME_SWITCH) break;
236. int p = nextQueryNr+1;
237. while(p<size(queries) && queries[p].t == t) ++p;
238. positionPlayers(t);
239. if(p-nextQueryNr >= SORT_THRESHOLD) {
240. sort(players.begin(), players.end());
241. FOR(i,nextQueryNr,p-1) {
242. Query &q = queries[i];
243. q.answer = players[q.pos].id;
244. }
245. } else {
246. FOR(i,nextQueryNr,p-1) {
247. Query &q = queries[i];
248. nth_element(players.begin(), players.begin()+q.pos, players.end());
249. q.answer = players[q.pos].id;
250. }
251. }
252. nextQueryNr = p;
253. }
254. }
256. struct cmpVelocity {
257. inline bool operator()(const Player&a, const Player&b) const {
258. return a.v > b.v;
259. }
260. };
262. struct Event {
263. int t,a,b; // player with id a passes player b
264. Event(int t,int a,int b):t(t),a(a),b(b) {}
265. };
267. inline bool operator<(const Event &a, const Event &b) {
268. return a.t < b.t;
269. }
271. int nextEventNr;
272. vector<Event> events;
273. vector<int> playerAt; // id -> player position
275. void processEvents(int t) {
276. while(nextEventNr < size(events) && events[nextEventNr].t <= t) {
277. int idA = events[nextEventNr].a;
278. int idB = events[nextEventNr].b;
279. ++nextEventNr;
280. int posA = playerAt[idA];
281. int posB = playerAt[idB];
282. if(posA > posB) {
283. playerAt[idA] = posB;
284. playerAt[idB] = posA;
285. swap(players[posA], players[posB]);
286. }
287. }
288. }
290. void phase1() {
291. sort(players.begin(), players.end(), cmpVelocity());
292. events.clear();
293. REP(a,size(players)) {
294. FOR(b,a+1,size(players)-1) {
295. int dv = players[a].v - players[b].v;
296. if(dv * TIME_SWITCH > MAX_DISTANCE) break;
297. if(dv==0) continue;
298. int dx = players[b].x0 - players[a].x0;
299. int aid = players[a].id;
300. int bid = players[b].id;
301. if(aid > bid) ++dx;
302. if(dx<=0) continue;
303. int t = (dx+dv-1)/dv;
304. if(t <= TIME_SWITCH) continue;
305. events.push_back(Event(t,aid,bid));
306. }
307. }
308. sort(events.begin(), events.end());
310. positionPlayers(TIME_SWITCH);
311. sort(players.begin(), players.end());
312. playerAt.resize(size(players));
313. REP(i,size(players)) {
314. playerAt[players[i].id] = i;
315. players[i].v = 0; // reuse as visited
316. }
317. nextEventNr=0;
318. while(nextQueryNr < size(queries)) {
319. Query &q = queries[nextQueryNr++];
320. processEvents(q.t);
321. q.answer = players[q.pos].id;
322. }
323. }
325. void solve() {
326. phase0();
327. phase1();
328. }
330. void print() {
331. vector<int> answers(size(queries),-1);
332. FOREACH(it,queries) {
333. Query &q = *it;
334. answers[q.id] = q.answer;
335. }
336. FOREACH(it, answers) output(*it + 1, 'n');
337. output('n');
338. }
340. int main() {
341. int ntc = input.readInt();
342. REP(tc,ntc) {
343. readInput();
344. sortQueries();
345. solve();
346. print();
347. }
348. }

My solution is actually quite similar to Mark's, but instead of keeping each individual group sorted, I keep the groups themselves in order (that is, every motorcycle in group i will be ahead of every motorcycle in group j if i<j).  Then for each query I can find the right group with binary search, then use nth_element to find the right motorcycle within the group.  Unfortunately, it's possible for every motorcycle to end up in the same group, but I got lucky and there weren't any test cases like this (I was quite surprised when my submission passed).

Ha, I was thinking you must have found a 92 comparators network. I also had a 93-gate network for n=20, but apparently wasn't optimizing it nearly that well.

I have to admit that my 0.15 solution could have probably been defeated with more difficult test cases - it's O(N^2 + Q log Q) in the worst case. I generate all pairwise position swaps after t=50, by looking at all pairs of bikers with the difference in velocities smaller than 2000. Apparently there weren't that many pairs of bikers with velocities that close.

Thanks guys. I suspected it would be something along the lines of grouping, but was always put off by easy worst cases.

I would be rather disappointed if the official solution had a worst-case quadratic running time.

Can somebody please post all the test cases used while evaluating the answers?? It will really help me to know what did I miss in this problem with my approach..