Search found 100 matches

by DJWS
Wed Aug 20, 2008 6:03 am
Forum: Bugs and suggestions
Topic: 193 - Graph Coloring(Solved)
Replies: 3
Views: 2369

Re: 193 - Graph Coloring

The code will lead to memory leaking.
by DJWS
Mon Jul 21, 2008 5:14 am
Forum: Algorithms
Topic: Transitive Closure Problems in UVa Online Judge
Replies: 2
Views: 1068

Re: Transitive Closure Problems in UVa Online Judge

Thank you, mf. It is an interesting problem. :D
by DJWS
Thu Jul 17, 2008 5:47 am
Forum: Algorithms
Topic: Transitive Closure Problems in UVa Online Judge
Replies: 2
Views: 1068

Transitive Closure Problems in UVa Online Judge

Hi,

Is there any transitive closure problem in UVa Online Judge? I need collect some transitive closure problems as exercise problems. :wink:
by DJWS
Sat Jun 14, 2008 4:52 am
Forum: Other words
Topic: What is the name of this kind of DP problems?
Replies: 3
Views: 2494

Re: What is the name of this kind of DP problems?

Finally I found 662 is called 'p-median problem' after googling around 3 hours. It belongs to the 'location-allocation problem.' The p-median problem is a well-known NP problem (but not for me :wink: ). There are many approaches to solve it, for example, integer programming. There are also many vari...
by DJWS
Fri Jun 13, 2008 11:12 am
Forum: Other words
Topic: What is the name of this kind of DP problems?
Replies: 3
Views: 2494

Re: What is the name of this kind of DP problems?

I think MCM is 348 or 442 instead.

In 714, 907, and 662, we make k partitions of a given sequence and minimize the maximal partition.
We can use DP, optimized DP, or binary search to solve this kind of problems.
That is special. Thus I wonder if a formal and unique name exists.
by DJWS
Fri Jun 13, 2008 6:41 am
Forum: Other words
Topic: What is the name of this kind of DP problems?
Replies: 3
Views: 2494

What is the name of this kind of DP problems?

Hi,

I found some similar dynamic programming problems: 714, 907, 662.
Is there a formal name for this kind of problems?
by DJWS
Wed Jun 11, 2008 9:10 am
Forum: Volume 108 (10800-10899)
Topic: 10888 - Warehouse
Replies: 19
Views: 12401

Re:

There are a situation that some X may not be matched to every B. So you should exam your cost list that shouldn't exist strange numbers. Hope that help you~ I made assertions in my code and I found the # of B is equal to the # of X. The problem statement does not mention the equality so we can not ...
by DJWS
Mon Jun 09, 2008 3:18 pm
Forum: Volume 101 (10100-10199)
Topic: 10101 - Bangla Numbers
Replies: 122
Views: 28052

Re: 10101 - Bangla Numbers

Okay. Think about the expression of a Bangla number. See what is before 'kuti' and what is after 'kuti.'
Try to keep your code clean and short, with a simple recursion. :wink:

BTW, 999999999999999 can be stored in a 'long long int'-type variable.
by DJWS
Mon Jun 09, 2008 8:49 am
Forum: Volume 101 (10100-10199)
Topic: 10101 - Bangla Numbers
Replies: 122
Views: 28052

Re: 10101 - Bangla Numbers

You can solve this problem with the Divide and Conquer approach.
by DJWS
Mon Jun 09, 2008 8:43 am
Forum: Volume 8 (800-899)
Topic: 833 - Water Falls
Replies: 5
Views: 3543

833 - Water Falls

I found the weakness of current datasets. In this case: 1 2 1 4 5 1 3 3 6 2 1 4 4 The answer should be 6, not 5. However my accepted code outputs 5. In my code, I sort all segments by their maximal height. And then determine if the source flows onto the segments in the sorted sequence. This algorith...
by DJWS
Thu Jun 05, 2008 7:21 am
Forum: Volume 101 (10100-10199)
Topic: 10135 - Herding Frosh
Replies: 33
Views: 12843

I generate some test cases, please help verify them. :)

Code: Select all

10
0
1
0 0
1
1 1
2
0 1
0 2
2
0 -1
0 1
3
0 -1
0 0
0 1
3
0 0
0 1
0 2
3
0 -1
0 0
0 1
4
0 -2
0 -1
0 1
0 2
4
1 0
-1 0
0 1
0 -1
by DJWS
Sat May 31, 2008 9:33 am
Forum: Volume 101 (10100-10199)
Topic: 10135 - Herding Frosh
Replies: 33
Views: 12843

I just see only few people who have solved this problem, however I think this problem it's not so hard. I have thought of a simple algorithm. If I miss something, please point out. My algorithm is very simple. Just sort all points by their angles in polar coordinate system. Next, try to wrap all poi...
by DJWS
Fri May 30, 2008 1:15 pm
Forum: Volume 106 (10600-10699)
Topic: 10673 - Play with Floor and Ceil
Replies: 11
Views: 6708

In this problem you need not to find all possible solutions, but only one of them. Thus you can make a simple assumption, e.g. "p equals zero", and make the things simpler. See if the assumption is reasonable. If reasonable, that is a solution. In addition, Modular can be used if you need to analysi...
by DJWS
Fri May 30, 2008 12:58 pm
Forum: Volume 4 (400-499)
Topic: 488 - Triangle Wave
Replies: 270
Views: 31111

Re: 488 TLE

Finally got AC, thanks But I want to know why the following can make my program run faster: 1. What's the difference between "endl" and "\n"? 2. What's the difference between "cin and cout" and "scanf and printf"? 3. Why "cin.sync_with_stdio(false);" and "cout.sync_with_stdio(false);" can make my p...

Go to advanced search