## Search found 13 matches

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

### 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...

- Thu Jan 16, 2003 1:45 pm
- Forum: Algorithms
- Topic: How to detect an arithmetic overflow
- Replies:
**6** - Views:
**3643**

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...

- Thu Jan 16, 2003 1:27 pm
- Forum: Volume 1 (100-199)
- Topic: 106 - Fermat vs. Pythagoras
- Replies:
**138** - Views:
**11967**

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...

- Wed Jan 15, 2003 7:55 pm
- Forum: Algorithms
- Topic: SPEEDING UP THE CODE
- Replies:
**1** - Views:
**921**

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...

- Wed Jan 15, 2003 10:09 am
- Forum: Algorithms
- Topic: How to detect an arithmetic overflow
- Replies:
**6** - Views:
**3643**

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...

- Tue Jan 14, 2003 5:53 pm
- Forum: Volume 1 (100-199)
- Topic: 107 - The Cat in the Hat
- Replies:
**278** - Views:
**20194**

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...

- Tue Jan 14, 2003 4:07 pm
- Forum: Volume 1 (100-199)
- Topic: 107 - The Cat in the Hat
- Replies:
**278** - Views:
**20194**

### 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...

- Tue Jan 14, 2003 3:24 pm
- Forum: Algorithms
- Topic: DFS-BFS
- Replies:
**1** - Views:
**2072**

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

http://www.ics.uci.edu/~eppstein/161/960215.html

- Mon Jan 13, 2003 12:05 pm
- Forum: Algorithms
- Topic: How to detect an arithmetic overflow
- Replies:
**6** - Views:
**3643**

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...

- Sun Jan 12, 2003 5:37 pm
- Forum: Algorithms
- Topic: How to detect an arithmetic overflow
- Replies:
**6** - Views:
**3643**

### 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...

- Mon Jan 06, 2003 4:54 pm
- Forum: Volume 1 (100-199)
- Topic: 106 - Fermat vs. Pythagoras
- Replies:
**138** - Views:
**11967**

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 ...

- Fri Jan 03, 2003 8:26 pm
- Forum: Volume 1 (100-199)
- Topic: 191 - Intersection
- Replies:
**103** - Views:
**18255**

- Fri Jan 03, 2003 2:51 pm
- Forum: Volume 1 (100-199)
- Topic: 191 - Intersection
- Replies:
**103** - Views:
**18255**

### 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:...