Search found 13 matches

by prilmeie
Tue Aug 26, 2003 10:19 am
Forum: Volume 105 (10500-10599)
Topic: 10544 - Numbering the Paths
Replies: 14
Views: 4867

Sample input

I have found all troubles in my code using this sample input: 3 7 15 CB FE DA GA AB DC AF GB AE GA AC CE GF GC CF 9 DCFE GCE GAB CFE AFE CB GB DAB DAFE 5 6 AB AC BC CD CE ED 3 ABCD ACD CD 3 3 AB AC AB 1 AC The output should be: DCFE: 9 GCE: 9 GAB: 1 CFE: 3 AFE: 6 CB: 1 GB: 7 DAB: 1 DAFE: 6 ABCD: 1 A...
by prilmeie
Thu Jan 16, 2003 1:45 pm
Forum: Algorithms
Topic: How to detect an arithmetic overflow
Replies: 6
Views: 3648

Yes you are right, I have made a calculation mistake which lead me to the wrong corollary, that the inverse operation could detect any overflow error. If you think twice (and analytically) you can easily detect, that this is not the case: An addition in a computer must allways be seen as a circlic o...
by prilmeie
Thu Jan 16, 2003 1:27 pm
Forum: Volume 1 (100-199)
Topic: 106 - Fermat vs. Pythagoras
Replies: 138
Views: 12148

See also http://acm.uva.es/board/viewtopic.php?t=2085 . My solution (the algorithm itself hasn't changed) uses this overflow checking functions. My integer data containers are all of type int, so this should be a prove that you do not have to use data containers longer than a machine word itself. Th...
by prilmeie
Wed Jan 15, 2003 7:55 pm
Forum: Algorithms
Topic: SPEEDING UP THE CODE
Replies: 1
Views: 922

A general tip might be: Reuse allready calculated values. You can do this as follows: Read the complete input. Determine which input values lead to the same output, i.e. be sure to know about equivalence classes of input data. Reuse exactly those values (and not all values), that way you can save so...
by prilmeie
Wed Jan 15, 2003 10:09 am
Forum: Algorithms
Topic: How to detect an arithmetic overflow
Replies: 6
Views: 3648

I do not agree with you that the check for the inversion value in detect_addition_overflow is never true. Let me prove this by a small example: Asume that we are using a 32bit machine, i.e. int has the length 32 bit. Let a = 2147483647, that is INT_MAX, and b = 2. There undoubtly will be an overflow...
by prilmeie
Tue Jan 14, 2003 5:53 pm
Forum: Volume 1 (100-199)
Topic: 107 - The Cat in the Hat
Replies: 278
Views: 20521

It is possible to hash all possible input values and thus have a look-up table. This is exactly the kind of solution which I do not want to submit - using precalculated values. Allthough this solves the problem, it does not respect the spirit and the intention of the problemset. But I do not want t...
by prilmeie
Tue Jan 14, 2003 4:07 pm
Forum: Volume 1 (100-199)
Topic: 107 - The Cat in the Hat
Replies: 278
Views: 20521

107 - Let's find an analytic solution

I am confident that there exists a faster solution for this problem than brute force iterating, evaluationg the power and afterwards value checking. As we all know, the two input values, I will call them x and y are of the form (mathematical expressions in LaTeX style): x = A^{k} y = (A + 1)^{k} The...
by prilmeie
Tue Jan 14, 2003 3:24 pm
Forum: Algorithms
Topic: DFS-BFS
Replies: 1
Views: 2079

Both algorithms are very simple, so you should be able to derivate the implementation of the algorithms by yourself. An explanation can be found at:

http://www.ics.uci.edu/~eppstein/161/960215.html
by prilmeie
Mon Jan 13, 2003 12:05 pm
Forum: Algorithms
Topic: How to detect an arithmetic overflow
Replies: 6
Views: 3648

Yes, you are right, I am indeed missing a sign check. For the value of ov_value, one could expect perhaps -1, for an addition of two positive integers, or +1 for an addition of two negative integers, whose values cannot be the result of the operation if everything went Ok. Otherwise an overflow cann...
by prilmeie
Sun Jan 12, 2003 5:37 pm
Forum: Algorithms
Topic: How to detect an arithmetic overflow
Replies: 6
Views: 3648

How to detect an arithmetic overflow

Hi all, I've had serious arithmetic overflow problems with the Problem 106. Therefore I have written some overlow checking code (in C++) for myself, but I am just curious if you know some slightly faster one, as this is obviously O(1): [cpp] /** * Performs an addition of parameters a and b. If an ar...
by prilmeie
Mon Jan 06, 2003 4:54 pm
Forum: Volume 1 (100-199)
Topic: 106 - Fermat vs. Pythagoras
Replies: 138
Views: 12148

I am also getting WA on this problem. Maybe someone can help me? I think I am having problems with the last for - Loop in the solve functions, because it once worked before the upper bound for the problem has been moved to 1000000. Regards, Franz [cpp]#include <iostream> #include <bitset> const int ...
by prilmeie
Fri Jan 03, 2003 8:26 pm
Forum: Volume 1 (100-199)
Topic: 191 - Intersection
Replies: 103
Views: 18381

Jordan Gordeev wrote:You have submitting problem. [...] I recomment you using a C-style comment (/* ... */)
You are right, this has been a submitting problem. I am using Mozilla which autowraped lines and C++ comments. Although this program produces WA it now compiles.

Thanks,
Franz
by prilmeie
Fri Jan 03, 2003 2:51 pm
Forum: Volume 1 (100-199)
Topic: 191 - Intersection
Replies: 103
Views: 18381

Weird compile error

Hello folks, I am having problems with the OJ C++ compiler. The program below compiles perfectly with the free Borland C++ compiler (Version 5.5.1) and with the GNU g++ compiler version 3.2, but the judge rejects it with a compile error. The compiler error messages seem strange to me: 01314075_24.c:...

Go to advanced search