Hellenico Training Contest #2

Ελληνικοί διαγωνισμοί για τα παιδιά του ΠΔΠ.
feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Hellenico Training Contest #2

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

Ψηθείτε για διαγωνισμό 16-18 Σεπτεμβρίου. Άντε να παίρνουμε μπρος σιγά-σιγά. :lol:
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Hellenico Training Contest #2

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

feedWARd έγραψε:Ψηθείτε για διαγωνισμό 16-18 Σεπτεμβρίου. Άντε να παίρνουμε μπρος σιγά-σιγά. :lol:
Θα μπορούσε να γίνει στις 9 Σεπτεμβρίου ή εάν γίνεται ακόμα πιο νωρίς;
Άβαταρ μέλους
mariosal
Δημοσιεύσεις: 63
Εγγραφή: Σάβ Μαρ 20, 2010 12:00 am
Τοποθεσία: Χολαργός, Ελλάδα
Επικοινωνία:

Re: Hellenico Training Contest #2

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

Ψήθηκα, ανυπομονώ! :D
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Hellenico Training Contest #2

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

Είναι καλύτερα να ξεκινάμε απο πιο νωρίς ;)

btw ψήθηκα και εγώ :mrgreen:
feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Hellenico Training Contest #2

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

sotiris έγραψε:
feedWARd έγραψε:Ψηθείτε για διαγωνισμό 16-18 Σεπτεμβρίου. Άντε να παίρνουμε μπρος σιγά-σιγά. :lol:
Θα μπορούσε να γίνει στις 9 Σεπτεμβρίου ή εάν γίνεται ακόμα πιο νωρίς;
Δεν νομίζω ότι προλαβαίνω να τον ετοιμάσω τόσο σύντομα. Άσε που μπορεί να μην προλάβουν να ενημερωθούν όλοι όσοι θέλουν να πάρουν μέρος. Πάντως αν δεν μπορείς εκείνο το διάστημα ίσως να τον παρατείνω κατά μία μέρα.
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Hellenico Training Contest #2

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

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

Re: Hellenico Training Contest #2

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

H επισημη ανακοινωση:
http://hellenico.gr/contest/index.php?page=news&id=14

Θα παρω το ρισκο να πω οτι θα προσπαθησουμε να διοργανωνουμε εναν διαγωνισμο καθε μηνα.
Άβαταρ μέλους
zaxeilasfc
Δημοσιεύσεις: 118
Εγγραφή: Δευ Οκτ 18, 2010 8:15 pm
Τοποθεσία: Macintosh HD

Re: Hellenico Training Contest #2

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

feedWARd έγραψε:H επισημη ανακοινωση:
http://hellenico.gr/contest/index.php?page=news&id=14

Θα παρω το ρισκο να πω οτι θα προσπαθησουμε να διοργανωνουμε εναν διαγωνισμο καθε μηνα.
Αα μου ακουγεται ωραίο αυτό... Να μην ξεχνιώμαστε και να περιμένουμε την κάθε φάση... +1 feedWARd
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Hellenico Training Contest #2

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

feedWARd έγραψε:H επισημη ανακοινωση:
http://hellenico.gr/contest/index.php?page=news&id=14

Θα παρω το ρισκο να πω οτι θα προσπαθησουμε να διοργανωνουμε εναν διαγωνισμο καθε μηνα.
Τα θέματα αυτά θα προστεθούν και στο training site του hellenico;
+1 για το ρίσκο.
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Hellenico Training Contest #2

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

Πολύ ωραία προβλήματα :), ανυπομονώ για τον επόμενο μήνα!
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
dimos
Δημοσιεύσεις: 18
Εγγραφή: Τρί Ιούλ 12, 2011 6:02 pm
Τοποθεσία: Σέρρες

Re: Hellenico Training Contest #2

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

Τα προβλήματα ήταν πολύ ωραία!Δυστυχώς δεν πρόλαβα να τα λύσω και τα 4 γιατί σε ένα με έφαγαν τα strings και οι δείκτες. :| Πιστεύω τον άλλο μήνα καλύτερα. :)
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Hellenico Training Contest #2

Δημοσίευση από 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;
}
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Hellenico Training Contest #2

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

compileGuy έγραψε: ΥΓ: Κάποιος που κατέχει το debugging γίνεται να μου αναλύσει γιατι ο κώδικας που υπέβαλα για το cave πετάει Runtime Error :roll:
1) Αναδρομική DFS με 300000 nodes.
2) Λίστα μέγιστου μεγέθους 300000 * 300000 = 90000000000 integers
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Hellenico Training Contest #2

Δημοσίευση από 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 θέσεις πίνακα.
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Hellenico Training Contest #2

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

Στο πρόβλημα frog διαθέτετε λύση DP που να πιάνει 100?
Επίσης μπορεί κάποιος να αποδείξει γιατί δουλεύει πάντα η Greedy λύση;
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Hellenico Training Contest #2

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

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

@sotiris:
Ποιά greedy;

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

ΥΓ2:
Γεια στο κουράγιο του MC Hatz και του User που μας έστησαν κι άλλο διαγωνισμό, ειδικά για τα αστραπιαία αποτελέσματα :)
Συνημμένα
nico_9_2011.zip
4 προγράμματα, 3 γραμμές σχολίων :P
(2.38 KiB) Μεταφορτώθηκε 278 φορές
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Hellenico Training Contest #2

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

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

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

Re: Hellenico Training Contest #2

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

@kernelpanic

Δεν νομιζω το πρόβλημα να είναι στο βάθος της dfs όσο σε λάθος σε δομή δεδομένων( vector ισως :| ). Σε κάθε αναδρομική κλήση δεσμεύει 5 bytes (4 + 1) οπότε σε καμιά περίπτωση δεν είναι θέμα .
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Hellenico Training Contest #2

Δημοσίευση από 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;
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Hellenico Training Contest #2

Δημοσίευση από 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....
Απάντηση