Search found 202 matches

by baodog
Wed May 20, 2009 2:10 am
Forum: Volume 116 (11600-11699)
Topic: 11613 - Acme Corporation
Replies: 5
Views: 1936

Re: 11613 - Acme Corporation

Hi,

Thanks! You are solving min cost flow using ternary search + min cost max flow .. A primal dual or cycle cancelation solution might be faster.
by baodog
Sun Jan 04, 2009 2:34 am
Forum: Volume 115 (11500-11599)
Topic: 11568 - Pincer Attack!!
Replies: 5
Views: 1201

Re: 11568 - Pincer Attack!!

Thanks! Got accepted.
by baodog
Fri Jan 02, 2009 11:53 pm
Forum: Volume 115 (11500-11599)
Topic: 11568 - Pincer Attack!!
Replies: 5
Views: 1201

Re: 11568 - Pincer Attack!!

1) Does bumping into mean robot and person cannot be in *adjacent" squares? Or just that they cannot be in same square? 2) Can robots see through each other? 3) What's wrong with NNWXNWWSW for my 3rd example? why a longer path is required? I simulate this and it looks perfectly fine to me. Thanks!
by baodog
Fri Jan 02, 2009 11:25 pm
Forum: Volume 115 (11500-11599)
Topic: 11568 - Pincer Attack!!
Replies: 5
Views: 1201

Re: 11568 - Pincer Attack!!

Hi, I keep get WA. Is the following io I got correct? Thanks in advance!! 8 ######## #S# # #E # # ## # ### T ### ## ## X ## ######## 8 ######## #S# # #E # # T ## # ### # ### ## ## X ## ######## 8 ######## #S#E # # # # # T # # ### ## ## X ## ######## 8 ######## #S#W # # # # # T # # ### ## ## X ## ###...
by baodog
Tue Dec 30, 2008 1:25 am
Forum: Volume 115 (11500-11599)
Topic: 11566 - Let's Yum Cha!
Replies: 10
Views: 4362

Re: 11566 Let's Yum Cha!

Hi, Any tricky datasets? I keep get wa. Thanks. Here is some of my IO. 3 10 5 2 6 7 5 6 9 10 9 10 10 8 3 10 5 2 6 7 5 6 9 10 9 10 2 8 3 10 5 2 6 7 5 6 9 10 2 1 3 8 9 9 3 2 4 7 5 6 9 10 2 1 3 8 0 0 0 0 16.00 14.00 13.50 10.20 Here is my code. It's just simple memorization. Thanks. Thanks! Fixed stupi...
by baodog
Sun Nov 02, 2008 10:28 pm
Forum: Volume 115 (11500-11599)
Topic: 11548 - Blackboard Bonanza
Replies: 17
Views: 5391

Re: 11548 - Blackboard Bonanza

First of all. Nice problem. However the problem statement is not completely correct, or the solution/ test cases are not. "What is the maximum number of candies that one of Alice and Bob will get in a turn?" "WILL GET" implies that no matter how the randomness of the words in the bag occurs they hav...
by baodog
Sun Nov 02, 2008 9:54 am
Forum: Volume 115 (11500-11599)
Topic: 11548 - Blackboard Bonanza
Replies: 17
Views: 5391

Re: 11548 - Blackboard Bonanza

It does not have to be contiguous!! You can skip letters. LCS is not the right algo!!!

Code: Select all

1
2
BOBALICALICBBBOBALICALICBBBOBALICALICBB
BOBALICEALICBOBALICEALICBOBALICEALICBOBALICEALICBOB

Code: Select all

15
by baodog
Fri Oct 31, 2008 6:32 am
Forum: Volume 115 (11500-11599)
Topic: 11544 - Recruiter's Problem
Replies: 12
Views: 1954

Re: 11544 - Recruiter's Problem

I get same answers.
by baodog
Thu Oct 30, 2008 11:43 am
Forum: Volume 115 (11500-11599)
Topic: 11544 - Recruiter's Problem
Replies: 12
Views: 1954

Re: 11544 - Recruiter's Problem

Thanks! I get it now, but I get TLE.

1) Do you clear the flows when you re-run network flow?
2) Do you use ford-fulkelson or dinic?

Thanks.
by baodog
Thu Oct 30, 2008 9:57 am
Forum: Volume 115 (11500-11599)
Topic: 11544 - Recruiter's Problem
Replies: 12
Views: 1954

Re: 11544 - Recruiter's Problem

>Suppose edges are ordered by worker #1's most preferred job,2nd most preferred job,....worker#2's most preferred,2nd most >preferred and so on. >To determine the assignment, I removed each edge in increasing order and saw if it reduces the network flow by 1. If it >does assign that worker to that j...
by baodog
Tue Oct 28, 2008 4:16 am
Forum: Volume 115 (11500-11599)
Topic: 11544 - Recruiter's Problem
Replies: 12
Views: 1954

Re: 11544 - Recruiter's Problem

Hi, After speeding up my BigNum, I keep get WA in 1.9 seconds. I tried many many cases and it gives the correct result. Does anyone have more tricky cases :-) ? Thanks. My setup is shown below, if you feel like reading it and finding a counter example. I keep multiplying the spacing by k and add 1, ...
by baodog
Tue Oct 28, 2008 12:29 am
Forum: Volume 115 (11500-11599)
Topic: 11521 - Compressor
Replies: 18
Views: 6008

Re: 11521 - Compressor (Wrong data)

As you can see, after the Rejudge, a completely different group of people get accepted.
In fact the contest should be rejudged as well.

Josh
by baodog
Mon Oct 27, 2008 12:08 pm
Forum: Volume 115 (11500-11599)
Topic: 11544 - Recruiter's Problem
Replies: 12
Views: 1954

Re: 11544 - Recruiter's Problem

Thanks! I can get right answer now using BigNum for cost and
multiplying the spacing by k each time going from n-1 to 0,
but getting TLE. What is your approach? Thanks!
by baodog
Mon Oct 27, 2008 2:58 am
Forum: Volume 115 (11500-11599)
Topic: 11544 - Recruiter's Problem
Replies: 12
Views: 1954

11544 - Recruiter's Problem

I keep get wa on this one. Is there some tricky i/o? I notice only 1/9 got ac on contest, and 16% on judge. Thanks. I just use max flow mincost (see below). I use 10*cand*cand*cand+pref*((n-cand)*(n-cand)+1) as the cost, where cand is candidate id-1, and pref is the order of preference for each task...
by baodog
Sun Oct 26, 2008 10:42 pm
Forum: Volume 115 (11500-11599)
Topic: 11546 - Olympic Swimming
Replies: 6
Views: 1183

Re: 11546 Olympic Swimming

Nevermind.

Go to advanced search