Search found 14 matches

by Nak
Sat Jun 14, 2003 10:38 am
Forum: Volume 105 (10500-10599)
Topic: 10509 - R U Kidding Mr. Feynman?
Replies: 41
Views: 13301

That's the same formula i used and got AC. I calculated a as:

[cpp]
double a = floor(pow(cube, 1.0/3.0)+0.0000000001);
[/cpp]
by Nak
Mon Jun 09, 2003 11:03 am
Forum: Volume 104 (10400-10499)
Topic: 10498 - Happiness
Replies: 18
Views: 9502

Consider buying 0 of item 1, 100 of item 2, 230 of item 3 (per person).

This does not violate any constraints, giving the total cost 1353.3, which rounds up to 1354.
by Nak
Sat May 31, 2003 2:33 am
Forum: Algorithms
Topic: Find the number of a sequence, and backwards...
Replies: 10
Views: 3447

Maybe guessing is the wrong word for 10460, but you should at least build up the solution step by step, each time dividing a sequence into it's building blocks.
by Nak
Sat May 31, 2003 2:22 am
Forum: Algorithms
Topic: Find the number of a sequence, and backwards...
Replies: 10
Views: 3447

A technique that often works with these kinds of problems is to try to identify some kind of structure in the sequence and search step by step closer to the object. Assume you are going from number to object. For example if you know the sequence of objects is divided in 26 parts (which is often the ...
by Nak
Tue May 27, 2003 2:55 am
Forum: Volume 104 (10400-10499)
Topic: 10495 - Conic Distance
Replies: 16
Views: 6292

Basic high school math is enough.
If you get TLE, maybe you're not reading input correctly?
by Nak
Tue May 06, 2003 4:20 am
Forum: Volume 104 (10400-10499)
Topic: 10453 - Make Palindrome
Replies: 38
Views: 15029

I think the easiest method is to make a function which takes a string and two indices as arguments (start and end index of a substring). Since these indices will both be smaller than 1000 you can make a memo-table which is 1000*1000 elements large and store values from old function calls. Then you p...
by Nak
Tue May 06, 2003 3:54 am
Forum: Volume 104 (10400-10499)
Topic: 10453 - Make Palindrome
Replies: 38
Views: 15029

I used dynamic programming to solve this. Let f(s) be the shortest palindrome created from the string s. There are two cases: If the first and last character of s is the same, say s=a[...]a, then f(s) = af([...])a Otherwise, say s=a[...]b, then f(s) = af([...]b)a or bf(a[...])b, whichever is shorter...
by Nak
Wed Mar 26, 2003 10:37 am
Forum: Algorithms
Topic: A*?
Replies: 3
Views: 2429

A* uses a heuristic to guide it's search. The only difference is what value you use for nodes on the priority queue. In Dijkstra you order nodes with their distance from the start node. In A* you simply add a heuristic value which estimates the distance from the current node to the goal. This way th...
by Nak
Sun Mar 16, 2003 4:33 am
Forum: Volume 103 (10300-10399)
Topic: 10330 - Power Transmission
Replies: 43
Views: 15730

I build the same graph as you and use Edmonds-Karp's algorithm. It only takes 0.273 seconds, perhaps you have an infinite loop or something?
by Nak
Sat Mar 01, 2003 3:21 am
Forum: Algorithms
Topic: Min-Max Heap
Replies: 2
Views: 2527

The "classic" min-max heap is a bit more tricky to implement, but uses less memory than two heaps. The idea is to divide the heaps in to levels where the "interleaved" heaps are partially ordered like a normal heap. The elements on even levels should always be smaller than their descendants, and the...
by Nak
Sun Dec 15, 2002 11:55 am
Forum: Volume 100 (10000-10099)
Topic: 10043 - Chainsaw Massacre
Replies: 18
Views: 6949

Incorrect testdata?

I think the testdata in this problem is incorrect :-(

My assert(n_trees <= 1000); fails, without it i get accepted.
by Nak
Fri Nov 08, 2002 1:11 pm
Forum: Volume 103 (10300-10399)
Topic: 10397 - Connect the Campus
Replies: 75
Views: 25280

Did you consider a disconnected input graph?

Input:

4
0 0
0 1
1 0
1 1
2
1 2
3 4

Output should be 1.00
by Nak
Wed Nov 06, 2002 9:20 pm
Forum: Volume 103 (10300-10399)
Topic: 10399 - Optimus Prime
Replies: 14
Views: 5105

Well yes, if there is no prime between c and c+n there is no such number and hence you loose. I admit I assumed c would not get bigger than 1000000. And yes i did get AC, perhaps i was just lucky :D
by Nak
Wed Nov 06, 2002 8:44 pm
Forum: Volume 103 (10300-10399)
Topic: 10399 - Optimus Prime
Replies: 14
Views: 5105

I used dynamic programming to solve this problem. Perhaps not the fastest way but it worked. A situation with some c and n is a winning situation if there is a number i between 1 and n so that c+i is prime and the situation with the counter = c+i is _not_ a winning situation, if there is no such num...

Go to advanced search