196 - Spreadsheet

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

[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

[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

[pdiaz]

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

[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

[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

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

[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

[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?

[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

[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?

[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

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

[uha]

*echoes*

[Ryan Pai]

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

[uha]

Thanks

I'll try putting in newlines.