BitCell

by **Mihai** » 11 Oct 2011, 23:08

Șiruri

Se citește din fișierul bitcell17.in un număr natural nenul N (1<=N<=1000) urmat de o matrice cu N linii și N coloane, fiecare element al matricii fiind un număr natural nenul de maximum 6 cifre.

Să se afișeze în fișierul bitcell17.out șirul de lungime maximă care poate fi format cu elemente adiacente din matricea dată (prin adiacență, se înțelege faptul că două elemente consecutive sunt vecine fie pe linie, fie pe coloană) cu condiția ca fiecare element să fie cel puțin egal cu precedentul (în afara primului element, bineînțeles).

Dacă există mai multe șiruri de lungime maximă, va fi afișat cel mai mic din punct de vedere lexicografic.

Exemplu:

bitcell17.in:

Line number On/Off | Expand/Contract | Select all

bitcell17.out:

Line number On/Off | Expand/Contract | Select all

1 4 5 8 9

Explicație: se pot identifica foarte multe șiruri ({1},{5},{1,5,5} șamd). Lungimea maximă a unui astfel de șir este 5, putând exemplifica două șiruri cu această lungime: {1,5,5,8,9} și {1,4,5,8,9}. Șirul mai mic din punct de vedere lexicografic este {1,4,5,8,9} așa că îl afișăm pe acesta.

Perioada de desfăşurare:

11-21 Octombrie - înscrierea în concurs
22-23 Octombrie- desemnarea câștigătorului

by **Mihai** » 15 Oct 2011, 15:30

Pentru că a trecut ceva timp și nu și-a arătat nimeni intenția de a participa, mă simt dator să simplific puțin problema pentru ca timpul sau dificultatea să nu mai constituie un impediment. În această direcție, considerați următoarele:

1 <= N <= 100
dacă există mai multe șiruri de lungime maximă, se poate afișa oricare dintre ele

by **nomemory** » 15 Oct 2011, 18:52

Am o solutie care functioneaza pe matrici mici, nu stiu cum se descurca la numere mari . Ai niste teste pentru numere mari ?
Vreau sa optimizez putin codul inainte sa-l "inscriu in concurs" .

by **Mihai** » 16 Oct 2011, 23:33

Din păcate, nu-ți pot da un test mare pentru că nu am avut încă timp să implementez generatorul de teste (sau soluția). Ca și indiciu, dacă ai găsit o rezolvare O(N2) poți sta liniștit.

by **nomemory** » 17 Oct 2011, 11:33

E departe de O(n^2), e un backtracking simplu cu niste conditii in plus . Cand ajung deseara acasa, o sa pun solutia . Pana atunci ma mai gandesc la alte solutii mai putin "brutale" .

by **Mihai** » 22 Oct 2011, 16:42

Din păcate, nimeni nu s-a arătat interesat de acest concurs - drept urmare, nu avem un câștigător nici de această dată.
Voi reveni mâine cu o temă nouă, ceva mai ușoară, care sper că va atrage mai mulți participanți.

by **new_luca** » 25 Oct 2011, 22:38

Mihai , implor, hai cu o problema de nivelul meu ^:)^

, probabil esti foarte ocupat asa ca iti urez spor la treaba.

by **Mihai** » 25 Oct 2011, 23:43

Promit că o să o pun mâine seară (deocamdată am fost foarte ocupat cu facultatea) și îmi cer scuze pentru întârzieri.

by **nomemory** » 27 Oct 2011, 09:32

Solutia mea (ineficienta, dar "straight-forward") este:

Line number On/Off | Expand/Contract | Select all

#include <cstdio>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
 
using namespace std;
 
//------------------------------------------------------------------------------
// DEBUGGING MACROS
//------------------------------------------------------------------------------
 
#define DBG
#define ERROR(fmt, args...) fprintf(stderr, "ERROR: "fmt, ## args)
#ifdef DBG
    #define DEBUG(fmt, args...) printf(fmt, ## args)
#else
    #define DEBUG ;
#endif
 
//------------------------------------------------------------------------------
// CUSTOM TYPES
//------------------------------------------------------------------------------
 
typedef struct s_Matrix {
    // Uni-dimensional vector to store matrix data
    vector<int> data;
    // The actual matrix dimension, sqrt(matrix.size)
    int size;
} Matrix;
#define ELEM(matrix, i, j) (matrix).data[(i) * ((matrix).size) + (j)]
 
typedef struct s_Position {
    // Encapsulates a position in the matrix
    s_Position(int i, int j) : i(i), j(j) {} ;
    int i;
    int j;
    // We will further insert "Position" objects into a set, we'll need to
    // implement the operator
    friend bool operator<(s_Position const &a, s_Position const& b) {
        return (a.i == b.i) ? a.j < b.j : a.i < b.i;
    }
} Position;
 
typedef struct s_Solution {
    // Encapsulates the "Final solution" :)
    s_Solution() : size(0), data(list<int>()) {};
    int size;
    list<int> data;
} Solution;
 
//------------------------------------------------------------------------------
// CONSTANTS
//------------------------------------------------------------------------------
 
static const char * FILE_IN = "bitcell17.in";
static int MAX_MATRIX_DIM = 1000;
static int MAX_MATRIX_NUM = 999999;
static int SUCCESS = 0;
static int FAILURE = 1;
 
//------------------------------------------------------------------------------
// FUNCTION DEFINITIONS AND DECLARATIONS
//------------------------------------------------------------------------------
 
bool read_matrix(Matrix &matrix, const char * file_name);
bool visited_contains(const set<Position> visited, const Position value);
bool up_ok(const Matrix matrix, const Position source,
    const set<Position> visited);
bool down_ok(const Matrix matrix, const Position source,
    const set<Position> visited);
bool left_ok(const Matrix, const Position source,
    const set<Position> visited);
bool right_ok(const Matrix, const Position source,
    const set<Position> visited);
bool util_ok(const Matrix, const Position source, const int i_add,
    const int j_add, const set<Position> visited);
void get_next_positions(const Matrix matrix, const Position source,
    list<Position> &next_positions);
void solution(const Matrix matrix, Solution &solution);
 
/**
* Reads a matrix from a given (input) file .
* @param matrix this matrix reference will be updated with data from file
* @param file_name the path to the input file .
* @return true if the matrix is succesfuly updated, false otherwise
*/
bool read_matrix(Matrix &matrix, const char * file_name)
{
    FILE *in = NULL;
    int tmp = 0;
    int lim = 0;
 
    in = fopen(file_name, "r");
    if(!in) {
        ERROR("Cannot open file %s . \n", file_name);
        return (false);
    }
 
    fscanf(in, "%d", &(matrix.size));
 
    if (matrix.size > MAX_MATRIX_DIM) {
        // Validates matrix size
        ERROR("Matrix dimension (%d) is bigger than MAX_LIMIT (%d). \n",
            matrix.size, MAX_MATRIX_DIM);
        fclose(in);
        return (false);
    }
 
    lim = matrix.size * matrix.size;
    matrix.data.reserve(lim);
    for(int i = 0; i < lim; ++i) {
        fscanf(in, "%d", &tmp);
        if(tmp > MAX_MATRIX_NUM) {
            // Validates number limit
            ERROR("\nNumber (%d) > Limit (%d)\n", tmp, MAX_MATRIX_NUM);
            fclose(in);
            return (false);
        }
        matrix.data.push_back(tmp);
    }
 
    fclose(in);
 
    return (true);
}
 
/**
* Test if a given position in the matrix was already visited .
* Using a set find works in O(logn) .
* @param visited a set o previously visited positions .
* @param position the position to test
* @return a boolean value
*/
bool visited_contains(const set<Position> visited, const Position value)
{
    return (visited.find(value) != visited.end());
}
 
/**
* Test if we can go to a certain position from a given source position .
* @param matrix the matrix used
* @param source current location in the matrix
* @param i_add , 0 means we will remain on the same row, +x will shift with x
            rows
* @param j_add, 0 means we will remain on the same column, +y we will shift y
            columns
* @param a set of previously visited positions .
* @see associated macros
*/
bool util_ok(const Matrix matrix,
    const Position source,
    const int i_add, const int j_add,
    const set<Position> visited)
{
    int new_i = source.i + i_add;
    int new_j = source.j + j_add;
    if (new_i >= 0 && new_i < matrix.size &&
        new_j >= 0 && new_j < matrix.size &&
        !visited_contains(visited, Position(new_i, new_j)) &&
        ELEM(matrix, source.i, source.j) < ELEM(matrix, new_i, new_j)) {
        return true;
    }
    return false;
}
// One row UP, keeping the same column
#define OK_UP(matrix, source, visited) \
    util_ok((matrix), (source), -1, 0, (visited))
// One row DOWN, keeping the same column
#define OK_DOWN(matrix, source, visited) \
    util_ok((matrix), (source), 1, 0, (visited))
// One column LEFT, keeping the same row
#define OK_LEFT(matrix, source, visited) \
    util_ok((matrix), (source), 0, -1, (visited))
// One column RIGHT, keeping the same row
#define OK_RIGHT(matrix, source, visited) \
    util_ok(matrix, source, 0, 1, visited)
 
/**
* Returns the next positions .
* @param matrix
* @param source the current position
* @param visited previously visited positions
* @param next_positions - possible postions go here
*/
void get_next_positions(const Matrix matrix,
    const Position source,
    const set<Position> visited,
    list<Position> &next_positions)
{
    if (OK_UP(matrix, source, visited)) {
        next_positions.push_back(Position(source.i-1, source.j));
    }
    if (OK_DOWN(matrix, source, visited)) {
        next_positions.push_back(Position(source.i+1, source.j));
    }
    if (OK_LEFT(matrix, source, visited)) {
        next_positions.push_back(Position(source.i, source.j-1));
    }
    if (OK_RIGHT(matrix, source, visited)) {
        next_positions.push_back(Position(source.i, source.j+1));
    }
}
 
/**
* Backtrack from here .
*/
void evaluate_paths(const Matrix matrix,
                    const Position source,
                    set<Position> &visited,
                    Solution &solution,
                    list<Solution> &solutions)
{
    list<Position> np;
    // Mark the source as visited
    visited.insert(source);
    // Put source int the current solution
    solution.data.push_back(ELEM(matrix, source.i, source.j));
    solution.size += 1;
    // Obtain next positions where we can go to
    get_next_positions(matrix, source, visited, np);
    // If this is a dead end we evaluate the solution
    if (!np.size()) {
        solutions.push_back(solution);
    } else {
        // We go to every possible path
        for(list<Position>::iterator it = np.begin(); it != np.end(); ++it) {
            // The visited and the solution will differ from now on, use
            // the copy constructor
            set<Position> new_visited(visited);
            Solution new_solution(solution);
            evaluate_paths(matrix, Position((*it).i, (*it).j),
                           new_visited, new_solution,
                           solutions);
        }
    }
}
 
void solution(const Matrix matrix, Solution &max)
{
    list<Solution>  solutions;
    // For every point in the matrix we backtrack
    for(int i = 0; i < matrix.size; ++i) {
        for(int j = 0; j < matrix.size ; ++j) {
            set<Position> visited;
            Solution tmp;
            evaluate_paths(matrix, Position(i,j), visited, tmp, solutions);
        }
    }
    // At this point solutions must be filtered
    for (list<Solution>::iterator i = solutions.begin(); i != solutions.end();
            i++) {
        if (max.size < (*i).size) {
            max = Solution(*i);
        } else if (max.size == (*i).size) {
            // If we more paths we the same size, choose the smallest from
            // a lexicographical point of view
            if(!lexicographical_compare(max.data.begin(), max.data.end(),
                                     (*i).data.begin(), (*i).data.end())){
               max = Solution(*i);
            }
        }
    }
}
 
//------------------------------------------------------------------------------
// MAIN
//------------------------------------------------------------------------------
int main(int argc, char *argv[])
{
    Matrix m;
    Solution max;
 
    // Read the matrix, into a matrix object, or fail miserably
    if(!read_matrix(m, FILE_IN)) {
        return (FAILURE);
    }
 
    // Determine the longest path
    solution(m, max);
 
    // Print solution to standard output
    for(list<int>::iterator i = max.data.begin(); i !=  max.data.end(); ++i){
        printf("%d ", (*i));
    }
 
    return (SUCCESS);
}

Nu am testat-o decat pe matricea primita in enunt . S-ar putea sa nu functioneze corect. Deasemenea e primul meu program in C++ (mai am insa ceva experienta cu C si Java) .

BitCell

[17] Concurs - Siruri

[17] Concurs - Siruri

Re: [17] Concurs - Siruri

Re: [17] Concurs - Siruri

Re: [17] Concurs - Siruri

Re: [17] Concurs - Siruri

Re: [17] Concurs - Siruri

Re: [17] Concurs - Siruri

Re: [17] Concurs - Siruri

Re: [17] Concurs - Siruri

Who is online