Search found 35 matches

by Hackson
Thu Sep 06, 2007 8:42 pm
Forum: Bugs and suggestions
Topic: New Time Limit is 1 second?
Replies: 8
Views: 3195

Same here for 10015.
It is said that time limit is 4 minutes but only 1 second is allowed.
I got a TLE then...
by Hackson
Mon Aug 27, 2007 7:06 am
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13645

OK seems nobody has idea on this problem, now I would like to post my code here and seek for any help, thanks :) #include<cstdio> #include<cstring> #include<vector> using namespace std; struct Edge{ int u, v; double w; Edge(){u=v=0;w=0;} Edge(int a, int b, double c){ u=a;v=b;w=c; } }; vector<Edge> E...
by Hackson
Fri Aug 24, 2007 6:39 am
Forum: Volume 110 (11000-11099)
Topic: 11097 - Poor My Problem! :-(
Replies: 8
Views: 5650

rammestain wrote:I've tried too solve this problem with bell-man ford but I got getting TLE.
I repeat outer loop of bell-man ford while I have a update in inner loop.
Is this true?
I solved that by DP.
Note that implementation of the graph really matters, I used adjacency list in this case. :wink:
by Hackson
Tue Aug 21, 2007 8:53 am
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13645

I got an AC code from my friend which uses binary search + warshall to solve. I generated some testdata and I found that there is an input which causes difference: 1 18 63 17 9 10 3 16 12 18 4 5 13 3 4 18 5 11 12 16 4 13 2 1 15 4 13 6 10 7 10 6 17 17 3 9 2 5 6 3 4 17 4 8 8 8 12 2 3 12 4 4 10 12 7 4 ...
by Hackson
Sat Aug 18, 2007 1:41 pm
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13645

I have tried this problem with applying Kosaraju's algorithm and Karp's algorithm without success. My algorithm is as follows: 1. use Kosaraju's algorithm and store each SCC as separate graph 2. for each SCC, run Karp's algorithm and give the min mean cycle I 've passed the test case provided from p...
by Hackson
Sun Jul 15, 2007 6:30 am
Forum: Volume 112 (11200-11299)
Topic: 11240 - Antimonotonicity
Replies: 33
Views: 12298

There can be at most 30000 numbers. Surely simple DP does not work, and you need further optimizations.
by Hackson
Sat May 05, 2007 11:34 am
Forum: Volume 1 (100-199)
Topic: 183 - Bit Maps
Replies: 15
Views: 2860

Please set the width to be 50 characters.
Try and see if you still get any WAs.
by Hackson
Mon Apr 16, 2007 10:01 am
Forum: Volume 1 (100-199)
Topic: 176 - City Navigation
Replies: 20
Views: 7827

I don't know if I am asking in the right place, but I am really confused by the problem statement (I don't understand the sample too!). Would anyone mind spending some time explaining the problem statement? Many thanks and sorry for my poor English :oops:
by Hackson
Mon Apr 09, 2007 7:07 pm
Forum: Algorithms
Topic: N-Queens and track back
Replies: 2
Views: 2107

Answers can be found in Wikipedia...
by Hackson
Tue Sep 12, 2006 3:47 pm
Forum: Volume 6 (600-699)
Topic: 612 - DNA Sorting
Replies: 122
Views: 15920

The last case should not have blank line at the end. Try it.
by Hackson
Mon May 29, 2006 5:48 pm
Forum: Volume 105 (10500-10599)
Topic: 10513 - Bangladesh Sequences
Replies: 15
Views: 8300

10513 WA and any efficient approach?

Hi, I know one way tackling this task is to calculate the non bangladesh sequences, which do not fufil all the 4 requirements. But I 've got WA all the time while I passed all the test data provided in this board... it's driving me insane :o Here comes my code: const lim : array[1..15] of char = ('A...
by Hackson
Wed May 24, 2006 6:24 pm
Forum: Volume 110 (11000-11099)
Topic: 11022 - String Factoring
Replies: 12
Views: 7089

Timo wrote:My solution is use recursive with memo and I get 0:00.051.
I think you must optimize your dp.

:D
Yep, under some but limited optimization, I got 0:00.58x.

But I 'd like to ask what you 've memoized?
Is the recursive formula same as mine?
by Hackson
Wed May 24, 2006 10:53 am
Forum: Volume 110 (11000-11099)
Topic: 11022 - String Factoring
Replies: 12
Views: 7089

it is 90% similiar to matrix chain multiplication problem :D Yes, definitely :D I 've got this problem accepted, but I think the runtime was a bit too slow. I 've tried writting it in both C++ and pascal, but well, the runtime is about 1.4~1.7sec, which is not enough to solve it for N = 380 (N=80 o...
by Hackson
Tue May 02, 2006 2:04 pm
Forum: Algorithms
Topic: Scheduling Problem?
Replies: 2
Views: 1244

One of the intervals has to contain the point 2000. Try all possibilities. Each time you have to find an optimal cover for [0, beginning of the chosen interval]. Thanks for your idea. But what if [a, b] such that a >= b? e.g. [1999, 5] would contain {1999, 2000, 0, 1, 2, 3, 4, 5} under a cycling se...
by Hackson
Mon May 01, 2006 2:42 pm
Forum: Algorithms
Topic: Scheduling Problem?
Replies: 2
Views: 1244

Scheduling Problem?

Suppose we have N sets of integers. Each set of integers is represented by [A, B], a closed interval of integers such that A <= B. Find the minimum number of sets such that those sets can cover [L, H], where 0<=L<=H<=2000, note that the selected sets can be overlapped. Is it a DP problem? I can't fi...

Go to advanced search