Search found 24 matches

by kenneth
Tue Mar 25, 2008 7:17 am
Forum: Volume 9 (900-999)
Topic: 902 - Password Search
Replies: 68
Views: 32498

emotional blind wrote:hint: I solved it using O(n*k) algorithm.
Care to share your method?
by kenneth
Fri Mar 21, 2008 4:11 am
Forum: Volume 9 (900-999)
Topic: 902 - Password Search
Replies: 68
Views: 32498

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 tha...
by kenneth
Thu Mar 20, 2008 4:08 pm
Forum: Volume 9 (900-999)
Topic: 902 - Password Search
Replies: 68
Views: 32498

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 "baababac...
by kenneth
Tue Oct 10, 2006 4:51 am
Forum: Volume 111 (11100-11199)
Topic: 11115 - Uncle Jack
Replies: 25
Views: 15985

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?
by kenneth
Tue Oct 10, 2006 3:02 am
Forum: Volume 111 (11100-11199)
Topic: 11115 - Uncle Jack
Replies: 25
Views: 15985

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 driving me nu...
by kenneth
Tue Oct 10, 2006 2:18 am
Forum: Volume 111 (11100-11199)
Topic: 11115 - Uncle Jack
Replies: 25
Views: 15985

11115 - Uncle Jack

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 chan...
by kenneth
Thu Nov 03, 2005 3:39 pm
Forum: Algorithms
Topic: Anagram
Replies: 7
Views: 2294

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.
by kenneth
Sat Oct 15, 2005 12:16 pm
Forum: Algorithms
Topic: Anagram
Replies: 7
Views: 2294

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 =)
by kenneth
Sat Oct 01, 2005 5:06 am
Forum: ACM ICPC Archive Board
Topic: 3283 Path
Replies: 2
Views: 1130

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; VI ma...
by kenneth
Thu Sep 29, 2005 3:00 pm
Forum: ACM ICPC Archive Board
Topic: 3283 Path
Replies: 2
Views: 1130

3283 Path

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
by kenneth
Tue Sep 13, 2005 8:30 am
Forum: Volume 102 (10200-10299)
Topic: 10242 - Fourth Point !!
Replies: 30
Views: 12522

Just a note that for C++ users, use double but NOT float
by kenneth
Sat Sep 10, 2005 5:22 pm
Forum: Volume 2 (200-299)
Topic: 267 - Of(f) Course!
Replies: 16
Views: 2476

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 relative to wind...
by kenneth
Fri Sep 09, 2005 5:57 pm
Forum: Volume 4 (400-499)
Topic: 467 - Synching Signals
Replies: 16
Views: 6054

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; while (ge...
by kenneth
Fri Sep 09, 2005 1:23 pm
Forum: Volume 2 (200-299)
Topic: 257 - Palinwords
Replies: 16
Views: 5700

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(string...
by kenneth
Sat Sep 03, 2005 3:25 pm
Forum: Volume 7 (700-799)
Topic: 729 - The Hamming Distance Problem
Replies: 54
Views: 15837

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.

Go to advanced search