Search found 15 matches

by filigabriel
Wed Nov 23, 2005 8:38 am
Forum: Volume 109 (10900-10999)
Topic: 10975 - Dueue's Quiz
Replies: 39
Views: 16236

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 required. I...
by filigabriel
Tue Nov 15, 2005 5:59 pm
Forum: Volume 109 (10900-10999)
Topic: 10975 - Dueue's Quiz
Replies: 39
Views: 16236

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]; WORD w[...
by filigabriel
Mon Nov 14, 2005 9:50 am
Forum: Volume 109 (10900-10999)
Topic: 10975 - Dueue's Quiz
Replies: 39
Views: 16236

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 and algo...
by filigabriel
Sat Nov 12, 2005 6:43 pm
Forum: Volume 109 (10900-10999)
Topic: 10975 - Dueue's Quiz
Replies: 39
Views: 16236

10975 - Dueue's Quiz

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 :D
by filigabriel
Sat Nov 12, 2005 5:18 pm
Forum: Volume 109 (10900-10999)
Topic: 10973 - Triangle Counting
Replies: 31
Views: 13046

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. T...
by filigabriel
Sat Nov 12, 2005 8:51 am
Forum: Volume 109 (10900-10999)
Topic: 10973 - Triangle Counting
Replies: 31
Views: 13046

me neither.

I just calculated by frute force :D 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).
by filigabriel
Thu Jun 02, 2005 9:43 pm
Forum: Volume 108 (10800-10899)
Topic: 10862 - Connect the Cable Wires
Replies: 14
Views: 7900

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 to...
by filigabriel
Tue Mar 22, 2005 8:49 am
Forum: Volume 108 (10800-10899)
Topic: 10825 - Anagram and Multiplication
Replies: 18
Views: 7827

shamim wrote:I was trying my luck
Me too. At least, during online contest :D.

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.
by filigabriel
Tue Mar 15, 2005 4:02 am
Forum: Volume 108 (10800-10899)
Topic: 10825 - Anagram and Multiplication
Replies: 18
Views: 7827

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. Then it h...
by filigabriel
Sat Mar 12, 2005 9:07 pm
Forum: Volume 108 (10800-10899)
Topic: 10829 - L-Gap Substrings
Replies: 14
Views: 9277

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 in...
by filigabriel
Tue Mar 08, 2005 2:20 pm
Forum: Volume 108 (10800-10899)
Topic: 10827 - Maximum sum on a torus
Replies: 52
Views: 26844

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 reader, but ...
by filigabriel
Tue Mar 08, 2005 12:33 pm
Forum: Volume 108 (10800-10899)
Topic: 10829 - L-Gap Substrings
Replies: 14
Views: 9277

10829 - L-Gap Substrings

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.
by filigabriel
Wed Feb 09, 2005 7:50 am
Forum: Volume 108 (10800-10899)
Topic: 10810 - Ultra-QuickSort
Replies: 36
Views: 20452

technobug wrote:How fast is your D+C algorithm? What is its idea?
My original program runs 8) in 1.150 seconds

Main idea was already posted by Eduard :D

I've managed for optimization, and now runs in 0.771. Showing that scanf is slow.
by filigabriel
Tue Feb 08, 2005 12:44 am
Forum: Volume 108 (10800-10899)
Topic: 10810 - Ultra-QuickSort
Replies: 36
Views: 20452

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 ...
by filigabriel
Tue May 25, 2004 9:14 pm
Forum: Volume 106 (10600-10699)
Topic: 10603 - Fill
Replies: 19
Views: 8464

Hi:

my output is

166 14
728 23
0 0
23 23
850 77

Go to advanced search