OJ Board

Same here for 10015.
It is said that time limit is 4 minutes but only 1 second is allowed.
I got a TLE then...

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

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.

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

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

There can be at most 30000 numbers. Surely simple DP does not work, and you need further optimizations.

Please set the width to be 50 characters.
Try and see if you still get any WAs.

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

Answers can be found in Wikipedia...

The last case should not have blank line at the end. Try it.

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

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?

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

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

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