OJ Board

The problem states..

The tournament schedule is organized so that no knight needs to compete in more than e events to be champion, for the minimum possible e given k, the number of knights.

The minimum possible e should be always 1. So, the number of knights can be reduced to 2. Am I right or I am missing something??

Thanks.

Jan wrote:The problem states..

The tournament schedule is organized so that no knight needs to compete in more than e events to be champion, for the minimum possible e given k, the number of knights.

The minimum possible e should be always 1. So, the number of knights can be reduced to 2. Am I right or I am missing something??
Thanks.

This question has really confused me!
Going by the words in the problem, I inferr the same as u!
All I did was:
Just scan all the knights and sort them based on their ratings.
Out put all the knights except the last 2.
If these knights are byes then we have the minimum possible value of (a - b)^2 for the 2 knights

This is what I did and got WA!!
Can anyone tell me, what is asked by the problem?
Is the problem statement, really clear enough? (I don't believe so!!! )

The correct way to interpret the problem is this.
First, think of the tournment as a binary tree, where each node is either a leaf, or has 2 children.

e is defined to be the minimum height over all possible trees.
Thus, e=ceiling(log(n)). It is then easy to compute how many byes are necessary.

A trivial dp solution is going to be O(n^3), which is TLE.
You need to think of a greedy solution that is O(n log n)

Judging by the number of people that solved this problem, this is not a very easy problem.

Jan wrote:The problem states..

The tournament schedule is organized so that no knight needs to compete in more than e events to be champion, for the minimum possible e given k, the number of knights.

The minimum possible e should be always 1. So, the number of knights can be reduced to 2. Am I right or I am missing something??

Thanks.

I composed the problem, so I am hardly an unbiased observer. But I think th e statement is clear. Suppose we have 4 knights, A,B,C,D. An optimal schedule involves 2 rounds where A plays B, C plays D, and then the winners play. So any knight, to win, must do 2 events. So no knight needs to compete in more than 2 events to win.

Now if, for example, A plays B, the winner plays C, and the winner plays D, we have the case that A needs to play in 3 events to win. So it is not true that no knight must compete in more than 2 events, because A must. So this second schedule fails to maximize e.

gvcormac wrote:I composed the problem, so I am hardly an unbiased observer. But I think th e statement is clear. Suppose we have 4 knights, A,B,C,D. An optimal schedule involves 2 rounds where A plays B, C plays D, and then the winners play. So any knight, to win, must do 2 events. So no knight needs to compete in more than 2 events to win.

Now if, for example, A plays B, the winner plays C, and the winner plays D, we have the case that A needs to play in 3 events to win. So it is not true that no knight must compete in more than 2 events, because A must. So this second schedule fails to maximize e.

Well, 4 knights, A, B, C, D. A plays B, and both C and D are given a bye. So, the winner has to compete 1 event. So, the minimum e should be 1. May be I am not geting it right. I have read sclo's post. But I don't think the problem reflects that. However, I will try to do it in his way.

Jan wrote:

gvcormac wrote: Now if, for example, A plays B, the winner plays C, and the winner plays D, we have the case that A needs to play in 3 events to win. So it is not true that no knight must compete in more than 2 events, because A must. So this second schedule fails to maximize e.

Well, 4 knights, A, B, C, D. A plays B, and both C and D are given a bye. So, the winner has to compete 1 event. So, the minimum e should be 1. May be I am not geting it right. I have read sclo's post. But I don't think the problem reflects that. However, I will try to do it in his way.

It says "no knight needs to compete in more than e events to win," not "some knight may win by competing in e events."

I have understood it now. Thanks .

What I did was -
1. Find the number of knights that will get a bye.

Let the number of knights that didn't get a bye = M.

2. Then I sorted all the <name, ability> in increasing order of ability.

Isn't it true that the best selection of M knights would be a consecutive subsequence?

This method gets WA!!

sohel wrote:What I did was -
1. Find the number of knights that will get a bye.

Let the number of knights that didn't get a bye = M.

2. Then I sorted all the <name, ability> in increasing order of ability.

Isn't it true that the best selection of M knights would be a consecutive subsequence?

This method gets WA!!

Here's a counterexample:

A 1
B 2
C 10
D 20
E 30
F 40
G 41

There is a greedy solution, but not quite that simple. It has a structure that looks like dijkstra.

I would like to use the occasion that prof. Cormac become involved
in this discussion to say THANK YOU to the Waterloo team for the excellent
problems they offered us during the last decade. I learnt a lot from
these problems.

I am extremely curious about the logic behind the author's solution of
this particular problem. Correct me if I am wrong, but it seems that
the problem is not about finding the "optimal" pairing in the first round
of the tournament, but rather to find the "lucky" knights who are not going
to take part in it (in other words - this is not the same problem as finding
the "optimal" pairing itself)?

By the the way, I recently came across a curious quote:

"...realize should you Luke that two ways are there to solve a problem - DP and
greedy called are they. Implies the first - the Force use you. Implies the second -
closer to the Dark Side are you, in danger you are..."
Yoda

sclo wrote:There is a greedy solution, but not quite that simple. It has a structure that looks like dijkstra.

I solved the problem using DP. Don't have any clue with greedy solution.
Could someone give me a hint ?

Anyway, if it has a structure like dijkstra, isn't it DP-kind solution ..?

----
Rio

rio wrote:

sclo wrote:There is a greedy solution, but not quite that simple. It has a structure that looks like dijkstra.

I solved the problem using DP. Don't have any clue with greedy solution.
Could someone give me a hint ?

Anyway, if it has a structure like dijkstra, isn't it DP-kind solution ..?

----
Rio

I think it is a mix of dp and greedy. Greedy because it involves a greedy choice. DP because it exhibits optimal substructure property. But I think it is really classified as greedy.

Greedy choice: At any step, we only need to consider adjacent knights, and pick the pair that has minimum cost.
The trick here is the define the cost properly. At the beginning, the cost is defined only between adjacent pairs and it is (a-b)^2 as expected. The trick is to figure out how to update the cost once a pair of knights are extracted.

Thanks sclo. I think I understood.

----
Rio

How do you prove the greedy is always correct?