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

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

Post by shuniu » Wed May 26, 2004 5:08 pm

Try using columns AA, BB.. ZZZ to see if u are calculating them correctly.

Input:

Code: Select all

1
30 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 =AA2
=AA1+B2+AC2 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000
Output:

Code: Select all

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 2700
3127 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000
Also, the input lines are quite long. If you are using UVA's java readLine(),
set the maximum line length to a million. (I originally had it at 500 and it got WA after 0.012s, after the change it got AC after 2.1s)

And there is no need for empty line to separate the outputs, it will give u Presentation Error.

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

Post by uha » Thu May 27, 2004 8:10 pm

Thanks shuniu. I tried your input and as far as I can tell it's the same as your output.

Code: Select all

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 2700
3127 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000
My cell name to index conversion function was the first thing I tested, repeatedly.

ZZZ = 18278

AA = 27

BB = 54

ZAZ = 17628

etc.

Also, I use c++ and read a character at a time so readline is definitely not the problem. I have no idea why I keep getting wa.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Sat Aug 14, 2004 5:03 am

shuniu wrote:Try using columns AA, BB.. ZZZ to see if u are calculating them correctly.
I've got AC in 0.9sec after correcting my "AA" calculation. Thanks!! :D 8)

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Mon Aug 23, 2004 12:48 pm

This problem is almost impossible ( well, for me at least! ) to solve it within the memory limits ( 32meg) if there were inputs of 999 x 18278 spreadsheet. But the stupid thing is that ROW*COLUMN is lot smaller than 999*18278.. yeah it seemed stupid to me because there was no indication about it in the problem statement.
So the problem now looks quiet trivial. So try to use dynamic memory.
Thanks.
Istiaque Ahmed [the LA-Z-BOy]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Aug 24, 2004 8:15 am

But still could be tests where columns = 18278 or rows = 999, so maximum values for this two variables are necessary :-) In problem like this you cannot deal with static tables of maximal size (it's stupid at all for such big tables) but you must use dynamic memory managment - that's all.

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Wed Aug 25, 2004 10:57 am

Dominik Michniewski wrote:But still could be tests where columns = 18278 or rows = 999, so maximum values for this two variables are necessary
i never said that these two variables are unnecessary. :wink:
Dominik Michniewski wrote:In problem like this you cannot deal with static tables of maximal size (it's stupid at all for such big tables) but you must use dynamic memory managment - that's all.
I'm not against dynamic memory usage at all... BUT, you see, the input with 999*18278 spreadsheet is still valid according to the problem statement... and i'm afraid dynamic memory management would do a very little to solve it.
I would have liked to see something like this in the problem statement :
Assume that the product of all rows and colums is maximum XXX ( Where XXX table elements can fit in memory easily)
Just as an example of South Pacific 2k1 problem "Maximum Subsequece"
http://acm.uva.es/archive/data/p2254.html
( Though the constrain specification is much necessary in p2254 than p196, but still p196 needs it i think )
greeting... :)
Istiaque Ahmed [the LA-Z-BOy]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Aug 25, 2004 11:21 am

You have right in one thing: if in input exists case, in which rows and cols are maximal, this problem would be extremally hard to solve :-) hehehe

I try to be more precision in my next posts :-) And I didn't say that you have said that you are against something or that some variables are unnecessary :-)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Blueteeth
New poster
Posts: 4
Joined: Tue Nov 09, 2004 10:28 pm

Post by Blueteeth » Wed Nov 10, 2004 2:30 pm

Hi ,
I've got this error
Dear Blueteeth:

Your program has died with signal 6 (SIGABRT). Meaning:

Abort signal from abort()

Before crash, it ran during 0.000 seconds.
And here's my code :
[cpp]#include <iostream>
#include <fstream>
#include <string>
//#include <conio.h>
#include <cmath>
#include <map>
using namespace std;

map<char,int> letters;

void allocate (string** str, int** intgrs , int r , int c)
{
str = new string*[r];
intgrs = new int*[r];
for ( int i=0 ; i<r ; i++ )
{
str = new string[c];
intgrs = new int[c];
}
}

void Free (string** str, int** intgrs , int r)
{
for (int i=0 ; i<r ; i++)
{
delete[] str;
delete[] intgrs;
}
}

int compute (int** rs ,const char* expr)
{
int r=0 , c=0;
int result=0;
char temp[3];
//temp[0] = expr[1]; // first letter
int size=0;
/*int i=2;*/
for ( int i=1 ; i<strlen(expr) ; )
{
while ( isalpha(expr) )
{
temp[size] = expr;
i++;
size++;
}
for (int j=0 ; j<size ; j++)
c += letters[ temp[j] ] * pow(26.0,size-j-1);

size = 0; // reset size
while ( isdigit(expr) )
{
temp[size] = expr;
i++;
size++;
}
i++; // to skip the plus sign

for (int j=0 ; j<size ; j++)
r += (temp[j]-'0') * pow(10.0,size-j-1);

result += rs[r-1][c-1];
c=r=0; // reset the c and r
}
return result;
}

void get_input (istream& in , string** spread , int r , int c)
{
for (int i=0 ; i<r ; i++)
for (int j=0 ; j<c ; j++)
in >> spread[j];
}

void set_values (string** s,int** rs, int r, int c)
{
const char* temp;
for (int i=0 ; i<r ; i++)
for (int j=0 ; j<c ; j++)
{
temp = /*static_cast<char*>*/( (s[j]).c_str() );
if ( temp[0] != '=' ) // it's a value
rs[i][j] = atoi(temp);
else // formula
rs[i][j] = compute(rs,temp);
}
}

void show_output(int** r , int rows , int columns)
{
for ( int i=0 ; i<rows ; i++ )
{
for ( int j=0 ; j<columns ; j++ )
cout << r[i][j] << ' ';
cout << endl;
}
}


int main()
{
ifstream in("in.txt");
/*map<char,int> letters;*/
char c = 'A';
int order = 1;
while ( c<='Z' )
letters[c++] = order++;
string** spread;
int** final_values;
int n;
in >> n;
for ( int i=0 ; i<n ; i++ )
{
int rows,columns;
in >> columns >> rows;
/*allocate(spread,final_values,rows,columns);*/
spread = new string*[rows];
final_values = new int*[rows];
for ( int k=0 ; k<rows ; k++ )
{
spread[k] = new string[columns];
final_values[k] = new int[columns];
}

get_input(in,spread,rows,columns);
set_values(spread,final_values,rows,columns);
show_output(final_values,rows,columns);
Free(spread,final_values,rows);
}
cin.get();
}[/cpp]
What's wrong ?!

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Wed Nov 10, 2004 6:39 pm

Try to read from standard input. :wink:

Blueteeth
New poster
Posts: 4
Joined: Tue Nov 09, 2004 10:28 pm

Post by Blueteeth » Thu Nov 11, 2004 10:35 pm

I did so , it gived me WA . :cry:

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

Post by Ryan Pai » Mon Jul 02, 2007 3:32 am

I keep getting a presentation error on this problem, and it doesn't really describe what the format of the output should be. For those of you in a similar situation, there shouldn't be any blank lines between output cases.
I'm always willing to help, if you do the same.

sangram
New poster
Posts: 8
Joined: Fri Jun 30, 2006 3:27 pm
Contact:

WA ... out of ideas :(

Post by sangram » Mon Jan 14, 2008 2:33 pm

Someone please help me get this right. Have tried quite a bit on this, but somehow can't get it AC :cry:

All the test inputs given in this thread seem to produce the correct output with my program.

Code: Select all

#include<iostream>
#include<cassert>
#include<vector>
using namespace std;

#define BLACK   101
#define WHITE   102
#define GRAY    103

class mypair{
      public:
      int finishTime;
      vector<int> depend;
};

int rows, columns, mytime;

int parse(string s){
    int a[3]={-1, -1, -1};
    int num = 0;
    int i;
    for (i=0; i<s.length(); i++){
        if (s[i]<'A' || s[i]>'Z'){
           num=atoi(s.substr(i).c_str())-1;
           break;
        }
        a[i]=(int) (s[i]-'A');
    }
    if(i == 1){
        return columns*num+a[0];
    }
    else if(i == 2){
        return columns*num+(26*(a[0])+26+a[1]);
    }
    else{
        return columns*num+(26*26*(a[0])+676+26*(a[1])+26+a[2]);
    }
}

void DFS(int index, vector<mypair>& dependencyGraph, vector< vector<short int> >& colour, vector<int>& processIndices){
    //cout << "Calling DFS for " << index << endl;
    
    int myrow, mycolumn;
    mypair p = dependencyGraph[index];
    myrow = index/columns;
    mycolumn = index%columns;
    
    colour[myrow][mycolumn]=GRAY;
    
    for(int i=0; i<p.depend.size(); i++){
            int next = p.depend[i];
    //        cout << "Next is: " << next << endl;
            if(colour[next/columns][next%columns] == WHITE){
                 DFS(next, dependencyGraph, colour, processIndices);
            }
    }
    
    colour[myrow][mycolumn]=BLACK;
    
    dependencyGraph[index].finishTime = mytime++;
    processIndices.push_back(index);
}
                

int main(){
    int numberOfSheets;
    cin >> numberOfSheets;
    
    for(int z=0; z<numberOfSheets; z++){
            mypair tempP;
            cin >> columns >> rows;
            
            vector< vector<short int> > colour;
            vector< mypair > dependencyGraph(rows*columns, tempP);
            vector< vector<int> > numbers;
            vector<int> processIndices;

            for(int i=0; i<rows; i++){
                    vector<short int> tempColour(columns);
                    vector<int> tempNumbers(columns);
                    for(int j=0; j<columns; j++){
                            string temp;
                            cin >> temp;
                            if(temp[0] == '='){
           //                     cout << temp << " ";
                                         int start = 1;
                                       int end = temp.find("+", start);
                                       while(end != string::npos){
                                                 int ref = parse(temp.substr(start, end-start));
                                                 dependencyGraph[i*columns+j].depend.push_back(ref);
      //                                           cout << ref << " ";
      //                                           cout << i << " " << j << ": " << ref << endl;
                                                 start = end+1;
                                                 end = temp.find("+", start);
                                       }
                                       int ref = parse(temp.substr(start));
                                       dependencyGraph[i*columns+j].depend.push_back(ref);
        //                               cout << i << " " << j << ": " << ref << endl;
                                       tempNumbers[j]=0;
                                       tempColour[j]=WHITE;
        //                               cout << ref << endl;
                            }
                            else{
                                 tempColour[j]=BLACK;
                                 tempNumbers[j]=atoi(temp.c_str());
                                 dependencyGraph[i*columns+j].finishTime = INT_MAX;
          //                       cout << i << " " << j << ": " << numbers[i][j] << endl;
                            }
                    }
                    colour.push_back(tempColour);
                    numbers.push_back(tempNumbers);
            }
            mytime = 0;          
            for(int i=0; i<rows*columns; i++){
                    if(colour[i/columns][i%columns]==WHITE){
                        DFS(i, dependencyGraph, colour, processIndices);
                    }
            }
            
            for(int i=0; i<processIndices.size(); i++){
                    int myrow = processIndices[i]/columns;
                    int mycolumn = processIndices[i]%columns;
                    for(int j=0; j<dependencyGraph[processIndices[i]].depend.size(); j++){
                            int tempIndex = dependencyGraph[processIndices[i]].depend[j];                                   
                            numbers[myrow][mycolumn]+=numbers[tempIndex/columns][tempIndex%columns];
                    }
            }
            
            for(int i=0; i<rows; i++){
                    for(int j=0; j<columns; j++){
                        if(j>0)
                            cout << " ";    
                        cout << numbers[i][j];
                    }
                    cout << endl;
            }
            
            if(z < numberOfSheets-1)
                cout << endl;
    }
    
    return 0;
} 
There are a few redundant things in the code, but I hope it is readable.

Thanks!
Sangram

sangram
New poster
Posts: 8
Joined: Fri Jun 30, 2006 3:27 pm
Contact:

No clue why this is WA!

Post by sangram » Thu Jan 24, 2008 4:24 pm

Someone please help me get this right. Have tried quite a bit on this, but somehow can't get it AC :cry:

All the test inputs given in this thread seem to produce the correct output with my program.

Code: Select all

#include<iostream>
#include<cassert>
#include<vector>
using namespace std;

#define BLACK   101
#define WHITE   102
#define GRAY    103

class mypair{
      public:
      int finishTime;
      vector<int> depend;
};

int rows, columns, mytime;

int parse(string s){
    int a[3]={-1, -1, -1};
    int num = 0;
    int i;
    for (i=0; i<s.length(); i++){
        if (s[i]<'A' || s[i]>'Z'){
           num=atoi(s.substr(i).c_str())-1;
           break;
        }
        a[i]=(int) (s[i]-'A');
    }
    if(i == 1){
        return columns*num+a[0];
    }
    else if(i == 2){
        return columns*num+(26*(a[0])+26+a[1]);
    }
    else{
        return columns*num+(26*26*(a[0])+676+26*(a[1])+26+a[2]);
    }
}

void DFS(int index, vector<mypair>& dependencyGraph, vector< vector<short int> >& colour, vector<int>& processIndices){
    //cout << "Calling DFS for " << index << endl;
    
    int myrow, mycolumn;
    mypair p = dependencyGraph[index];
    myrow = index/columns;
    mycolumn = index%columns;
    
    colour[myrow][mycolumn]=GRAY;
    
    for(int i=0; i<p.depend.size(); i++){
            int next = p.depend[i];
    //        cout << "Next is: " << next << endl;
            if(colour[next/columns][next%columns] == WHITE){
                 DFS(next, dependencyGraph, colour, processIndices);
            }
    }
    
    colour[myrow][mycolumn]=BLACK;
    
    dependencyGraph[index].finishTime = mytime++;
    processIndices.push_back(index);
}
                

int main(){
    int numberOfSheets;
    cin >> numberOfSheets;
    
    for(int z=0; z<numberOfSheets; z++){
            mypair tempP;
            cin >> columns >> rows;
            
            vector< vector<short int> > colour;
            vector< mypair > dependencyGraph(rows*columns, tempP);
            vector< vector<int> > numbers;
            vector<int> processIndices;

            for(int i=0; i<rows; i++){
                    vector<short int> tempColour(columns);
                    vector<int> tempNumbers(columns);
                    for(int j=0; j<columns; j++){
                            string temp;
                            cin >> temp;
                            if(temp[0] == '='){
           //                     cout << temp << " ";
                                         int start = 1;
                                       int end = temp.find("+", start);
                                       while(end != string::npos){
                                                 int ref = parse(temp.substr(start, end-start));
                                                 dependencyGraph[i*columns+j].depend.push_back(ref);
      //                                           cout << ref << " ";
      //                                           cout << i << " " << j << ": " << ref << endl;
                                                 start = end+1;
                                                 end = temp.find("+", start);
                                       }
                                       int ref = parse(temp.substr(start));
                                       dependencyGraph[i*columns+j].depend.push_back(ref);
        //                               cout << i << " " << j << ": " << ref << endl;
                                       tempNumbers[j]=0;
                                       tempColour[j]=WHITE;
        //                               cout << ref << endl;
                            }
                            else{
                                 tempColour[j]=BLACK;
                                 tempNumbers[j]=atoi(temp.c_str());
                                 dependencyGraph[i*columns+j].finishTime = INT_MAX;
          //                       cout << i << " " << j << ": " << numbers[i][j] << endl;
                            }
                    }
                    colour.push_back(tempColour);
                    numbers.push_back(tempNumbers);
            }
            mytime = 0;          
            for(int i=0; i<rows*columns; i++){
                    if(colour[i/columns][i%columns]==WHITE){
                        DFS(i, dependencyGraph, colour, processIndices);
                    }
            }
            
            for(int i=0; i<processIndices.size(); i++){
                    int myrow = processIndices[i]/columns;
                    int mycolumn = processIndices[i]%columns;
                    for(int j=0; j<dependencyGraph[processIndices[i]].depend.size(); j++){
                            int tempIndex = dependencyGraph[processIndices[i]].depend[j];                                   
                            numbers[myrow][mycolumn]+=numbers[tempIndex/columns][tempIndex%columns];
                    }
            }
            
            for(int i=0; i<rows; i++){
                    for(int j=0; j<columns; j++){
                        if(j>0)
                            cout << " ";    
                        cout << numbers[i][j];
                    }
                    cout << endl;
            }
            
            if(z < numberOfSheets-1)
                cout << endl;
    }
    
    return 0;
} 
There are a few redundant things in the code, but I hope it is readable.

Thanks!
Sangram

deadangelx
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

Re: What a strange problem: 196!

Post by deadangelx » Sun Apr 19, 2009 12:21 pm

my AC code uses these sizes:

Code: Select all

max row: 999
max column: 999
formula length: 1000
formula divide into cells: 1000
formula queue size(it means how many cells are formula): 8000
cell number length: 8
it means nothing to calculate the threshold of sizes, and these sizes are enough to help you get AC.
Hope it helps.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: What a strange problem: 196!

Post by suneast » Thu Jul 15, 2010 3:14 am

deadangelx wrote:

Code: Select all

max row: 999
max column: 999
:oops: I dont't understand , the problem description says

Code: Select all

The name of a cell consists of one to three letters for the column followed by a number between 1 and [color=#FF0000]999[/color] (including) for the row. --------- letters correspond to the number from 1 to [color=#FF0000]18278[/color]. 
so shouldn't the max column be 18278 :o

Post Reply

Return to “Volume 1 (100-199)”