11766 - Racing Car Computer

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11766 - Racing Car Computer

Post by nymo » Sun Jan 24, 2010 9:26 pm

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

Post by serur » Mon Feb 01, 2010 8:59 am

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

Post by serur » Mon Feb 01, 2010 3:12 pm

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

Post Reply

Return to “Volume 117 (11700-11799)”