Search found 38 matches

by jah
Mon Sep 03, 2007 3:45 pm
Forum: Volume 112 (11200-11299)
Topic: 11269 - Setting Problems
Replies: 26
Views: 11061

Well, in fact, when I saw the constraints of the problem (n<=20) DP is the first thing that came into my mind to pass the timelimit.
by jah
Mon Sep 03, 2007 8:02 am
Forum: Volume 112 (11200-11299)
Topic: 11269 - Setting Problems
Replies: 26
Views: 11061

11269 - Setting Problems

Hi could you give me some hints on how to solve this problem efficiently.

I solved it by means of the obvious dp on subsets.
by jah
Sun Sep 02, 2007 4:17 pm
Forum: Volume 112 (11200-11299)
Topic: 11265 - The Sultan's Problem
Replies: 13
Views: 6085

I have not tried the problem yet but what I will try is the following. Initially your region is a square (which is a convex polygon). You process each segment one by one and you partition your current convex region with this segment. This line defines two halfspaces, you eliminate all the points lyi...
by jah
Sun Sep 02, 2007 9:37 am
Forum: Volume 112 (11200-11299)
Topic: 11264 - Coin Collector
Replies: 14
Views: 5561

The output for:

16
1 2 4 17 58 69 125 254 478 1023 10000 145236 172589 172590 1000000 10000000


is 2??

What happens if you want to withdraw 7?
by jah
Sun Sep 02, 2007 8:01 am
Forum: Volume 112 (11200-11299)
Topic: 11264 - Coin Collector
Replies: 14
Views: 5561

Well I used an interval based strategy to solve this problem but I get WA.
Some test cases would be appreciated.
by jah
Sun Sep 02, 2007 7:39 am
Forum: Volume 112 (11200-11299)
Topic: 11264 - Coin Collector
Replies: 14
Views: 5561

11264 - Coin Collector

I think the problem statement is a little bit ambiguous because it says: "He should maximize the number of different coins that he can collect in a single withdrawal." and also it says: "For each test case output one line denoting the maximum number of coins that Sultan can collect in a single withd...
by jah
Sat Aug 18, 2007 1:33 pm
Forum: Volume 112 (11200-11299)
Topic: 11209 - Be Together Again and Forever
Replies: 9
Views: 3416

Hi baodog,

You can improve your method by sorting the nodes in the adjacency list. My dfs only computes a single path (not two simultaneously) and looks for the existance of a midpoint in that path.
by jah
Wed Aug 15, 2007 5:04 pm
Forum: Volume 112 (11200-11299)
Topic: 11209 - Be Together Again and Forever
Replies: 9
Views: 3416

The idea is to generate all the paths from Jiajia to WinD incrementally, in order of length, and stop when you find one which has a node equidistant from both.
by jah
Tue Aug 14, 2007 4:30 pm
Forum: Volume 112 (11200-11299)
Topic: 11252 - Take Me Home (To the Place I Belong)
Replies: 8
Views: 2741

My algorithm uses O(n) memory.
by jah
Tue Aug 14, 2007 3:26 am
Forum: Volume 105 (10500-10599)
Topic: 10559 - Blocks
Replies: 37
Views: 12387

My output: Case 1: 1484 Case 2: 1632 Case 3: 1532 Case 4: 1760 Case 5: 1454 Case 6: 1604 Case 7: 1416 Case 8: 1870 Case 9: 1498 Case 10: 1748 Case 11: 1788 Case 12: 1694 Case 13: 1816 Case 14: 1494 Case 15: 1642 Case 16: 1558 Case 17: 2048 Case 18: 1718 Case 19: 1922 Case 20: 1522 This is the output...
by jah
Mon Aug 13, 2007 12:00 pm
Forum: Volume 112 (11200-11299)
Topic: 11252 - Take Me Home (To the Place I Belong)
Replies: 8
Views: 2741

I didn't use sclo's observation directly. I just thought about an O(n^3) implementation and then I found a clever reduction to an O(n^2) solution.

The idea I had originally was is in fact O(n(logn + n)) but I finally implemented it as plain O(n^2).
by jah
Sun Aug 05, 2007 1:16 am
Forum: Volume 112 (11200-11299)
Topic: 11256 - Repetitive Multiple
Replies: 15
Views: 6952

Well in my case I did it with O(d^2 * sqrt(n) ) which can easily be derived to O(d^2 log(n) ).
by jah
Wed Aug 01, 2007 3:27 am
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 9238

Highest-label preflow-push algorithm

Hi,

I haven't tried the problem yet but I have seen a possible approach in the book Network flows (ahuja,magnanti,orlin) which is called Highest-label preflow-push. I think I will wait until uva's migration, I'm not a sadomasochist, :) .
by jah
Tue Jul 31, 2007 2:30 pm
Forum: Volume 112 (11200-11299)
Topic: 11248 - Frequency Hopping
Replies: 20
Views: 9238

Reading Rio's post many doubts came to my mind. I don't know if this method is incorrect: 1) Find the maxflow F and it's corresponding mincut. 2) For each node in S which shares and edge with an edge in T find the additional flow which can be sent from the source. 3) For each node in T sharing and e...
by jah
Sun Jul 29, 2007 12:14 am
Forum: General
Topic: very tight timelimit
Replies: 11
Views: 5088

very tight timelimit

I believe the timelimit for some of the new problems is very tight. For problem 11250, I am running my programs in a P3 800MHz and I get the answer for m = 1000000000 n = 1000000000 in 0.024 secs (obviously for 2000 cases it's not enough). Probably I should write a new optimized BigInt library which...

Go to advanced search