10895 - Matrix Transpose

[Sedefcho]

Does anyone have an idea what may have caused that ?

gcj: Internal compiler error: program jc1 got fatal signal 11

The same Java Code compiles OK on my Win 2000 machine using
the GCJ from the cygwin project. Should I send some email to the
Judge Administrators ?

[Larry]

Post some of your code?

[Sedefcho]

Thanks for the interest.

Below is the full version of my code.

Just a note : at first I was using a second helper class
in same source file called Elem, representing an element in
the matrix in the most natural way. It had just three fields
named row, col, value. Then I decided to get rid of it as I tought
it might have caused the GCJ error I mentioned. But after
getting rid of it and switching just to using the built-in Integer
class I still kept on getting same error.

Code: Select all

import java.util.StringTokenizer;
import java.util.Vector;

class Main { 

    private static Vector columnsR[] = null;
    private static Vector columnsV[] = null;

    private static int cntRows = 0;
    private static int cntCols = 0;

    public static void main (String[] args){
        String token = null;
        int cntNonZeroElems = 0;
        Vector nonZeroElemsR = new Vector();
        Vector nonZeroElemsV = new Vector();
        Vector nonZeroElemsC = new Vector();

        // int c = -1;
        // int r = -1;
        // int value = -1;
        // int k = -1;

        init();
        Integer d = null;

        while (true){
            token = getNextToken();
            if (token==null) break;

            // Read the matrix from the input file
            clear();
            cntRows = Integer.parseInt(token);
            cntCols = Integer.parseInt(getNextToken());
            for (int r=0; r<cntRows; r++){
                cntNonZeroElems = Integer.parseInt(getNextToken());
                nonZeroElemsR.removeAllElements();
                nonZeroElemsV.removeAllElements();
                nonZeroElemsC.removeAllElements();
                for (int k=0; k<cntNonZeroElems; k++){
                    int c = Integer.parseInt(getNextToken()) - 1;
                    d = new Integer(r);
                    nonZeroElemsR.addElement(d);
                    nonZeroElemsC.addElement(new Integer(c));
                    columnsR[c].addElement(d);
                }
                for (int k=0; k<cntNonZeroElems; k++){
                    int value = Integer.parseInt(getNextToken());
                    d = new Integer(value);
                    nonZeroElemsV.addElement(d);
                    columnsV
                    [((Integer)nonZeroElemsC.elementAt(k)).intValue()].
                    addElement(d);
                }
            }

            // Process the matrix ( transpose it )
            System.out.println(cntCols + " " + cntRows);
            for (int c=0; c<cntCols; c++){
                System.out.print(columnsR[c].size());
                for (int k=0; k<columnsR[c].size(); k++){
                    System.out.print
                    (" " + (((Integer)columnsR[c].elementAt(k)).intValue()+1));
                }
                System.out.println();
                for (int k=0; k<columnsV[c].size(); k++){
                    System.out.print((k!=0) ? (" ") : (""));
                    System.out.print
                    (((Integer)columnsV[c].elementAt(k)).intValue());
                }
                System.out.println();
            }
        }
    }

    // Initialization Methods
    private static void init(){
        columnsR = new Vector[10005];
        columnsV = new Vector[10005];
        for (int i=0; i<columnsR.length; i++){
            columnsR[i] = new Vector();
            columnsV[i] = new Vector();
        }
    }

    private static void clear(){
        for (int i=0; i<columnsR.length; i++){
            columnsR[i].removeAllElements();
            columnsV[i].removeAllElements();
        }
    }

    // I/O Related Variables and Methods
    private static String line = null;
    private static StringTokenizer st = null;
    private static final String SEPARATORS = "\t \r\n";

    private static String getNextToken(){
        while (st==null || !st.hasMoreTokens()){
            line = readLn(128);
            if (line == null) return null;
            st = new StringTokenizer(line, SEPARATORS);
        }
        return st.nextToken().trim();
    }

    private static String readLn (int maxLg){
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        try{
            while (lg < maxLg){
                car = System.in.read();
                if ((car < 0) || (car == '\n')) {
                    break;
                }
                lin [lg++] += car;
            }
        }catch (java.io.IOException e){
            return (null);
        }
        if ((car < 0) && (lg == 0)) {
            return (null);
        }
        return (new String (lin, 0, lg));
    }

}

[tRipper]

I dont understand this sentence in problem descreption:

You are given several sparse matrix in a row, each of them described as follows.

Does it mean there are more than one matrices or just one?

[Martin Macko]

I dont understand this sentence in problem descreption:

You are given several sparse matrix in a row, each of them described as follows.

Does it mean there are more than one matrices or just one?

There are more matrices in a row (not in a line)...
Several lines per a matrix. Read the input description more carrefully...

[rahurprem]

Please provide me with some critical input. I am getting wrong answer for many days.

[Dani Rodrigo]

I dont understand this sentence in problem descreption:

You are given several sparse matrix in a row, each of them described as follows.

Does it mean there are more than one matrices or just one?

It means that there are more than one matrix.

[Alice_Italy]

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
using namespace std;
typedef pair<int, int> ii;
typedef vector<ii> vii;

vector<pair <pair<int, int> , int> > matrix;

bool cmp(pair <pair<int, int> , int> a, pair <pair<int, int> , int> b)
{
    if (a.first.first != b.first.first) return a.first.first < b.first.first;
    return a.first.second < b.first.second;
}

void transpose(){
    vector<pair <pair<int, int> , int> >::iterator it = matrix.begin();
    while (it < matrix.end())
    {
        pair <pair<int, int> , int> atual = *it;
        pair<int, int> coords = (*it).first;
        int x = coords.first;
        int y = coords.second;
        pair<int, int> coords2;
        coords2.first = y;
        coords2.second = x;
        (*it).first = coords2;
        it++;
    }
}

int main()
{
    int m,n;
    while (scanf("%d %d", &m, &n) != EOF)
    {
        int col[10001];
        for (int i = 0; i<10001; i++) col[i] = 0;
        int row = 1;
        int aux = m;
        while (m--)
        {
            int nblanks;
            scanf("%d", &nblanks);
            int posicoes[1001];
            int valores[1001];
            for (int h = 0; h<1001; h++){posicoes[h] = 0; valores[h]=0;}
            int inx =0, iny=0;
            for (int z = 0; z<nblanks; z++){scanf("%d", &posicoes[inx]); inx++;}
            for (int z = 0; z<nblanks; z++){scanf("%d", &valores[iny]); iny++;}
            int u = 0;
            for (; u<nblanks ;u++)
            {
                pair<int, int> coords;
                coords.first = row;
                coords.second = posicoes[u];
                col[posicoes[u]]++;
                pair<pair<int, int>, int> element;
                element.first = coords;
                element.second = valores[u];
                matrix.push_back(element);
            }
            row++;
        }
            transpose();
            sort(matrix.begin(), matrix.end(), cmp);
            printf("%d %d\n", n, aux);
            vector<pair <pair<int, int> , int> >::iterator it = matrix.begin();
            int r = 1;
            int atual = 0;
            string line1 = "";
            string line2 = "";
            while (it < matrix.end())
            {
                pair <pair<int, int> , int> elem = *it;
                pair<int,int> coords = elem.first;
                int row = coords.first;
                int colu = coords.second;
                int val = elem.second;
                stringstream conv, conv1, conv2, conv3;
                if (row > atual){
                    if (it != matrix.begin()) { cout << line1 << endl; cout << line2 << endl;}
                    line1 = "";
                    line2 = "";
                    string n;
                    conv << col[r];
                    r++;
                    atual++;
                    n = conv.str();
                    line1 += n;
                    line1 += " ";
                    if (col[r-1] == 0){
                        printf("0\n");
                        printf("\n");
                        line1 = "";
                        line2 = "";
                        string n;
                        conv3 << col[r];
                        r++;
                        atual++;
                        n = conv3.str();
                        line1 += n;
                        line1 += " ";
                    }
                }
                string x;
                conv1 << colu;
                x = conv1.str();
                line1 += x;
                line1 += " ";
                string y;
                
                conv2 << val;
                y = conv2.str();
                line2 += y;
                line2 += " ";
                it++;
                if (it == matrix.end()){
                    cout << line1 << endl; cout << line2 << endl;
                }
            }
        matrix.clear();
    }
    return 0;
}

This is my code for this problem. It's right for sample input and for some inputs i've created. I keep getting WA though. Could anyone help with that by checking my code or sparing some critical input/output? Thanks.

[brianfry713]

Don't print a space at the end of a line.

[Alice_Italy]

It didn't solve it

[meee...]

Hi , prove this trivial case:

Code: Select all

0 1
1 0
0

the correct outputs:

Code: Select all

0 0
0 0

[arash]

can someone help me why my code is incorrect ???

Code: Select all

#include <string>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <vector>
#include <iostream>
#include <iomanip>
#include <map>
#include <stack>
#include <queue>
#include <stdio.h>
using namespace std;


int main ()
{
    int m,n;
    cin >> m >> n;
    cout << n << " " << m << endl;
    int** matris=0;
    matris = new int* [n];
    for (int i=0; i<n; i++) {
        matris[i]=new int[m];
    }
    for (int i=0; i<m; i++) {
        int k; cin >> k;
        if (k==0) {
            string lkhg;
            getline(cin,lkhg);
        }
        vector<int> a;
        for (int j=0; j<k; j++) {
            int w; cin >>w;
            a.push_back(w);
        }
        vector<int> b;
        for (int j=0; j<k; j++) {
            int w; cin >>w;
            b.push_back(w);
        }
        for (int j=0; j<k; j++) {
            matris[a[j]-1][i]=b[j];
        }
    }
    for (int i=0; i<n; i++) {
        int counter=0;
        vector<int> a,b;
        for (int j=0; j<m; j++) {
            if (matris[i][j]!=0) {
                counter++; a.push_back(j+1); b.push_back(matris[i][j]);
            }
        }
        if (counter==0) {
            cout << "0" << endl ;
        }
        else {
            cout << counter << " ";
            for (int k=0; k<a.size(); k++) {
                cout << a[k];
                if (k!=a.size()-1) {
                    cout << " ";
                }
            }
            cout << endl;
            for (int k=0; k<b.size(); k++) {
                cout << b[k];
                if (k!=b.size()-1) {
                    cout << " ";
                }
            }
        }
        cout << endl;
    }
    return 0;
}

[brianfry713]

You are given several sparse matrix, not just one.
Input:

Code: Select all

4 3
3 1 2 3
1 3 2
2 2 3
4 -1
0

3 1 2 3
5 -2 11
4 3
3 1 2 3
1 3 2
2 2 3
4 -1
0

3 1 2 3
5 -2 11

Output should be:

Code: Select all

3 4
2 1 4
1 5
3 1 2 4
3 4 -2
3 1 2 4
2 -1 11
3 4
2 1 4
1 5
3 1 2 4
3 4 -2
3 1 2 4
2 -1 11

[arash]

You are given several sparse matrix, not just one.

i still get WA it's my new code
why It is not correct ????!!!!!
i can't believe that's wrong ...

Code: Select all

Accepted! Thanks

[brianfry713]

Change line 48 to:
for (int j=0; j < v.size() && v[j].first.first==i; j++) {