## Search found 158 matches

Fri Apr 13, 2012 11:08 pm
Forum: Volume 113 (11300-11399)
Topic: 11334 - Antenna in the Cinoc Mountains
Replies: 6
Views: 3891

### Re: 11334 - Antenna in the Cinoc Mountains

I haven't been able to get Accepted yet, but with assertions I discovered the following: Can a tower stand on a mountain? Yes. The first sample test case shows this. If a tower can stand on a mountain, should the height of the top be added to the height of the mountain at that point? No. You are giv...
Tue Feb 17, 2009 8:05 pm
Forum: Volume 115 (11500-11599)
Topic: 11572 - Unique Snowflakes
Replies: 36
Views: 11936

### Re: 11572 - Unique Snowflakes

f74956227 wrote:Hey! i got AC use a O(nlogn) algorithm.. i want to know if there is a O(N) algorithm for solving this problem ?
I solved it in O(n log n) too. It runs in ~0.7 seconds, but Rio solved it in 0.09 seconds, which makes me believe an O(n) solution does exist.
Tue Nov 25, 2008 9:51 pm
Forum: Volume 100 (10000-10099)
Topic: 10090 - Marbles
Replies: 43
Views: 21913

### Re: 10090 - Marbles

I'm getting Wrong Answer. My code passes all output in the forum. Please help me find the bug: using namespace std; #include <cstdio> #include <cassert> #include <algorithm> long long get_gcd(long long a, long long b, long long &x, long long &y){ if (b > a) return get_gcd(b, a, y, x); if (b == 0){ x...
Tue Nov 18, 2008 5:17 pm
Forum: Algorithms
Replies: 1
Views: 915

Tue Nov 18, 2008 4:59 pm
Forum: Volume 113 (11300-11399)
Topic: 11367 - Full Tank?
Replies: 13
Views: 7751

### Re: 11367 - Full tank?

Imagine you build a graph where each node is a pair of integers; let's call them where and fuel . So, if we reach a node <where, fuel> in this new graph, it means that we can reach node "where" from the original graph in such a way that we have exactly "fuel" units of fuel in our tank at the moment ...
Tue Nov 18, 2008 5:51 am
Forum: Volume 113 (11300-11399)
Topic: 11367 - Full Tank?
Replies: 13
Views: 7751

### Re: 11367 - Full tank?

I solved it using Dijkstra's algorithm. But your state must contain the amount of fuel that you currently have in the tank.
Mon Oct 27, 2008 4:06 pm
Forum: Volume 115 (11500-11599)
Topic: 11536 - Smallest Sub-Array
Replies: 9
Views: 1894

### Re: 11536 - Smallest Sub-Array

I can't solve this. Give me some hint please.
Fri Oct 24, 2008 10:35 pm
Forum: Volume 104 (10400-10499)
Topic: 10469 - To Carry or not to Carry
Replies: 24
Views: 10035

### Re: 10469 - To Carry or not to Carry

You are over complicating the problem.

Study the bitwise XOR operator.
Wed Oct 22, 2008 4:03 pm
Forum: Volume 115 (11500-11599)
Topic: 11504 - Dominos
Replies: 55
Views: 19806

### Re: 11504 - Dominos

Reduce the original graph to a DAG where each new node corresponds to a strongly connected component of the old graph.
Tue Oct 21, 2008 6:05 am
Forum: Volume 115 (11500-11599)
Topic: 11504 - Dominos
Replies: 55
Views: 19806

### Re: 11504 - Dominos

Try this case:

Code: Select all

``````1
4 5
1 2
2 1
3 2
3 4
4 3
``````
Correct output is 1 (Tile #4), but your code outputs 2.
Sun Oct 19, 2008 12:46 am
Forum: Volume 115 (11500-11599)
Topic: 11504 - Dominos
Replies: 55
Views: 19806

### Re: 11504 - Dominos

It may fail in some cases. For example, if you have the following graph: 3 nodes and these directed edges: <1, 2> <2, 1> and <3, 2> If you start the DFS at node 1 you will visit nodes 1 and 2. Then you will also knockdown tile 3, with total score 2 (Tiles 1 and 3). But the best solution is to just k...
Sat Oct 04, 2008 10:43 pm
Forum: Volume 115 (11500-11599)
Topic: 11516 - WiFi
Replies: 4
Views: 3185

### 11516 - WiFi

I don't know hot to solve this problem. Please give me a hint. Thanks.
Sat Oct 04, 2008 6:09 pm
Forum: Volume 115 (11500-11599)
Topic: 11509 - Touring Robot
Replies: 8
Views: 1743

### Re: 11509 - Touring Robot

Try these cases: 3 -10 -2 4 -6 1 7 9 7 9 2 10 -5 4 0 -3 10 10 -7 7 2 -7 -4 0 4 7 4 -6 2 6 5 -7 4 3 9 5 -4 0 -9 0 1 6 7 4 3 -2 10 7 8 -8 4 9 -9 3 -7 -7 -7 8 -1 7 0 10 9 -2 -3 -3 -2 6 10 0 -10 -10 0 -10 -6 -10 9 -3 -2 -7 7 4 -1 -4 6 -8 -7 9 1 -8 0 -4 -2 6 -9 3 -3 -8 -9 0 -8 4 5 7 2 -7 -2 3 8 1 0 0 0 5...
Sat Oct 04, 2008 5:54 pm
Forum: Volume 115 (11500-11599)
Topic: 11511 - Frieze Patterns
Replies: 2
Views: 749

### Re: 11514 - Frieze Patterns

I have tried too to prove it without success.

What I did in my code was build the table for the first N+1 rows like this:

Code: Select all

``````f[i][j] = ( f[i+1][j-1] * f[i-1][j] + 1 ) / f[i][j-1];
``````
So we need to prove that

Code: Select all

``````f[i][j] = f[i][j-N-1] for all j > N + 1
``````
Does anyone have some idea?
Fri Oct 03, 2008 3:35 pm
Forum: Volume 115 (11500-11599)
Topic: 11509 - Touring Robot
Replies: 8
Views: 1743

### Re: 11509 - Touring Robot

How are you calculating angles? I used atan2 and doubles for the calculations and then print the answer like this (without rounding):

Code: Select all

``````printf("%.0lf\n", ans/(2*pi));
``````