### simp1eton's blog

By simp1eton, 11 years ago,
Hi all,

I have a few problems in this contest that I am not sure about. Can I please have some help? Thanks!

The first problem is problem B (School).

I have no idea how to do this problem. Actually, I dont really understand the question as well :(. Can someone help me?

Problem C (Dancing Lessons):

I wrote my code, but it keeps failing on testcase 11 and I dont know why. The outline of my algorithm is as follows:

First, I find all the immediate pairs of boys and girls and push them all into a set. The pairs in the set are sorted according to the conditions given.

Then, if the set is not empty:
1) I take the best pair out of the set.
2) If both members of the pair have not gone off for the dance yet, I add this person into the dance. Then, I add the pair that envelopes this pair into the set (for example, if I remove pair (4,5), I add pair (3,6) if this pair is available).
3) If one member is present, I expand it until I hit someone. Then I push it into the set.
4) If both members are gone, I just remove this pair from the set.

I keep doing this. Below is a link to my code.

http://pastebin.com/qAipmk63

Can someone help me and tell me what is wrong? :(

• 0

 11 years ago, # |   +3 With C, I seem "if" clauses in the loop aren't needed except first clause.Broken pairs are not needed to be repaired.But, modified code was TLE@26.You should make use of more efficient data structure.
•  11 years ago, # ^ |   0 Ok thanks, I have solved it.What about F (Goats and Wolves)? Do you have any idea?
•  11 years ago, # ^ | ← Rev. 2 →   0 In fact, I've been caught on case 10 with F.Main idea... in (wolf,goat)-space, valid condition on a bank is g=0 or g>=w. On the other bank, m-g=0 or m-g>=m-w, simultaneously. So the condition 'g=0 or g=w or g=m' remains. This forms like a letter 'Z'.On this 'Z' shape, you move from (0,0) to (m,m) as fast as possible. At odd steps, you can move from (x,y) to (x',y') such that (x',y')>=(x,y) and (x',y')!=(x,y) and (x'-x)+(y'-y)<=n. At even steps, (x',y')<=(x,y) and (x',y')!=(x,y) and (x-x')+(y-y')<=n.So, sample1 follows, (0,0)->(2,0)->(1,0)->(3,0)->(2,0)->(2,2)->(1,1)->(1,3)->(0,3)->(2,3)->(1,3)->(3,3), 11 steps.I'm overlooking something... but I've not found it.
•  11 years ago, # ^ |   +5 Lol, I am caught on testcase 10 too XD
 11 years ago, # |   0 oh, reallyI wrote too much :-)
•  11 years ago, # ^ |   0 Haha XD.My solution is different though. It is kind of a constant time solution.http://pastebin.com/EzNPZNif
•  11 years ago, # ^ | ← Rev. 2 →   0 oh very com... simple! I can't paste my solution now, but it is long BFS.