## Search found 83 matches

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.
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...
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...
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.
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 ...
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.
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 ...
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...
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 ...
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.
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 ...
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...
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...
Thu Jun 29, 2006 10:52 pm
Forum: Bugs and suggestions