OJ Board

the judge is back again!

Any official statement of the system's administration regarding when it will be working back again?

Hi people,
I'm trying to solve this problem and it appears to be NP (dominating seT). I've implemented a recursive solution using backtracking, but it is giving time limit.
Anyone could help?
Regards!

Exactly. Prim's MCST does not work. For those wanting to see a BS solution, look at Waterloo.
Regards...

Here's a counterexample to Prim.

1
3 6
0 1
0 2
0 4
0 5
0 7
0 8

The output should be 1, but Prim will give 2.

Let's say you start with 0,1. You will connect it to 0,2. Then the closest point ...

You could find a description at http://www.delphiforfun.org/Programs/15puzzle_2.htm or at AIMA
Regards!

Hi, uzioriluzan:
You would like this web page: "http://mathworld.wolfram.com/15Puzzle.html".
By the way, could you briefly introduce the heuristic method to me? :wink:
Thanks in advance.

The MCST does not solve this problem. It appears as if you did so.

I first compute the distance and add a corresponding edge between each pair of outposts. That is, I construct an undirected graph where edge weights are those distances.
Then I apply Kruskal algorithm until P-S edges are added and ...

This is a problem from Waterloo. Maybe you could find something helpful there.
Regards!

I don't know why I always recieve WA . :cry:
Could someone give me some data?
thanks!! :)


Here is my code :

//@BEGIN_OF_SOURCE_CODE
#include <stdio.h>
void main(){
char array[25];

int i=0;
int ...

maybe this has already been answered, but there is the
http://www.ioiforum.org

Archangel wrote:Does anybody know any other ACM forum ??

try using pi = acos(-1). Also there is no a>360 in the input. What happens if a > 180? Try using cos instead of sin to determine chord.
Regards!


#include<iostream.h>
#include<math.h>
#include<stdio.h>
#define pi 3.1415926535897932384626433832795
void main()
{
double arc,chord;
char ch[4];
long ...

Hi, how can I use this information? I've implemented A* with the Manhattan Distance heuristic and it still gives time limit.
Your help is welcome :)
Regards!

Read description for problem 652. Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable ...

Is there any trick with this problem? Does anyone have an interesting input?
Thanks a lot!

Picard wrote:i've solved it generaly (i still think the problem description allow longer minimal pathes), but now i checked the judge's input and found no minimal path longer as width+height-2

Where can you find judge's input? Have u got the input for problem 827 - Buddy Memory Allocator, too?

Thanks a lot!

you must use long long. but the initial value for C must be the minimum of the vector, not 2.

I don't understand why I'm getting WA here. The problem desc. says exactly what to do and it works on all the input i've tried. Can anyone see the problem? (I know my split function is fine, and i added ...

Hi all! What's the idea behind the dynamic programming?
Thanx a lot! :D

My solution worked with an array with 100000 elements. So there are no more than 100000 parts in the input.
But how do you store the used solutions? I think this is your problem. I used another array of 100000 elements to ...

How could we solve it in O(length(s))? What's is the time complexity of your algorithm?
Thanx!