Search found 158 matches

by andmej
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...
by andmej
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.
by andmej
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.
by andmej
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...
by andmej
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.
by andmej
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...
by andmej
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.
by andmej
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! :D
Japanese??
by andmej
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...
by andmej
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?
by andmej
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...
by andmej
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...
by andmej
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

What's your algorithm?
by andmej
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.
by andmej
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.

Go to advanced search