## Search found 35 matches

Thu Sep 06, 2007 8:42 pm
Forum: Bugs and suggestions
Topic: New Time Limit is 1 second?
Replies: 8
Views: 3250
Same here for 10015.
It is said that time limit is 4 minutes but only 1 second is allowed.
I got a TLE then...
Mon Aug 27, 2007 7:06 am
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13789
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...
Fri Aug 24, 2007 6:39 am
Forum: Volume 110 (11000-11099)
Topic: 11097 - Poor My Problem! :-(
Replies: 8
Views: 5691
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.
Tue Aug 21, 2007 8:53 am
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13789
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 ...
Sat Aug 18, 2007 1:41 pm
Forum: Volume 110 (11000-11099)
Topic: 11090 - Going in Cycle!!
Replies: 23
Views: 13789
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...
Sun Jul 15, 2007 6:30 am
Forum: Volume 112 (11200-11299)
Topic: 11240 - Antimonotonicity
Replies: 33
Views: 12574
There can be at most 30000 numbers. Surely simple DP does not work, and you need further optimizations.
Sat May 05, 2007 11:34 am
Forum: Volume 1 (100-199)
Topic: 183 - Bit Maps
Replies: 15
Views: 3026
Please set the width to be 50 characters.
Try and see if you still get any WAs.
Mon Apr 16, 2007 10:01 am
Forum: Volume 1 (100-199)
Replies: 20
Views: 7941
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
Mon Apr 09, 2007 7:07 pm
Forum: Algorithms
Topic: N-Queens and track back
Replies: 2
Views: 2134
Answers can be found in Wikipedia...
Tue Sep 12, 2006 3:47 pm
Forum: Volume 6 (600-699)
Topic: 612 - DNA Sorting
Replies: 122
Views: 16791
The last case should not have blank line at the end. Try it.
Mon May 29, 2006 5:48 pm
Forum: Volume 105 (10500-10599)
Replies: 15
Views: 8392

### 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...
Wed May 24, 2006 6:24 pm
Forum: Volume 110 (11000-11099)
Topic: 11022 - String Factoring
Replies: 12
Views: 7182
Timo wrote:My solution is use recursive with memo and I get 0:00.051.
I think you must optimize your dp.

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?
Wed May 24, 2006 10:53 am
Forum: Volume 110 (11000-11099)
Topic: 11022 - String Factoring
Replies: 12
Views: 7182
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...
Tue May 02, 2006 2:04 pm
Forum: Algorithms
Topic: Scheduling Problem?
Replies: 2
Views: 1256
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...
Mon May 01, 2006 2:42 pm
Forum: Algorithms
Topic: Scheduling Problem?
Replies: 2
Views: 1256

### 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...