Search found 83 matches

by david
Sat Oct 22, 2005 1:02 pm
Forum: Volume 109 (10900-10999)
Topic: 10947 - Bear with me, again..
Replies: 23
Views: 2906

I think most problems from the last contest were badly specified (if not downright wrong, as was the case for problem A). Does anyone know how big can the coordinates be? Will a sum of squares overflow a long long? I have also tried using doubles, but nothing seems to work. My algorithm simply uses ...
by david
Sun Oct 09, 2005 6:17 pm
Forum: Volume 109 (10900-10999)
Topic: 10927 - Bright Lights
Replies: 26
Views: 13592

Just sort the points according to their angle from the origin, and then a linear search suffices to find the visible points (after which you need to sort them again to meet the output specifications). In fact, for the first sorting the only thing needed is that points collinear with (0, 0) are next ...
by david
Tue Sep 27, 2005 8:43 pm
Forum: Volume 107 (10700-10799)
Topic: 10736 - Series of PI
Replies: 6
Views: 3085

One more important thing - my ACC program outputs for N = 7 the answer 9 and not 10 as the ACC program from david ?! All other answers of my program are same as his answers ( I mean if we use the input from Observer ). The 10th term of the taylor expansion for arcsin(x) is 12155/1245184*x^19, and t...
by david
Tue Sep 27, 2005 8:07 pm
Forum: Volume 107 (10700-10799)
Topic: 10763 - Foreign Exchange
Replies: 45
Views: 17517

I ask those of you who got AC with O(N). What was your method? If you mean O(N) expected time, then hashing is a correct solution. I don't know why some of you seem to imply that it is "logically incorrect". Just keep a hash table that can be indexed by an ordered pair of numbers and contains the n...
by david
Mon Sep 26, 2005 5:32 pm
Forum: Volume 109 (10900-10999)
Topic: 10905 - Children's Game
Replies: 66
Views: 25376

The idea is actually very intuitive. In fact when I wrote my solution, I didn't think of any justification, but if you are interested there is one in the last paragraph. Let "++" stand for the operation of concatenation of strings. If you put string "a" after (but not neccesarily next to) string "b"...
by david
Fri Apr 15, 2005 3:39 pm
Forum: Volume 108 (10800-10899)
Topic: 10834 - The Story of Two Coins
Replies: 18
Views: 4245

Thanks for that. I changed the code to avoid printing -0.000, switched back to doubles (instead of long doubles) and got AC.
But I don't know how on earth one could have guessed that was the problem. I think the judge shouldn't test for an exact match in floating point problems.
by david
Mon Apr 11, 2005 10:19 pm
Forum: Volume 108 (10800-10899)
Topic: 10834 - The Story of Two Coins
Replies: 18
Views: 4245

Thanks for replying. The proper way to read and print long doubles is with %Lf, not with %llf. I haven't had any problems so far using %llf (just as %lli for long longs). In any case changing this leads to WA again. Make sure to print 0.000 instead of -0.000. But when should I do so? If a number is ...
by david
Thu Mar 24, 2005 4:19 pm
Forum: Volume 108 (10800-10899)
Topic: 10834 - The Story of Two Coins
Replies: 18
Views: 4245

Can anyone tell me why this code returns WA? (The code is a bit ugly but very simple, just computes the angle 'a' the center of the coin has rotated, and then the position of T). I have used long doubles to account for precision errors. By the way, are there any test cases in which the coin has not ...
by david
Sat Nov 13, 2004 7:38 pm
Forum: Volume 107 (10700-10799)
Topic: 10760 - Translation or rotation
Replies: 13
Views: 4386

Hi.
The correct output is "Translation by vector <0.0,0.0>."
You should only print "No move" when the coordinates of the endpoints coincide to within 10e-8.
by david
Mon Nov 01, 2004 5:08 pm
Forum: Volume 3 (300-399)
Topic: 315 - Network
Replies: 68
Views: 21018

My program works fine for both inputs. Might the problem statement be wrong? For example, might the judge test data contain disconnected graphs or graphs with more than 100 vertices?
by david
Mon Nov 01, 2004 1:26 am
Forum: Volume 3 (300-399)
Topic: 315 - Network
Replies: 68
Views: 21018

Can anyone tell me what's wrong with my program? It prints the correct answer for every input I have tried, but gives WA after 0.000 s, so I thought the problem might be input-related and added some extra checking (i.e, white spaces at the end of the line or cheking end of input file), but to no ava...
by david
Sun Oct 24, 2004 6:41 pm
Forum: Volume 107 (10700-10799)
Topic: 10740 - Not the Best
Replies: 23
Views: 12967

What reference do you need? Isn't slightly modified Dijkstra (with counting the k-th shortest path to all the verticles) good enough?
No, it isn't. It is not inmediately clear how to deal with zero-length cycles.
by david
Fri Oct 22, 2004 6:11 pm
Forum: Volume 107 (10700-10799)
Topic: 10744 - The Optimal Super-Highway
Replies: 29
Views: 14612

But I can't understand How I find medians in linear time ? I use partition method that use quick sort. But it's worst case complexity is O(nlogn) Please some one help me to get medians in linear time. Even when counting sort isn't possible, the median can be found in linear time. The idea is simila...
by david
Wed Oct 20, 2004 10:47 pm
Forum: Volume 107 (10700-10799)
Topic: 10744 - The Optimal Super-Highway
Replies: 29
Views: 14612

We can ignore 99.045 (since it is constant for all points), but result (10203) is too big for counting sort. What is my mistake ? Why do you say 10203 is too big for counting sort??? The numbers ax + by will always be in the range -40000...40000, so you need an array of 80000 integers, which easily...
by david
Wed Oct 20, 2004 10:39 pm
Forum: Volume 107 (10700-10799)
Topic: 10736 - Series of PI
Replies: 6
Views: 3085

My program outputs

2
3
4
5
7
8
10
11
13
14
220299
407969
449880
472680
567574
576113
664903
692269
731378
778737
846672
935864
996559
996561
996562
996564

(and yes, the key idea is to take logarithms)

Go to advanced search