Page **1** of **3**

Posted: **Sun Feb 03, 2002 11:25 am**

by **chhsiao**

I use "new"(C++) to allocate memory to store the input data.

And I use a string buffer with size 65536 when reading a formula.

When I have read all data, I store them and use "top-down DP" method to count each fields.

But I get a Runtime Error(SIGSEGV).

How should I do to solve this problem?

Thanks for your answer.

### Problem 196 (spreadsheet)

Posted: **Sat May 04, 2002 11:48 pm**

by **pdiaz**

Hi all,

I'm trying to solve the spreadsheet problem (196). From my point of view, the problem itself is quite simple, and it seems I have it almost working (same results for the sample input, and

other tests I performed seemed OK).

In either case I'm getting runtime errors from the judge (invalid memory access) and I suspect that this could be because I use

a static buffer to read the nodes of the spreadsheet

The problem's description doesn't state what is the maximum

size of a formula, so I choosed an arbitrary one. I tried increasing it, without success. Anyone here has had similar experiences?

Cheers

Pedro

Posted: **Sun May 05, 2002 11:01 am**

by **Ivor**

Try using dynamic memory allocation. You can use static array, but in that case use onedimensional.

As far as I remeber, there were no more than 100000 cells. The reason, why you can't use twodimensional static array, is... well you'd have to declare a 100000x100000 matrix -- and that's a bit too much.

Ivor

Posted: **Sun May 05, 2002 2:29 pm**

by **pdiaz**

Ivor wrote:Try using dynamic memory allocation. You can use static array, but in that case use onedimensional.

As far as I remeber, there were no more than 100000 cells. The reason, why you can't use twodimensional static array, is... well you'd have to declare a 100000x100000 matrix -- and that's a bit too much.

Ivor

Well, in fact I dynamic allocation for the spreadshet per se (an a one dimensional array). The problem is when reading each cell(I guess)

Here the code:

Code: Select all

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CELL 1000
/* @JUDGE_ID: 19527HM 196 C "Pu
```

Posted: **Sun May 05, 2002 10:02 pm**

by **Ivor**

I'm not sure I'm able to understand your code at this time of day... umm...

But are you sure your algorithm can manage with a testcase, were cell you are reading contains a formula which refers to a cell yet to be read?

Like

=B1+B2 7

=B2+A2 6

or smth like that one.

Ivor

Posted: **Sun May 05, 2002 10:15 pm**

by **pdiaz**

I think so, because of the recursive nature of calc_val()

for example, the following spreadsheet:

1

3 3

1 2 3

=A3 0 2

=A1 2 =A2+A3

gives the correct result, that is

1 2 3

1 0 2

1 2 2

Cheers (and thanks for your help!)

Pedro

P.S.: BTW, I believe that your example is not correct, =B2+A2 references to itself, which is assured that wont happen in the

test spreadsheets

P.S2: I forgot to put a free(ss) at the bottom of the main() loop, but the corrected (with free()) program keeps crashing on the judge

Ivor wrote:I'm not sure I'm able to understand your code at this time of day... umm...

But are you sure your algorithm can manage with a testcase, were cell you are reading contains a formula which refers to a cell yet to be read?

Like

=B1+B2 7

=B2+A2 6

or smth like that one.

Ivor

### 196 : Memory Limit Exceeded

Posted: **Sun Jan 05, 2003 10:02 pm**

by **Sword Coast**

I can't find the solution for this problem.

This problem demands that you create a table with 1000 rows and 18278 columns. Whatever type I choose exceed the limit. For example, int types requires

**71407kb **and short int types requires

**35704kb**. The limit is

**32768kb**.

I tried to decrease the dimension of the columns, but i got RTE. I saw people that made this problem with low memory spent(<64kb)!!

If someone knows another way to do this problem, please help me.

Code: Select all

```
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#ifndef ONLINE_JUDGE
#include <io.h>
#include <fcntl.h>
#endif
/* memoria m
```

### What a strange problem: 196!

Posted: **Tue Jul 01, 2003 2:44 pm**

by **Alexander**

Is there are any limitations in this problem?

1. Maximum length of a formula string?

2. Maximum number of formulas? (26^3*999?)

What a real range of the value's matrix?

Is it really 18278x999? If it is, what 'bout memory limitations?

Just integer values: 18278*1000*4 bytes ~= **73 Mb**. Too much!!!

Am i wrong? Could anyone help me?

Posted: **Tue Jul 01, 2003 5:18 pm**

by **Ivor**

I woudn't advise you to use static arrays. Matrix proportions vary a lot. But overall number of elements is not bigger than 100000.

Try it out. My first version worked with dynamic array allocation. However I did rewrite it to use static array but I had to implement the indexing system myself.

Ivor

Posted: **Tue Jul 01, 2003 7:31 pm**

by **Alexander**

Thanks for answer!

I'm trying to solve this problem with Pascal.

Would you please tell me how to create a dynamic arrays using Pascal?

And what 'bout formula's maximum length?

Posted: **Wed Jul 02, 2003 11:23 am**

by **Ivor**

It was way too long ago when I did any pascal.

If I remeber there were memory functions like New and GetMem. Try to come up with something. Maybe friend google can help you.

I don't know the maximum length of formula. But I guess it can't be very long. Sorry, I really don't know.

Ivor

### 196 - Spreadsheet

Posted: **Thu Apr 29, 2004 3:45 am**

by **uha**

OK, this problem is driving me crazy. As far as I can see my program gives the correct answer for every test case I can think of but the judge gives me WA EVERY time.

Here's my output for some input

4

10 10

48 39 30 =A1+A2+A3 99 33 39 =A5+A6+A7 =A4+A8 =A9

75 77 39 =B1+B2+B3 33 42 45 =B5+B6+B7 =B4+B8 =B9

34 22 99 =C1+C2+C3 44 23 34 =C5+C6+C7 =C4+C8 =C9

27 45 28 =D1+D2+D3 64 22 34 =D5+D6+D7 =D4+D8 =D9

67 23 84 =E1+E2+E3 99 17 54 =E5+E6+E7 =E4+E8 =E9

94 95 98 =F1+F2+F3 37 95 34 =F5+F6+F7 =F4+F8 =F9

33 49 99 =G1+G2+G3 37 48 34 =G5+G6+G7 =G4+G8 =G9

=A1+A2+A3+A4 =B1+B2+B3+B4 =C1+C2+C3+C4 =D1+D2+D3+D4 =E1+E2+E3+E4 =F1+F2+F3+F4 =G1+G2+G3+G4 =H1+H2+H3+H4 =I1+I2+I3+I4

=J1+J2+J3+J4

=A5+A6+A7 =B5+B6+B7 =C5+C6+C7 =D5+D6+D7 =E5+E6+E7 =F5+F6+F7 =G5+G6+G7 =H5+H6+H7 =I5+I6+I7 =J5+J6+J7

=A8+A9 =B8+B9 =C8+C9 =D8+D9 =E8+E9 =F8+F9 =G8+G9 =H8+H9 =I8+I9 =J8+J9

4 3

10 34 37 =A1+B1+C1

40 17 34 =A2+B2+C2

=A1+A2 =B1+B2 =C1+C2 =D1+D2

4 3

10 34 37 =A1+B1+C1

40 17 34 =A2+B2+C2

=A1+A2 =B1+B2 =C1+C2 =A1

5 5

5 7 11 22 -1

=B1+B2+B3 0 5 16 -2

8 =C1+D2+E5 14 13 =A5+E1

5 10 20 100 -10

=D3+C4 15 13 =C1 200

My program gives:

48 39 30 157 99 33 39 194 211 194

75 77 39 138 33 42 45 167 228 167

34 22 99 168 44 23 34 281 224 281

27 45 28 463 64 22 34 392 1389 392

67 23 84 176 99 17 54 173 304 173

94 95 98 98 37 95 34 160 142 160

33 49 99 118 37 48 34 122 186 122

184 183 196 926 240 120 152 1034 2052 1034

194 167 281 392 173 160 122 455 632 455

378 350 477 1318 413 280 274 1489 2684 1489

10 34 37 81

40 17 34 91

50 51 71 172

10 34 37 81

40 17 34 91

50 51 71 10

5 7 11 22 -1

234 0 5 16 -2

8 227 14 13 32

5 10 20 100 -10

33 15 13 11 200

Does anyone with an accepted program get the same thing? Or are there any particularly tricky test cases? I'm out of ideas.

Thanks in advance.

Posted: **Fri May 14, 2004 5:41 pm**

by **uha**

*echoes*

Posted: **Sat May 15, 2004 6:36 am**

by **Ryan Pai**

My AC gives the same output (except newlines between spreadsheets).

Posted: **Mon May 17, 2004 6:01 pm**

by **uha**

Thanks

I'll try putting in newlines.