Search found 131 matches

by abishek
Mon Aug 08, 2005 10:42 pm
Forum: Volume 108 (10800-10899)
Topic: 10888 - Warehouse
Replies: 19
Views: 12373

I find myself wanting to do a minimal weighted bipartite matching. I don't see how I can do this withouht using the hungarian method :( too lazy to code it to see if it give me TLE too :D but simple greedy gave me WA and a backtrack with some simple pruning gave TLE. is there a polytime algorithm fo...
by abishek
Mon Aug 08, 2005 10:26 pm
Forum: Volume 108 (10800-10899)
Topic: 10887 - Concatenation of Languages
Replies: 49
Views: 18650

jdmetz
you were right. I never noticed this subtle point. mine also times out! thining of better ways to hash.
bye
abishek
by abishek
Mon Aug 08, 2005 3:41 pm
Forum: Volume 108 (10800-10899)
Topic: 10887 - Concatenation of Languages
Replies: 49
Views: 18650

Almost similar code. #include <stdio.h> #include <string> #include <set> #include <iostream> using namespace std; set<string> first; set<string> final; int main() { int t, cano=0; scanf("%d\n", &t); while(t--) { int m, n; string inp; scanf("%d %d\n", &m, &n); first.clear(); final.clear(); for(int i=...
by abishek
Mon Aug 08, 2005 8:20 am
Forum: Volume 108 (10800-10899)
Topic: 10887 - Concatenation of Languages
Replies: 49
Views: 18650

I keep getting WA. I do the following I assume first tht theere are no extra blank lines in input. then I just consider each test case, and find the mxn possible strings and store them in a set. I consider empty strings and I use gets to parse the input. finally I output the size of this set. I don'...
by abishek
Sun Jul 31, 2005 7:11 pm
Forum: Algorithms
Topic: Colin and Ryan
Replies: 3
Views: 1226

amazing that worked, although even my overall complexity is O(sqrt(n-k)) (because the first step to generate prime numbers), your algorithm essentially does the same step thru every iteration and for every test case. you could have done the part of enumerating all the primes using a naive primality ...
by abishek
Sun Jul 31, 2005 7:05 pm
Forum: Algorithms
Topic: Standard Deviation
Replies: 4
Views: 1415

I think the random number generator used int he problem is commonly known as the
chi^2 generator. (except for the division by 2^31-1, which could have been ignored in the computations anyways). But I don't know anything about the period of this generator or how to find it : (
by abishek
Sun Jul 31, 2005 7:00 pm
Forum: Volume 108 (10800-10899)
Topic: 10880 - Colin and Ryan
Replies: 45
Views: 28048

this was stupid!
I think that the problem must have been rejudged, and the solution must have been changed, rather than changing the question.
its not right to expect ppl to refresh the clarifications page.
by abishek
Fri Jun 24, 2005 4:11 am
Forum: Algorithms
Topic: algorithm/ideas needed
Replies: 4
Views: 1662

it may not be enuf to test primes as 2 and 6 may well produce different results than just 2.
by abishek
Mon Jun 13, 2005 7:24 pm
Forum: Volume 108 (10800-10899)
Topic: 10811 - Up the Ante
Replies: 20
Views: 5639

I am confused with some probability here. Will stan continue to play after scoring a positive score in the kth round or higher rounds? if we call stan's score A isnt the answer to the question Prob(A>0 after k rounds) + prob(A<= 0 in the kth round) * prob (A>0 in the k+1 th round) + prob(A<=0 in the...
by abishek
Sun Jun 12, 2005 7:51 pm
Forum: Algorithms
Topic: algorithm/ideas needed
Replies: 4
Views: 1662

algorithm/ideas needed

http://acmicpc-live-archive.uva.es/nuev ... php?p=2339

I am completely stumped by this problem :(
any body has any ideas how to proceed? may be very advanced math?
by abishek
Sun May 08, 2005 7:26 am
Forum: Volume 106 (10600-10699)
Topic: 10655 - Contemplation - Algebra
Replies: 42
Views: 10535

may be he will read this post add the case to the input set and rejudge the problem ;). I for one would be happy as I am sure my solution will not fail ;)
by abishek
Mon Apr 18, 2005 4:21 am
Forum: Algorithms
Topic: Problem J - World Finals 2005
Replies: 11
Views: 6739

Re: hmm

Voronoi diagram was not required for B. I guess some teams did not touch it considering that they need to implement V diagram. I think we need to find the number of intersections of the road with vornoi boundaries in problem B. But I don't see how to find it without the vornoi diagram itself. May b...
by abishek
Mon Apr 18, 2005 3:59 am
Forum: Other words
Topic: ACM regionals and finals questions..
Replies: 29
Views: 12849

http://www.ioi2004.org/html/competition_test.html This is a link where problem/solution/test data for the IOI 2004 is available. I think IOI is also an as important competetion as the ACM and I think they are a setting a good example. One thing to say is that the IOI is an one time competetion so it...
by abishek
Wed Apr 13, 2005 5:09 pm
Forum: Algorithms
Topic: Problem J - World Finals 2005
Replies: 11
Views: 6739

the problem set was very good and I really enjoyed it, though I should crib saying that too much of geometry was there. A, B, E, F, G all had some kind of floating point operations involved and I have always hated floating point numbers :(
by abishek
Tue Apr 12, 2005 8:47 pm
Forum: Volume 108 (10800-10899)
Topic: 10826 - Hot or Cold?
Replies: 26
Views: 13238

only hint that I wish to give is that the problem says n <=300, think about this!!

Go to advanced search