## 11766 - Racing Car Computer

Moderator: Board moderators

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### 11766 - Racing Car Computer

Is it DP? How do you people solve this?
regards,
nymo

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### Re: 11766 - Racing Car Computer

I haven't solved the problem yet. Still, I have a few remarks:

Code: Select all

``````i-th car is definitely lying if a[i]+1+b[i] > n;
every pair (a[i],b[i]) _uniquely_ defines the configuration of the cars
``````
Now, if a particular car -- say, j-th -- is definitely lying in the above sense, and i-th car's data is plausible,
then then the relative order of the cars determined by (a,b) dictates terms for j-th car, i.e. we place
j-th car wherever we like. Considering only cars with plausible data, we are looking for a maximum (in terms of cardinality)
consistent subset...

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### Re: 11766 - Racing Car Computer

It was I who was lying when I said that (a,b) uniquely defines the configuration. Obviously it does not.