## Search found 12 matches

Sun Dec 28, 2008 12:44 am
Forum: Volume 115 (11500-11599)
Topic: 11566 - Let's Yum Cha!
Replies: 10
Views: 4688

### 11566 - Let's Yum Cha!

I am having hard time understanding the problem statement. From what i understand, 1) There are N+1 persons in total including you. 2) Each person can spend \$x at max. 3) Each person spends the same amount of money(I don't understand what 'same amount of money to within one dollar' means). 4) Each p...
Tue Nov 18, 2008 9:35 am
Forum: Bugs and suggestions
Topic: You are not authorised to view this resource.
Replies: 10
Views: 10504

### Re: You are not authorised to view this resource.

I am having the same problem too. Previously, this did not happen. I sent a mail to the admins regarding this, but so far, haven't got any reply.

Cheers
Vinay
Mon Sep 15, 2008 1:21 am
Forum: Volume 114 (11400-11499)
Topic: 11490 - Just Another Problem
Replies: 4
Views: 2682

### 11490 - Just Another Problem

My O(sqrt(n)) solution is timing out. Any hints are appreciated. I just dont see any different algorithm.
TIA
Vinay Emani
Sun Sep 14, 2008 6:57 am
Forum: Volume 114 (11400-11499)
Topic: 11481 - Arrange the Numbers
Replies: 10
Views: 4673

### Re: 11481 - Arrange the Numbers

Yep, I solved it during the contest using a recurrence relation.

Hint : Think of how to get a recurrence relation to find the number of derangements of n numbers.
Tue Oct 31, 2006 9:36 pm
Forum: Algorithms
Topic: MST Via Floyd Warshall Question ??
Replies: 1
Views: 1716
When you need shortest distance from any vertex to anyother vertex, you can use All pairs shortest paths(Floyd-Warshall's). When you need a least cost path which connects all the vertices in a graph, use the MST.
Mon Oct 23, 2006 9:18 am
Forum: Volume 111 (11100-11199)
Topic: 11132 - Dice from pennies
Replies: 10
Views: 4022
Could you explain it with an example? What i think is suppose we have 2D6, so we need 4 pennies to describe a throw, suppose the sequence is TTTHTTTHHHHH. "TTTH" is 15, so we look at next "TTTH", this is not possible as well, so we look at "HHHH". This is possible with sum being 1, so we return 1, I...
Mon Oct 23, 2006 7:08 am
Forum: Volume 111 (11100-11199)
Topic: 11138 - Nuts and Bolts
Replies: 9
Views: 5494
Maximum bipartite matching?
Mon Oct 23, 2006 6:55 am
Forum: Volume 111 (11100-11199)
Topic: 11132 - Dice from pennies
Replies: 10
Views: 4022

### 11132 - Dice from pennies

First please correct me if my understanding of what is being asked is wrong. ADB means we have A B-sided dice and we want to simulate these dice using pennies. With A B-sided dice the maximum sum we can get is A*B, so the number of pennies needed is minimum N such that 2^N >=A*B. After this point, w...
Mon Oct 16, 2006 10:42 am
Forum: Volume 111 (11100-11199)
Topic: 11125 - Arrange Some Marbles
Replies: 20
Views: 14454

### ????

@cpphamza, could you post your code please #include <iostream> #include <cmath> #include <vector> #include <algorithm> #include <string> #include <cstring> using namespace std; #define LL long long LL res[8][8][8][8][4][3]; int maxs[4],FC,FG,N,tmp[4]; LL ways(int l1,int l2,int l3,int l4,int prevc,in...
Thu Sep 28, 2006 12:37 pm
Forum: Volume 103 (10300-10399)
Topic: 10304 - Optimal Binary Search Tree
Replies: 24
Views: 12733

### 10304 OBST

I tried this with a O(n^3) DP approach. But it times out. Later i came to know there exists a Knuth's O(n^2) algorithm for finding OBST. Could someone please explain what it is? Thanks in advance.
Mon Sep 25, 2006 4:12 pm
Forum: Algorithms
Topic: usaco training problem
Replies: 5
Views: 3293

### ??

It seems like you are doing wrong somewhere. Insertion sort is O(n^2). Even you get the logic correct, no way your solution can get AC with no. of farmers being 5000 or 10000. Try to use standard sort function available in your programming language. It is O(n*logn) mergesort. So, sorting should not ...
Mon Sep 25, 2006 11:16 am
Forum: Algorithms
Topic: usaco training problem
Replies: 5
Views: 3293

### Hello

For this problem, you need to sort the farmers by their starting times and you need to keep a count of how many people are working at any moment. For that first you need to sort farmers by their starting times. I think you are doing right, only sorting by O(n^2) algorithm. Thats not good enough. Try...