196 - Spreadsheet

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

chhsiao
New poster
Posts: 2
Joined: Sun Feb 03, 2002 2:00 am

Post by chhsiao » Sun Feb 03, 2002 11:25 am

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
New poster
Posts: 3
Joined: Sat May 04, 2002 11:35 pm

Problem 196 (spreadsheet)

Post by pdiaz » Sat May 04, 2002 11:48 pm

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
/*
* P.D.J.
* spam-here@pdiaz.homeunix.net
* http://acm.asoc.fi.upm.es/~pdiaz
* GPG KeyID: E118C651
*
* Home address: 40

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Sun May 05, 2002 11:01 am

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
New poster
Posts: 3
Joined: Sat May 04, 2002 11:35 pm

Post by pdiaz » Sun May 05, 2002 2:29 pm

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
/*
* P.D.J.
* spam-here@pdiaz.homeunix.net
* http://acm.asoc.fi.upm.es/~pdiaz
* GPG KeyID: E118C651
*
* Home address: 40

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Sun May 05, 2002 10:02 pm

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
New poster
Posts: 3
Joined: Sat May 04, 2002 11:35 pm

Post by pdiaz » Sun May 05, 2002 10:15 pm

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
/*
* P.D.J.
* spam-here@pdiaz.homeunix.net
* http://acm.asoc.fi.upm.es/~pdiaz
* GPG KeyID: E118C651
*
* Home address: 40

Sword Coast
New poster
Posts: 2
Joined: Sun Jan 05, 2003 9:01 pm

196 : Memory Limit Exceeded

Post by Sword Coast » Sun Jan 05, 2003 10:02 pm

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
New poster
Posts: 5
Joined: Thu Dec 19, 2002 2:01 pm
Location: Moscow, Russia

What a strange problem: 196!

Post by Alexander » Tue Jul 01, 2003 2:44 pm

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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Tue Jul 01, 2003 5:18 pm

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
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

Alexander
New poster
Posts: 5
Joined: Thu Dec 19, 2002 2:01 pm
Location: Moscow, Russia

Post by Alexander » Tue Jul 01, 2003 7:31 pm

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
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Wed Jul 02, 2003 11:23 am

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
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

uha
New poster
Posts: 12
Joined: Mon Mar 22, 2004 3:35 am

196 - Spreadsheet

Post by uha » Thu Apr 29, 2004 3:45 am

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
New poster
Posts: 12
Joined: Mon Mar 22, 2004 3:35 am

Post by uha » Fri May 14, 2004 5:41 pm

*echoes*

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Sat May 15, 2004 6:36 am

My AC gives the same output (except newlines between spreadsheets).
I'm always willing to help, if you do the same.

uha
New poster
Posts: 12
Joined: Mon Mar 22, 2004 3:35 am

Post by uha » Mon May 17, 2004 6:01 pm

Thanks :)

I'll try putting in newlines.

Post Reply

Return to “Volume 1 (100-199)”