Search found 12 matches

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

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...
by Naani
Tue Nov 18, 2008 9:35 am
Forum: Bugs and suggestions
Topic: You are not authorised to view this resource.
Replies: 10
Views: 10406

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
by Naani
Mon Sep 15, 2008 1:21 am
Forum: Volume 114 (11400-11499)
Topic: 11490 - Just Another Problem
Replies: 4
Views: 2623

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
by Naani
Sun Sep 14, 2008 6:57 am
Forum: Volume 114 (11400-11499)
Topic: 11481 - Arrange the Numbers
Replies: 10
Views: 4600

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.
by Naani
Tue Oct 31, 2006 9:36 pm
Forum: Algorithms
Topic: MST Via Floyd Warshall Question ??
Replies: 1
Views: 1685

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.
by Naani
Mon Oct 23, 2006 9:18 am
Forum: Volume 111 (11100-11199)
Topic: 11132 - Dice from pennies
Replies: 10
Views: 3949

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...
by Naani
Mon Oct 23, 2006 7:08 am
Forum: Volume 111 (11100-11199)
Topic: 11138 - Nuts and Bolts
Replies: 9
Views: 5412

Maximum bipartite matching?
by Naani
Mon Oct 23, 2006 6:55 am
Forum: Volume 111 (11100-11199)
Topic: 11132 - Dice from pennies
Replies: 10
Views: 3949

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...
by Naani
Mon Oct 16, 2006 10:42 am
Forum: Volume 111 (11100-11199)
Topic: 11125 - Arrange Some Marbles
Replies: 20
Views: 13029

????

@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...
by Naani
Thu Sep 28, 2006 12:37 pm
Forum: Volume 103 (10300-10399)
Topic: 10304 - Optimal Binary Search Tree
Replies: 24
Views: 12522

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.
by Naani
Mon Sep 25, 2006 4:12 pm
Forum: Algorithms
Topic: usaco training problem
Replies: 5
Views: 3207

??

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 ...
by Naani
Mon Sep 25, 2006 11:16 am
Forum: Algorithms
Topic: usaco training problem
Replies: 5
Views: 3207

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...

Go to advanced search