ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1791. Uncle Styopa and Buses

Anybody would like to share some ideas? Thanks.
Posted by [York Hotel] 3xian 16 Oct 2010 18:54
Anybody would like to share some ideas? Thanks.
Re: Anybody would like to share some ideas? Thanks.
Posted by Avriskin[SESC USU] 17 Oct 2010 13:00
Greedy algorithm.
For every bus you can comptute "Critical time"=p[i]+t[i]-i.
If 1st Bus from "Small Vasyuki" will pass the road after critical time of ith bus from "Small Vasyuki" then ith bus will be late. If jth bus from "Small Vasyuki" will pass the road after (critical time + j-1) then ith bus will be late.

If k1-1 buses from "Small Vasyuki" passed and k2-1 buses from "Big Vasyuki" passed then buses from direction with lower critcaltime(of some bus)+k (k1 or k2) are prefered.

Edited by author 17.10.2010 14:17
Re: Anybody would like to share some ideas? Thanks.
Posted by [York Hotel] 3xian 17 Oct 2010 15:04
Get it.
Thank you.
Re: Anybody would like to share some ideas? Thanks.
Posted by Haixia Sahyon 18 Oct 2010 21:53
Let 'l' and 'r' be the waiting buses on each direction.

Let l[i].f be l[i].t + l[i].p

I define the priority between buses as follows:
1. If l[i].t < r[j].t then l[i] should pass first.
2. If l[i].t > r[j].t then r[j] should pass first.
ELSE (l[i].t==r[j].t)
3. If l[i].f < r[j].f then l[i] should pass first.
4. If l[i].f > r[j].f then r[i] should pass first.
ELSE (l[i].f==r[j].f)
5. If l[i+1] should pass before r[j+1] then l[i] should pass first, else r[j]

Can anyone provide a counterexample for this approach?

---
Nevermind, I was terribly wrong.

Edited by author 18.10.2010 22:10
Re: Anybody would like to share some ideas? Thanks.
Posted by svr 19 Oct 2010 15:41
You said about greedy criterion as it is your discovery.
More rightly  to note math theorem, name of schedulling
problem, article in wiki.
We have two decks of cards. On each step we dicide from which of them to take one card. For decision we must compare two new states acording two way of choice. You formula is criterion of compairing. But prove is unknown and criterion may be very deep but not absolute greedy.

Edited by author 19.10.2010 16:01
Re: Anybody would like to share some ideas? Thanks.
Posted by Haixia Sahyon 19 Oct 2010 19:20
Consider the following algorithm:

current_time = 0

While there are buses, select a bus i according to Avriskin's priority.

If current_time + 1 > ti + pi then answer "NO" else current_time = max(current_time, ti) + 1 and erase the bus.

Does anyone see something wrong?
Re: Anybody would like to share some ideas? Thanks.
Posted by RR 16 Jan 2011 21:36
I used simple dynamic programming :)