Σελίδα 1 από 2

Hellenico Training Contest #2

Δημοσιεύτηκε: Σάβ Σεπ 03, 2011 6:37 am
από feedWARd
Ψηθείτε για διαγωνισμό 16-18 Σεπτεμβρίου. Άντε να παίρνουμε μπρος σιγά-σιγά. :lol:

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Σάβ Σεπ 03, 2011 12:54 pm
από pman
feedWARd έγραψε:Ψηθείτε για διαγωνισμό 16-18 Σεπτεμβρίου. Άντε να παίρνουμε μπρος σιγά-σιγά. :lol:
Θα μπορούσε να γίνει στις 9 Σεπτεμβρίου ή εάν γίνεται ακόμα πιο νωρίς;

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Σάβ Σεπ 03, 2011 5:54 pm
από mariosal
Ψήθηκα, ανυπομονώ! :D

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Κυρ Σεπ 04, 2011 6:18 pm
από compileGuy
Είναι καλύτερα να ξεκινάμε απο πιο νωρίς ;)

btw ψήθηκα και εγώ :mrgreen:

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Κυρ Σεπ 04, 2011 9:12 pm
από feedWARd
sotiris έγραψε:
feedWARd έγραψε:Ψηθείτε για διαγωνισμό 16-18 Σεπτεμβρίου. Άντε να παίρνουμε μπρος σιγά-σιγά. :lol:
Θα μπορούσε να γίνει στις 9 Σεπτεμβρίου ή εάν γίνεται ακόμα πιο νωρίς;
Δεν νομίζω ότι προλαβαίνω να τον ετοιμάσω τόσο σύντομα. Άσε που μπορεί να μην προλάβουν να ενημερωθούν όλοι όσοι θέλουν να πάρουν μέρος. Πάντως αν δεν μπορείς εκείνο το διάστημα ίσως να τον παρατείνω κατά μία μέρα.

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Κυρ Σεπ 04, 2011 9:20 pm
από pman
feedWARd έγραψε:
sotiris έγραψε:
feedWARd έγραψε:Ψηθείτε για διαγωνισμό 16-18 Σεπτεμβρίου. Άντε να παίρνουμε μπρος σιγά-σιγά. :lol:
Θα μπορούσε να γίνει στις 9 Σεπτεμβρίου ή εάν γίνεται ακόμα πιο νωρίς;
Δεν νομίζω ότι προλαβαίνω να τον ετοιμάσω τόσο σύντομα. Άσε που μπορεί να μην προλάβουν να ενημερωθούν όλοι όσοι θέλουν να πάρουν μέρος. Πάντως αν δεν μπορείς εκείνο το διάστημα ίσως να τον παρατείνω κατά μία μέρα.
ΟΚ

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Τετ Σεπ 07, 2011 1:14 pm
από feedWARd
H επισημη ανακοινωση:
http://hellenico.gr/contest/index.php?page=news&id=14

Θα παρω το ρισκο να πω οτι θα προσπαθησουμε να διοργανωνουμε εναν διαγωνισμο καθε μηνα.

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Σάβ Σεπ 10, 2011 2:27 am
από zaxeilasfc
feedWARd έγραψε:H επισημη ανακοινωση:
http://hellenico.gr/contest/index.php?page=news&id=14

Θα παρω το ρισκο να πω οτι θα προσπαθησουμε να διοργανωνουμε εναν διαγωνισμο καθε μηνα.
Αα μου ακουγεται ωραίο αυτό... Να μην ξεχνιώμαστε και να περιμένουμε την κάθε φάση... +1 feedWARd

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Σάβ Σεπ 10, 2011 2:23 pm
από pman
feedWARd έγραψε:H επισημη ανακοινωση:
http://hellenico.gr/contest/index.php?page=news&id=14

Θα παρω το ρισκο να πω οτι θα προσπαθησουμε να διοργανωνουμε εναν διαγωνισμο καθε μηνα.
Τα θέματα αυτά θα προστεθούν και στο training site του hellenico;
+1 για το ρίσκο.

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Σάβ Σεπ 17, 2011 10:52 pm
από chris
Πολύ ωραία προβλήματα :), ανυπομονώ για τον επόμενο μήνα!

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Κυρ Σεπ 18, 2011 1:30 am
από dimos
Τα προβλήματα ήταν πολύ ωραία!Δυστυχώς δεν πρόλαβα να τα λύσω και τα 4 γιατί σε ένα με έφαγαν τα strings και οι δείκτες. :| Πιστεύω τον άλλο μήνα καλύτερα. :)

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Δευ Σεπ 19, 2011 9:59 pm
από compileGuy
Πολύ ωραία προβλήματα και φανταστικός διαγωνισμός. Συγχαρητήρια σε όλους που συμμετείχαν. ;)

Ευχαριστούμε θερμά τους διοργανωτές και ανυπομονώ για τον επόμενο διαγωνισμο :mrgreen:

ΥΓ: Κάποιος που κατέχει το debugging γίνεται να μου αναλύσει γιατι ο κώδικας που υπέβαλα για το cave πετάει Runtime Error :roll:
Spoiler: show

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

#include<iostream>
#include<stdio.h>
#include<string>
#include<cstring>
#include<stdlib.h>
#include<vector>

#define MAXN 300005
using namespace std;

vector<vector<int> > v;
int group[MAXN];
int N,M,W,gr,gr2;

void dfs(int n,bool f)
{
	group[n] = gr;
	vector<int>::iterator it;
	for(it = v[n].begin();it!=v[n].end();it++){
		if(f && !group[*it])
			dfs(*it,f);
		else if(!f && group[*it] == gr2)
			dfs(*it,f);
	}
}

int main()
{

	FILE* fin = fopen("caves.in","r");
	FILE* fout = fopen("caves.out","w");
	int i,f,t;
	v.resize(MAXN);

	// reading //
	fscanf(fin,"%d %d",&N,&M);
	for(i=0;i<M;i++){
		fscanf(fin,"%d %d",&f,&t);
		v[f].push_back(t);
		v[t].push_back(f);
	}
	
	// find groups of nodes //
	gr = 1;
	for(i=1;i<=N;i++)
	{
		if(!group[i]){
			gr++;
			dfs(i,true);
		}
	}

	// do queries //
	fscanf(fin,"%d\n",&W);
	char q;
	for(i=0;i<W;i++){
		fscanf(fin,"%c %d %d\n",&q,&f,&t);

		if(q == 'Q')
		{
			if(group[f] == group[t])
				fprintf(fout,"Y\n");
			else fprintf(fout,"N\n");
		}
		else if(q == 'C'){
			group[f] = group[t];
			v[f].push_back(t);
			v[t].push_back(f);
		}
		else if (q == 'P')
		{
			gr = group[f];
			gr2 = group[t];
			v[f].push_back(t);
			v[t].push_back(f);
			dfs(t,false);
		}
	}

	return 0;
}

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Δευ Σεπ 19, 2011 10:22 pm
από chris
compileGuy έγραψε: ΥΓ: Κάποιος που κατέχει το debugging γίνεται να μου αναλύσει γιατι ο κώδικας που υπέβαλα για το cave πετάει Runtime Error :roll:
1) Αναδρομική DFS με 300000 nodes.
2) Λίστα μέγιστου μεγέθους 300000 * 300000 = 90000000000 integers

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Δευ Σεπ 19, 2011 10:36 pm
από compileGuy
chris έγραψε:
compileGuy έγραψε: ΥΓ: Κάποιος που κατέχει το debugging γίνεται να μου αναλύσει γιατι ο κώδικας που υπέβαλα για το cave πετάει Runtime Error :roll:
1) Αναδρομική DFS με 300000 nodes.
2) Λίστα μέγιστου μεγέθους 300000 * 300000 = 90000000000 integers
Νομιζω πως κανεις λάθος:
Δεν έχω σε καθε dfs 300.000 nodes (απλα έχω τον αριθμο του κομβου ;) ). Αντίθετα έχω εναν πίνακα με 300.000 θέσεις και συνολικα σε αυτες μπαίνουν ακόμα 2*Μ ints. Άρα έχω 300.000+200.000 = 500.000 θέσεις πίνακα.

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Δευ Σεπ 19, 2011 10:46 pm
από pman
Στο πρόβλημα frog διαθέτετε λύση DP που να πιάνει 100?
Επίσης μπορεί κάποιος να αποδείξει γιατί δουλεύει πάντα η Greedy λύση;

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Δευ Σεπ 19, 2011 11:11 pm
από kernelpanic
@compileguy:
Ποιό είναι το μέγιστο βάθος της αναδρομικής κλήσης; Νομίζω στα περίπου 2ΜΒ στοίβας καίγεσαι ;)

@sotiris:
Ποιά greedy;

ΥΓ:
Τελικά πόσο μεγάλη ήταν η μεγαλύτερη σειρά γραμμάτων στο compress που έπρεπε να αναγραφεί ολογράφως; Δε το έλεγε στην εκφώνηση :?

ΥΓ2:
Γεια στο κουράγιο του MC Hatz και του User που μας έστησαν κι άλλο διαγωνισμό, ειδικά για τα αστραπιαία αποτελέσματα :)

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Δευ Σεπ 19, 2011 11:17 pm
από chris
sotiris έγραψε:Στο πρόβλημα frog διαθέτετε λύση DP που να πιάνει 100?
Επίσης μπορεί κάποιος να αποδείξει γιατί δουλεύει πάντα η Greedy λύση;
Υπάρχει λύση O(1) νομίζω, αλλά γίνεται εύκολα O(N) αν βαριέσαι να ψάχνεις τύπους.

Δεν είμαι βέβαιος, αλλά νομίζω πως μια γρήγορη εξήγηση είναι αυτή:
Spoiler: show
Για να ελαχιστοποιήσεις το άθροισμα τετραγώνων πρέπει οι αριθμοί να είναι όσο πιο ομοιόμορφα μοιρασμένοι γίνεται. Άρα, αν (Ν-1)%Κ=0, και οι Κ αριθμοί μπορούν να είναι ίσοι και δεν έχεις πρόβλημα. Αν υπάρχει υπόλοιπο (R=(N-1)%K και προφανώς R<Κ), τότε πρέπει να το μοιράσεις σε Κ αριθμούς όσο πιο ομοιόμορφα γίνεται. Επειδή R<Κ, απλώς πρέπει να προσθέσεις 1 σε R αριθμούς. ~Κάτι τέτοιο.~

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Δευ Σεπ 19, 2011 11:19 pm
από compileGuy
@kernelpanic

Δεν νομιζω το πρόβλημα να είναι στο βάθος της dfs όσο σε λάθος σε δομή δεδομένων( vector ισως :| ). Σε κάθε αναδρομική κλήση δεσμεύει 5 bytes (4 + 1) οπότε σε καμιά περίπτωση δεν είναι θέμα .

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Δευ Σεπ 19, 2011 11:23 pm
από chris
compileGuy έγραψε:
chris έγραψε:
compileGuy έγραψε: ΥΓ: Κάποιος που κατέχει το debugging γίνεται να μου αναλύσει γιατι ο κώδικας που υπέβαλα για το cave πετάει Runtime Error :roll:
1) Αναδρομική DFS με 300000 nodes.
2) Λίστα μέγιστου μεγέθους 300000 * 300000 = 90000000000 integers
Νομιζω πως κανεις λάθος:
Δεν έχω σε καθε dfs 300.000 nodes (απλα έχω τον αριθμο του κομβου ;) ). Αντίθετα έχω εναν πίνακα με 300.000 θέσεις και συνολικα σε αυτες μπαίνουν ακόμα 2*Μ ints. Άρα έχω 300.000+200.000 = 500.000 θέσεις πίνακα.
Εννοώ πως μπορεί η αναδρομή να είναι πολύ μεγάλη στο (1). Στο (2) θέλω να πως πως αν κρατάς όλον τον γράφο πιθανώς να καίγεσαι από μνήμη. Παίρνεις Runtime Error και στα μικρά testcases;

Re: Hellenico Training Contest #2

Δημοσιεύτηκε: Δευ Σεπ 19, 2011 11:30 pm
από compileGuy
chris έγραψε:
compileGuy έγραψε:
chris έγραψε:
compileGuy έγραψε: ΥΓ: Κάποιος που κατέχει το debugging γίνεται να μου αναλύσει γιατι ο κώδικας που υπέβαλα για το cave πετάει Runtime Error :roll:
1) Αναδρομική DFS με 300000 nodes.
2) Λίστα μέγιστου μεγέθους 300000 * 300000 = 90000000000 integers
Νομιζω πως κανεις λάθος:
Δεν έχω σε καθε dfs 300.000 nodes (απλα έχω τον αριθμο του κομβου ;) ). Αντίθετα έχω εναν πίνακα με 300.000 θέσεις και συνολικα σε αυτες μπαίνουν ακόμα 2*Μ ints. Άρα έχω 300.000+200.000 = 500.000 θέσεις πίνακα.
Εννοώ πως μπορεί η αναδρομή να είναι πολύ μεγάλη στο (1). Στο (2) θέλω να πως πως αν κρατάς όλον τον γράφο πιθανώς να καίγεσαι από μνήμη. Παίρνεις Runtime Error και στα μικρά testcases;
Μπα δεν είναι η μνήμη το θέμα. Το hellenico μου βγάζει "σφάλμα κατάτμησης"( που κατά κύριο λόγο είναι το πρόβλημα που δεν τυπώνει στο αρχείο εξόδου) . Μέτα από αυτό δοκίμασα τα testcases manually και είδα πως όντως δεν τύπωνε και κάπου έχω θέμα στην dfs . Λες να είναι όντως inf-loop στην dfs; ( παίζει ... )

EDIT: Και ναι σε κάποια μικρά παίρνω Runtime-Error....