## Search found 158 matches

Sun Jul 20, 2008 4:40 am
Forum: Volume 113 (11300-11399)
Topic: 11367 - Full Tank?
Replies: 13
Views: 8083

### Re: 11367 - Full tank?

OK, I've optimized and got accepted. Just in case anyone cares, the observation is that if you are in state <i, g> you have two choices: -> For every neighbor j of i you can go to state <j, g - distance(i, j)> spending no extra money and only if g - distance(i, j) > 0, that is, if you have enough fu...
Mon Jul 14, 2008 12:54 am
Forum: Volume 114 (11400-11499)
Topic: 11465 - Count the Polygons
Replies: 4
Views: 1263

### Re: 11465 - Count the polygons

Can you describe the algorithm in more detail? I still don't know how to solve it. Thanks.

By the way, nice problem Sohel.
Sun Jul 13, 2008 5:31 am
Forum: Volume 104 (10400-10499)
Topic: 10446 - The Marriage Interview :-)
Replies: 17
Views: 9634

### Re: 10446 - The Marriage Interview ;-)

Input is terminated by a case where the value of n is greater than 60. This line should not be processed.
Paradoxically, this is explained in the output specification. And yes, your output of 60 60 is correct.
Sun Jul 13, 2008 5:08 am
Forum: Volume 113 (11300-11399)
Topic: 11367 - Full Tank?
Replies: 13
Views: 8083

### 11367 - Full Tank?

Hi, I tried the problem using Dijkstra's algorithm but I get Time Limit Exceeded. My state is <i, g> which means I can reach node i having g units of fuel in my tank. I do a STL priority_queue search. Is there a possible optimization or must I change my approach (DP maybe)? Thanks a lot for the help...
Sat Jul 12, 2008 11:34 pm
Forum: Volume 114 (11400-11499)
Topic: 11466 - Largest Prime Divisor
Replies: 29
Views: 15687

### Re: 11466 - Largest Prime Divisor

Also, I was getting Time Limit Exceeded. I got Accepted when I memoized input numbers so I wouldn't have to calculate any result more than once.
Sat Jul 12, 2008 10:43 pm
Forum: Volume 114 (11400-11499)
Topic: 11465 - Count the Polygons
Replies: 4
Views: 1263

### 11465 - Count the Polygons

I think this problem is solvable by DP. During the contest I thought about this state: dp [j] = Numbers of ways I can select some subset of the first i edges such that their sum is >= j, but it is extremely big to memoize..., would need about 4 gigabytes of memory ;). Any advice on how to solve this...
Wed Jun 25, 2008 12:54 am
Forum: Java
Topic: Need Help Using Scanner
Replies: 3
Views: 3983

### Re: Need Help Using Scanner

Actually, if you are using Linux you can. Just press Ctrl + D at a console waiting for input and it will send the EOF signal to the process. If you are using Windows, download a Linux distro for free.
Tue Jun 24, 2008 2:31 am
Forum: Volume 114 (11400-11499)
Topic: 11449 - Go Alonso go!
Replies: 8
Views: 1782

### Re: 11449 - Go Alonso go!

emotional blind wrote: SO-RE-DA!
Japanese??
Tue Jun 24, 2008 1:59 am
Forum: Volume 114 (11400-11499)
Topic: 11451 - Water restrictions
Replies: 23
Views: 3280

### Re: 11451 - Water restrictions

I'm using bitwise operations too. Here's my backtracking code: void backtrack(){ for (int i=0, sum = 0; i<S; ++i){ sum += n[i]; if (sum > C) return; } int mask = 0; for (int i=0; i<S; ++i){ if (n[i] > 0){ for (int j=pos[i]-n[i]; j<= pos[i]+n[i]; ++j){ mask = mask | (1<<j); } } } best >?= __builtin_p...
Mon Jun 23, 2008 5:26 pm
Forum: Volume 114 (11400-11499)
Topic: 11451 - Water restrictions
Replies: 23
Views: 3280

### Re: 11451 - Water restrictions

I tried brute force but got Time Limit Exceeded. How did you do it?
Sun Jun 22, 2008 8:46 am
Forum: Volume 110 (11000-11099)
Topic: 11003 - Boxes
Replies: 29
Views: 17053

### Re: 11003 - Boxes

Are you maximizing the length during your DP? If so, then it's not correct because sometimes it's better to have less boxes, but with more weight remaining for future boxes. A fix is to make DP 2-dimensional -- add length of the sequence as an additional parameter to your DP, and try to maximize re...
Sun Jun 22, 2008 8:37 am
Forum: Volume 101 (10100-10199)
Topic: 10154 - Weights and Measures
Replies: 60
Views: 40218

### Re:

I am not sure if your greedy is correct. At first I got Accepted with a greedy algorithm, for which I found a counter example. Here is the correct way how to solve the problem: First, you can sort by strength. Prove: Assume the solution would have a turtle that is stacked upon a turtle with smaller...
Fri Jun 13, 2008 5:31 am
Forum: Volume 114 (11400-11499)
Topic: 11452 - Dancing the Cheeky-Cheeky
Replies: 7
Views: 4044

### Re: 11452 - Dancing the Cheeky-Cheeky

Fri Jun 13, 2008 5:30 am
Forum: C++
Topic: use fgets
Replies: 4
Views: 2729

### Re: use fgets

I'm not sure, but I've always used getline(cin, myString).

Greetings.
Sat May 31, 2008 10:01 pm
Forum: Volume 111 (11100-11199)
Topic: 11115 - Uncle Jack
Replies: 25
Views: 15782

### Re: 11115 - Uncle Jack

I think the problem is the Big Integer class. The code I posted just before your post also gets a Runtime Error. I changed it to not use BigInteger and got Wrong Answer instead.