OJ Board

WORD w[100000];
why is that array only 100000 big ?


It's not neccesary to check out anymore !!!! Your observation is correct and exact, thanks !!!!!

I increased length of array to 400000, and it was accepted :D.

I didn't expect to have any wrong answer, because of using less memory than ...

Next code was the first one i submitted :D

All later submissions are very similar.

#include <stdio.h>

int v[8][2] = {{-1,-1}, {-1,0}, {-1,1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

typedef struct {
int cont;
int isfinal;
int letter[26];
} WORD;

char map[101][101];
char words[15000][101 ...

thanks angga888, but i'm still getting wrong answer :(.

can anyone post their code of reading test cases of this problem, please ???

I've thought about no printable characters in map.

problem is case sensitive ???

Thanks in advance.

Maybe my algo is wrong :cry: . But i have faith in my code ...

Is there any special trick for this problem ???

What should be the correct answer for this input

Sample Input

1
4
a
a
bb
bbb
3
3 3
aaa
aaa
aaa
3 3
bbb
bbb
bbb
3 3
ccc
ccc
ccc

My Output

Test Case #1
Query #1
a 9
a 9
Query #2
bb 40
bbb 16
Query #3

Any commenting or suggesting will be pleased

Your assumption that the number of edges in such a graph is less than 3*V is wrong

I have to accept you are allright. Very nice sample. When i solved this problem, i was thinking what was the worst case for number of triangules :D. Well, at least my algo runs on time. I didn't expect such a case ...

me neither.

I just calculated by frute force with some optimizations. My algo depends on number of vertices. Since there isnt any edge into more than 2 triangles, you know there is no more edges than 3 times number of nodes. In general, it's better an algo O(3n*k) than O(n^2 * k).

Almost all of you are talking about fibonacci numbers.

I found a formula that looks like: f(n) = c1 * f(n - 1) + f1(n-2);
where f1 and f are functions totally diferent. But both depend on each other.

I got it, using simple reasoning. Suppose we have all ways for connecting n - 1 houses. Let's try ...

shamim wrote:I was trying my luck

Me too. At least, during online contest .

I dont know if a case exists where previous method doesn't find a solution. I think it's ok. Why?? I don't know how to explain it.

Wow :o , nice solution.

I solved this problem using brute force (Until now, without any optimization)

Main idea is:

Let X = Xn Xn-1 ... X1 be solution in base B.

We start in this way:

Define Yi(X1) as the most left digit of X1 * i in base B, then Yi(X1) = (X*i) % B;

If there is a solution ...

A g-Gap is defined as a string in the form UVU such that |V| = g.

For example: AALLAA is a 2-Gap taking U = AA and V = LL .
furthermore is 4-GAP because of U = A and V = ALLA and |V| = 4,
finally is not a 6-GAP, because U can not be empty.

The problem consists in given a string S , and a positive ...

My programs runs is O(n^3) best case and O(n^4) in worst case.

It runs in 1.059 seconds.

Can anybody explain any O (n^3) solution ???


the circular can be solved by substracting the total of that column with minimum sum between row 1..n-2 -> therefore O(n^3)

Maybe I am not a good english ...

Any hint for solving this problem ??

In the worst case (a string with 50,000 same character), the solution is greater than 500,000,000 L-GAP. O.K. We can manage that case.

I think, even using KMP's algrithm is not possible count all L-GAPs in time

Please, help.

technobug wrote:How fast is your D+C algorithm? What is its idea?

My original program runs in 1.150 seconds

Main idea was already posted by Eduard

I've managed for optimization, and now runs in 0.771. Showing that scanf is slow.

I'm not sure if your algorithm is fast. In order to count the minimun number of swaps, you should use a 64-bit integer, because of in the worst case [ 500000, 499999, 499998, .... , 1 ] you need (500,000) * (499,999) / 2 swaps and that number doesn't fit into a 32-bit integer.

My implementation use ...

Hi:

my output is

166 14
728 23
0 0
23 23
850 77