Search found 83 matches

by david
Tue Sep 26, 2006 1:18 pm
Forum: ACM ICPC Archive Board
Topic: p2195 Counting Zeroes (dhaka regionals)
Replies: 25
Views: 11157

I think vinay is right, it seems no one reads the forums at the live archive so I don't think it's a bad idea to discuss them at the uva forum.
by david
Mon Sep 18, 2006 8:26 pm
Forum: Algorithms
Topic: time complexity
Replies: 3
Views: 1614

If you are talking about, for example, the typical algorithm that examines all elements of the array at most a constant number of times, the complexity is linear in the size of the input. Just notice that the number of times you will access a particular bit is bounded, so the time it takes is linear...
by david
Sun Sep 17, 2006 4:23 pm
Forum: Algorithms
Topic: time complexity
Replies: 3
Views: 1614

Yes, if an algorithm takes just a number n as input, and requires O(n) steps to compute the answer, it is exponential in the size of the input (assuming n is coded in binary, or in any base larger than one for that matter). However, if n is given, for instance, in base 3, the time complexity will be...
by david
Sun Aug 20, 2006 8:36 pm
Forum: ACM ICPC Archive Board
Topic: DP problem from LIve Archive - 3144.
Replies: 2
Views: 2170

There's a much simpler recurrence. Think of the number of sequences of length n having maximum element <= m.
by david
Sat Aug 19, 2006 2:02 pm
Forum: Volume 110 (11000-11099)
Topic: 11066 - Aragorn
Replies: 7
Views: 2880

I don't know what you mean by "clipping". I simply build the curve that is the "minimum" of the two given (you just need to find their points of intersection, which can be done in linear time) and substract areas. My code, excluding the pre-written geometric routines for segment intersection, is 60 ...
by david
Fri Aug 18, 2006 5:23 pm
Forum: Volume 110 (11000-11099)
Topic: 11066 - Aragorn
Replies: 7
Views: 2880

My program outputs

0.00
500.00
0.00
1.00
100000000.00
3.33
25000000.00
4.73

Anyway, it would have been easy for you to check most of your answers by hand.
by david
Tue Aug 15, 2006 7:21 pm
Forum: Volume 110 (11000-11099)
Topic: 11068 - An Easy Task
Replies: 16
Views: 7126

Re: 11068

In my opinion, the question is asking for the intersection point of the lines (if any), is that the whole thing this question is asking? Well, the question doesn't ask that directly, although it ends up being just that. The question is asking whether the composition of two "mirrorings" (that is, a ...
by david
Sat Aug 12, 2006 8:39 pm
Forum: Volume 110 (11000-11099)
Topic: 11067 - Little Red Riding Hood
Replies: 23
Views: 8497

Maybe you should increase size of array np[][], and use %d in scanf (%i treats integers with leading zeroes as octal, and that could hurt here.) Many thanks for that, just increasing the array size to 128 (or to 102, for that matter) worked. The problem was that, the way I have written the calcdp f...
by david
Sat Aug 12, 2006 8:04 pm
Forum: Volume 110 (11000-11099)
Topic: 11067 - Little Red Riding Hood
Replies: 23
Views: 8497

I have tried changing %i to %d, but to no avail. Increasing the size of np is unneccessary, although I have tried that as well, just in case. As for \n, there is none missing. puts() always inserts \n at the end. I really have no idea what is going on. Can someone check that the answer is sometimes ...
by david
Sat Aug 12, 2006 7:42 pm
Forum: Volume 110 (11000-11099)
Topic: 11067 - Little Red Riding Hood
Replies: 23
Views: 8497

I already use long longs (as you can see in the code above), and I get wrong answer even though my code is correct.
If you read what I wrote before, my point is that the judge input is flawed and I can't guess what I have to do in order to get accepted.
by david
Sat Aug 12, 2006 7:12 pm
Forum: Volume 110 (11000-11099)
Topic: 11067 - Little Red Riding Hood
Replies: 23
Views: 8497

11067 - Little Red Riding Hood

I think the judge input for this problem doesn't meet the constraints (and neither did the input used during the contest). First of all, there are cases when a wolf is located at (0, 0), contrary to the problem description. (I have checked this with assert). My program would then return 0 (which is ...
by david
Mon Aug 07, 2006 8:54 pm
Forum: Volume 110 (11000-11099)
Topic: 11051 - Dihedral groups
Replies: 8
Views: 2450

I am getting TLE just by reading the input. I read a line and successively use sscanf with the appropiate pointer within the string; I have successfully used this method on many other occasions. Does anyone know where the problem lies? Here goes my code: /* 11051 dihedral groups */ #include <algorit...
by david
Tue Jul 04, 2006 8:32 pm
Forum: ACM ICPC Archive Board
Topic: 3506 - 4 values whose sum is 0
Replies: 3
Views: 2942

The official solution is to compute all sums of elements of A and B, all sums of elements of C and D, sort them and then find, in linear time with the total size of both vectors, pairs of sum zero. The running time is O(n^2 log n). However, the time constraints at SWERC were too tight, so if you use...
by david
Thu Jun 29, 2006 10:52 pm
Forum: Bugs and suggestions
Topic: "received" status
Replies: 1
Views: 1544

"received" status

Every time I try to submit my code for problem 10989, the judge status shows "received" and stays so forever. Why is this happening?
by david
Sat Jun 10, 2006 8:24 pm
Forum: Volume 110 (11000-11099)
Topic: 11039 - Building designing
Replies: 9
Views: 5417

I used qsort() and got Accepted. You can try replacing your sort() function with qsort() function. May be the sort() function is too slow. Hope it helps. The STL sort() function is usually quite a bit faster than qsort(), because it doesn't incur the overhead of comparison function calls (the compi...

Go to advanced search