OIS 2017/2018 - Round 2

Olimpiadi
1

Ciao a tutti!
Domani pomeriggio, dalle 15:00 alle 18:00, è in programma la seconda gara dell’edizione 2017/2018 delle Olimpiadi di Informatica a Squadre.

Per chi volesse scaricare i testi dei problemi o partecipare in forma non ufficiale, una gara è disponibile all’indirizzo https://training.olinfo.it/contests con relativa classifica all’indirizzo https://squadre.olinfo.it/ranking2. Si accede con le stesse credenziali di questa piattaforma. Non viene garantita la responsività del server per la gara non ufficiale.

Inoltre, per garantire una equa competizione ai partecipanti alla gara ufficiale, questa piattaforma (forum incluso) sarà temporaneamente oscurata per la durata della stessa.

Buona gara!

1 Mi Piace
2

Per aumentare la suspense… sette suggerimenti per provare a indovinare i sette problemi :stuck_out_tongue_winking_eye:

teaser

3 Mi Piace
3

Il terzo sembrerebbe fractal_painting 2.0 :sweat_smile:

1 Mi Piace
4

Per fortuna non lo era :sweat_smile:

1 Mi Piace
5

Quale era la strategia ottimale per search(l’esercizio nel quale ti veniva fornita una matrice di char e dovevi cercare quante volte era presente una parola potendo muoverti in tutte le direzione e potendo ripassare su una cella già utilizzata)

Io ho usato un approccio ricorsivo con l’aggiunta delle memoizzazione, ma si è dimostrato inefficiente anche se solo per un caso(70/100).

1 Mi Piace
6

La nostra soluzione è stata proprio quella, forse salvi in maniera poco efficiente la memo?

1 Mi Piace
7

Era una funzione del tipo
Int solve (int i, int j, int usati)
i e j rappresentano gli indici dell ultima casella utilizzata è usati rappresenta a quale lettera ci si trova (usati=0 -> prima lettera)
In memo [i][j][usati] avevo la somma dele combinazioni ottenibili partendo da i j andando nelle 8 direzioni

1 Mi Piace
8

L’algoritmo è praticamente uguale.

1 Mi Piace
9

Si trattava di TLE o MLE?

4 Mi Piace
10

TLE , appena recupero il codice lo posto.

1 Mi Piace
11 
#include<fstream>
#include<string>
#include<stdlib.h>
#include<iostream>
using namespace std;
int const MAXN=110;
string s;
int r,c;
char A[MAXN][MAXN];
int mem[MAXN][MAXN][1001];
int solve(int i, int j, int usati)
{
        long long int ris=0;
        if(usati==s.length())      return 1;
    if(mem[i][j][usati]!=0)
                           return mem[i][j][usati];
    
    else{

    if(i>0 && j>0 && A[i-1][j-1]==s[usati])     //a s
           { ris+=solve(i-1 , j-1, usati +1);     ris%=1000000007;}
    if(i>0 && A[i-1][j]==s[usati])             //a
         {  ris+=solve(i-1 , j, usati +1);    ris%=1000000007;}
    if(i>0 && j<c-1 && A[i-1][j+1]==s[usati])  //alt des
         {  ris+=solve(i-1 , j+1, usati +1);    ris%=1000000007;}         
    if(j>0 && A[i][j-1]==s[usati])             //sin
          { ris+=solve(i , j-1, usati +1);    ris%=1000000007;}
    if(j<c-1 && A[i][j+1]==s[usati])           //des
          { ris+=solve(i , j+1, usati +1);    ris%=1000000007;}
    if(j>0 && i<r-1 && A[i+1][j-1]==s[usati])             //bass sin
          { ris+=solve(i+1 , j-1, usati +1);    ris%=1000000007;}
    if(i<r-1 && A[i+1][j]==s[usati])                                 //bas 
          { ris+=solve(i+1 , j, usati +1);    ris%=1000000007;}
    if(i<r-1 && j<c-1 && A[i+1][j+1]==s[usati])
         {  ris+=solve(i+1 , j+1, usati +1);    ris%=1000000007;}
    ris%=1000000007;
    }
    mem[i][j][usati]=ris;
    return ris;
}

int main()
{
    ifstream in("input.txt");
    ofstream out("output.txt");
    in>>s;
    long long int ris=0;
    in>>r>>c;
    for(int i=0;i<r;i++)       for(int j=0;j<c;j++)     in>>A[i][j];
    for(int i=0;i<r;i++)       for(int j=0;j<c;j++)     if(A[i][j]==s[0])   
    {
            ris+=solve(i, j,1);
            ris%=1000000007;
    }
    out<<ris;    
}
1 Mi Piace
12

Mi duole ravvisare che il sito web da lei proposto non è attualmente funzionante. Ogni qualvolta io abbia eseguito un tentativo di accesso alla prova, mi è stato ricordato che la seguente è gia terminata pocanzi.
Attendo chiarimenti
Grazie
Distinti Saluti

Zanettemerda

13

Se per sito web s’intende https://training.olinfo.it/contests , allora è corretto che ora non sia più possibile accedere alla gara mirror. Questa infatti resta attiva solo per 24 ore dall’inizio della gara principale.

Ad ogni modo, come per tutte le precedenti gare a breve i problemi verranno caricati sul portale di allenamento (ovvero questa stessa piattaforma: https://training.olinfo.it) dove resteranno consultabili e risolvibili senza restrizioni temporali.

14

Ok risolto era un errore molto imbarazzante :sweat_smile:

1 Mi Piace
15

Salve a tutti, io ho un grande dilemma a proposito dell’immagine in basso a destra:
se il testo dei problemi è in inglese, perché la foto degli ammessi ha le parole in italiano? :confused:

2 Mi Piace
16

Perché è stata la prima foto trovata che mi piacesse (e la sua interpretazione non è così language dependent).

Ci sono dilemmi ben più grandi :rofl:

1 Mi Piace
17

No no, questo dilemma è di quelli superiori ai quali non siamo in grado di trovarne da noi una risposta e abbiamo bisogno che qualche essere superiore ce la riveli; un po’ come la risposta alla domanda su quale sia il senso della vita.

18

Beh, lí non ci sono dubbi: 42

5 Mi Piace