196 - Spreadsheet

[shuniu]

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]

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]

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!!

[the LA-Z-BOy]

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.

[Dominik Michniewski]

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

[the LA-Z-BOy]

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.

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

[Dominik Michniewski]

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

[Blueteeth]

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]

Try to read from standard input.

[Blueteeth]

I did so , it gived me WA .

[Ryan Pai]

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.

[sangram]

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

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]

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

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]

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]

Code: Select all

max row: 999
max column: 999

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