OJ Board

emotional blind wrote:hint: I solved it using O(n*k) algorithm.

Care to share your method?

The complexity of the algorithm is O(n) as you only need to go thru the string once followed by going thru the map once. Hope this helps.

but access map and insertion in map will cost O(logn), Sor your algorithm is not O(n) it is O(nlogn).

Thanks for pointing that out. But the STL has optimised ...

Hi Guys, I got my solution accepted with run time of 2.830 seconds so it's not extremely fast but it's not bad.

I can see that there are lots of ideas came up in the discussion but I solved this problem just by brute force using substring function and a map (I coded in C++).

Say for string ...

The input that I have created includes cases of
9 24
9 25
10 24
10 25

So I think they should cover al of the extrem cases right???

Is there any special cases that I have missed out on?

Thanks for the quick reply!

I got the same answers as you but got judged as WA......

the input handling case is easy

int n, d;
cin >> n >> d;
while (n != 0 || d != 0)
{
printf("%0.0Lf\n", pow((long double) n, d));
cin >> n >> d;
}

Can anyone think of how else could I get it wrong? It's ...

Is this problem meant to be easy? As I keep getting WA! I am not too sure if it's because of the precision or my logic is wrong

I use the following to output the answer, is that correct?

printf("%0.0Lf\n", pow((long double) n, d));

Can anyone provide sample output for the following cases by any ...

Tanu, like Fixxxer said, next_permutation will do your trick. However, it may be a bit slow depending on what you need to do.

Furthermore, should you be trying to solve an ACM problem, it would be helpful to tell us the problem number so that we can look at the spec.

If you want to check if two words s1, s2 are anagrams,

perform sorting on both s1 and s2 in term of the characters. If the result of both strings are the same, then they are anagrams =)

Thanks. That will be much more efficient then my current implementation.

However, now I am getting Memory Limit Exceeded. Would anyone have some suggestion? The following is my memory usage:

typedef vector <map <int, int> > VMII;
typedef vector <int> VI;

int profit(VMII& graph)
{
int road = 0 ...

Hi There,

I am trying to solve 3283 by using DFS n times which means my algorithm is O(n ^ 2). However, I get timed out, does anyone have a suggestion on how to solve this problem efficiently?

http://acmicpc-live-archive.uva.es/nuev ... php?p=3283

Thanks

Just a note that for C++ users, use double but NOT float

Hi All

I think I have a problem of understanding the output. Can anyone help?

For the second sample input

15.0 270.0 135.0 200.0

We have the following diagram

15 (wind)
---->
\
\ 200 (plane relative to air)
\

Since we know the velocity of plane relative to ground = velocity of plane ...

I have tried different methods and I still got TLE

Would someone be able to inform me some quicker way of solving this problem?



#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); i++)

string line;
int cases = 1 ...

Hi

Would anyone be able to help me out on this? I have got the following error message with the online judge but not on my own computer.

Thanks



#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOREACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); i++)

bool palinword ...

Just would like to let you know that in the actual competition, the last line in the output does not matter. You will still get accepted.