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.