Page 2 of 3

Posted: Wed May 26, 2004 5:08 pm
by 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.

Posted: Thu May 27, 2004 8:10 pm
by 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.

Posted: Sat Aug 14, 2004 5:03 am
by minskcity
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)

Posted: Mon Aug 23, 2004 12:48 pm
by 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.

Posted: Tue Aug 24, 2004 8:15 am
by 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

Posted: Wed Aug 25, 2004 10:57 am
by the LA-Z-BOy
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... :)

Posted: Wed Aug 25, 2004 11:21 am
by 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

Posted: Wed Nov 10, 2004 2:30 pm
by 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 ?!

Posted: Wed Nov 10, 2004 6:39 pm
by minskcity
Try to read from standard input. :wink:

Posted: Thu Nov 11, 2004 10:35 pm
by Blueteeth
I did so , it gived me WA . :cry:

Posted: Mon Jul 02, 2007 3:32 am
by 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.

WA ... out of ideas :(

Posted: Mon Jan 14, 2008 2:33 pm
by sangram
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

No clue why this is WA!

Posted: Thu Jan 24, 2008 4:24 pm
by sangram
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

Re: What a strange problem: 196!

Posted: Sun Apr 19, 2009 12:21 pm
by 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.

Re: What a strange problem: 196!

Posted: Thu Jul 15, 2010 3:14 am
by suneast
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