Μηνιαία Πρόκληση: Μάρτιος 2021

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Άβαταρ μέλους
switch
Δημοσιεύσεις: 90
Εγγραφή: Σάβ Δεκ 05, 2015 11:46 am
Τοποθεσία: 127.0.0.1

Re: Μηνιαία Πρόκληση: Μάρτιος 2021

Δημοσίευση από switch »

Ανιιξε την εφαρμογη zoom, για join id κανεις copy paste το id και σου εβγαλε invalid?

Βαλε αυτο για id
https://ucph-ku.zoom.us/j/62298579631?p ... RQZitYZz09

Copy link address πρεπει να κανεις, οχι copy text
Άβαταρ μέλους
giorgosk
Δημοσιεύσεις: 26
Εγγραφή: Κυρ Μαρ 07, 2021 12:03 am
Επικοινωνία:

Re: Μηνιαία Πρόκληση: Μάρτιος 2021

Δημοσίευση από giorgosk »

ακριβώς έτσι τα έκανα και νγάζει invalid
Python, C++
Marilenatsiop
Δημοσιεύσεις: 27
Εγγραφή: Παρ Ιουν 12, 2020 10:04 am

Re: Μηνιαία Πρόκληση: Μάρτιος 2021

Δημοσίευση από Marilenatsiop »

Καλησπέρα σας!
Παρακάτω βρίσκονται οι κώδικες για τις λύσεις που παρουσιάσαμε στην κλήση.

Η αναπαράσταση του binary tree γίνεται με έναν διπλό πίνακα : node[1002][2] και η DFS υλοποιείται αναδρομικά.
Spoiler: show
ΛΥΣΗ Ο(Ν+Μ)
⋒ Σε αυτήν την λύση, ξεκινώ απο δύο roots που διασχίζουν ταυτόχρονα το
tree, όταν το root1 κινείται left το root2 κινείται right και αντίστροφα, οπότε το root1
είναι αντικατοπρικο του root2 (και αντίστροφα) και αυτή την πληροφορία την αποθηκεύω
στον πίνακα mirror.

Κώδικας: Επιλογή όλων

//ΛΥΣΗ Ο(Ν+Μ)

#include <iostream>
using namespace std;

int n,m,q,a,b;
int node[1002][2];
int mirror[1002];
char c;
int L=0,R=1;

void dfs(int root1,int root2){
    if(root1==0 or root2==0){
        return;
    }
    mirror[root1]=root2;
    mirror[root2]=root1;

    dfs(node[root1][L],node[root2][R]);
    dfs(node[root1][R],node[root2][L]);
}

int main()
{
    cin>>n>>m;
    for(int i=1; i<n; i++){
        cin>>a>>b>>c;
        if(c=='L'){
            node[a][L]=b;
        }else{
            node[a][R]=b;
        }
    }
    for(int i=0; i<m; i++){
       cin>>q;
       if(mirror[q]==0){
         cout<<"-1"<<'\n';
       }else{
         cout<<mirror[q]<<'\n';
       }
    }
    return 0;
}
ΛΥΣΗ Ο(Ν*Μ)
⋒ Σε αυτήν την λύση έχω πάλι 2 roots που τρέχουν ταυτόχρονα το tree, το root1 διασχίζει το left sub tree και το root2 το right sub tree με την dfs. Πρώτα διασχίζω τα external nodes και μετά τα internal nodes και αν κάποιο root βρεί το value, επιστρέφω το αντίθετο root.

Κώδικας: Επιλογή όλων

//ΛΥΣΗ Ο(Ν*Μ)

#include <iostream>
using namespace std;

int n,m,a,b,q;
char c;
int node[1002][2];
int L=0,R=1;

int dfs(int value, int root1, int root2){
    if(root1==0 or root2==0){
        return -1;
    }
    if(root1==value){
        return root2;
    }
    if(root2==value){
        return root1;
    }
    int ans=dfs(value,node[root1][L],node[root2][R]);
    if(ans>0){
        return ans;
    }
        return dfs(value,node[root1][R],node[root2][L]);
}
int main(){
    cin>>n>>m;
    for(int i=1; i<n; i++){
            cin>>a>>b>>c;
        if(c=='L'){
            node[a][L]=b;
        }else{
            node[a][R]=b;
        }
    }
    for(int i=0; i<m; i++){
        cin>>q;
        cout<<dfs(q,1,1)<<'\n';
    }
    return 0;
}
ΛΥΣΗ Ο(Ν*Μ)
⋒ Σε αυτήν την λύση έχω μόνο ένα root, το οποίο τρεχει ολο το tree μέχρι να βρει το value και αποθηκεύω τον "δρόμο" του σε έναν πίνακα path. Μετά διαβαζω τον πίνακα path αντίστροφα , δηλαδή όποτε βλέπω right , το root παει left και το αντίστροφο.

Κώδικας: Επιλογή όλων

//ΛΥΣΗ Ο(Ν*Μ)

#include <iostream>
using namespace std;

int n,m,a,b,q;
char c;
int node[1002][2];
const int L=0,R=1;
char path[1002];


bool dfs1(int value, int root, int height){
    if(root==0){
        return false;
    }
    if(root==value){
        path[height]=0;
        return true;
    }
    path[height]='L';
    if(dfs1(value,node[root][L],height+1)>0){
        return true;
    }
    path[height]='R';
    if(dfs1(value,node[root][R],height+1)>0){
        return true;
    }
    return false;
}

int dfs2(int root,int height){
    if(root==0){
        return -1;
    }
    if(path[height]=='\0'){
       return root;
    }
    if(path[height]=='L'){
        dfs2(node[root][R],height+1);
    }if(path[height]=='R'){
       dfs2(node[root][L],height+1);
    }

}

int main(){
    cin>>n>>m;
    for(int i=1; i<n; i++){
            cin>>a>>b>>c;
        if(c=='L'){
            node[a][L]=b;
        }else{
            node[a][R]=b;
        }
    }
    for(int i=0; i<m; i++){
        cin>>q;
        dfs1(q,1,0);
        cout<<dfs2(1,0)<<'\n';
    }
    return 0;
}
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Μηνιαία Πρόκληση: Μάρτιος 2021

Δημοσίευση από Κηπουρίδης »

Ορίστε και η παρουσίαση που μας έκανε η Μαριλένα. Να σημειώσω ότι λόγω τεχνικών προβλημάτων η Μαριλένα μου ζήτησε να την ανεβάσω εγώ ακριβώς μετά την κλήση.
Η αργοπορία είναι καθαρά δικό μου λάθος, ζητώ συγγνώμη.

https://www.file.io/download/231AJr2Ls7Mh
Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
radaiosm7
Δημοσιεύσεις: 18
Εγγραφή: Δευ Μαρ 23, 2020 6:31 pm

Re: Μηνιαία Πρόκληση: Μάρτιος 2021

Δημοσίευση από radaiosm7 »

Υπάρχει ένα πρόβλημα με το αρχείο οπότε θα ανέβει ξανά σήμερα.
Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 397
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Μηνιαία Πρόκληση: Μάρτιος 2021

Δημοσίευση από Κηπουρίδης »

Λύσεις θεμάτων ΠΔΠ: https://pdp-archive.github.io/
Μπούσουλας διαβάσματος ΠΔΠ: http://snf-800715.vm.okeanos.grnet.gr/PDP/
Tutorials: https://kallinikos.github.io/
Επίσημο forum ΠΔΠ: https://www.pdpforum.eu.org/forum/
Απάντηση