simp1eton's blog

Questions about Winter School Team Contest #3
By simp1eton, 14 years ago, In English
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? :(

Thanks a lot in advance!
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
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.

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Ok thanks, I have solved it.

    What about F (Goats and Wolves)? Do you have any idea?
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      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.
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
oh, really
I wrote too much :-)
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Haha XD.

    My solution is different though. It is kind of a constant time solution.

    http://pastebin.com/EzNPZNif
    → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      oh very com... simple! I can't paste my solution now, but it is long BFS.
      → Reply