Hellenico Training Contest #2

[feedWARd]

Ψηθείτε για διαγωνισμό 16-18 Σεπτεμβρίου. Άντε να παίρνουμε μπρος σιγά-σιγά.

[pman]

Ψηθείτε για διαγωνισμό 16-18 Σεπτεμβρίου. Άντε να παίρνουμε μπρος σιγά-σιγά.

Θα μπορούσε να γίνει στις 9 Σεπτεμβρίου ή εάν γίνεται ακόμα πιο νωρίς;

[mariosal]

Ψήθηκα, ανυπομονώ!

[compileGuy]

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

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

[feedWARd]

Ψηθείτε για διαγωνισμό 16-18 Σεπτεμβρίου. Άντε να παίρνουμε μπρος σιγά-σιγά.

Θα μπορούσε να γίνει στις 9 Σεπτεμβρίου ή εάν γίνεται ακόμα πιο νωρίς;

Δεν νομίζω ότι προλαβαίνω να τον ετοιμάσω τόσο σύντομα. Άσε που μπορεί να μην προλάβουν να ενημερωθούν όλοι όσοι θέλουν να πάρουν μέρος. Πάντως αν δεν μπορείς εκείνο το διάστημα ίσως να τον παρατείνω κατά μία μέρα.

[pman]

Ψηθείτε για διαγωνισμό 16-18 Σεπτεμβρίου. Άντε να παίρνουμε μπρος σιγά-σιγά.

Θα μπορούσε να γίνει στις 9 Σεπτεμβρίου ή εάν γίνεται ακόμα πιο νωρίς;

Δεν νομίζω ότι προλαβαίνω να τον ετοιμάσω τόσο σύντομα. Άσε που μπορεί να μην προλάβουν να ενημερωθούν όλοι όσοι θέλουν να πάρουν μέρος. Πάντως αν δεν μπορείς εκείνο το διάστημα ίσως να τον παρατείνω κατά μία μέρα.

ΟΚ

[feedWARd]

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

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

[zaxeilasfc]

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

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

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

[pman]

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

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

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

[chris]

Πολύ ωραία προβλήματα , ανυπομονώ για τον επόμενο μήνα!

[dimos]

Τα προβλήματα ήταν πολύ ωραία!Δυστυχώς δεν πρόλαβα να τα λύσω και τα 4 γιατί σε ένα με έφαγαν τα strings και οι δείκτες. Πιστεύω τον άλλο μήνα καλύτερα.

[compileGuy]

Πολύ ωραία προβλήματα και φανταστικός διαγωνισμός. Συγχαρητήρια σε όλους που συμμετείχαν.

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

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

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]

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

1) Αναδρομική DFS με 300000 nodes.
2) Λίστα μέγιστου μεγέθους 300000 * 300000 = 90000000000 integers

[compileGuy]

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

1) Αναδρομική DFS με 300000 nodes.
2) Λίστα μέγιστου μεγέθους 300000 * 300000 = 90000000000 integers

Νομιζω πως κανεις λάθος:
Δεν έχω σε καθε dfs 300.000 nodes (απλα έχω τον αριθμο του κομβου ). Αντίθετα έχω εναν πίνακα με 300.000 θέσεις και συνολικα σε αυτες μπαίνουν ακόμα 2*Μ ints. Άρα έχω 300.000+200.000 = 500.000 θέσεις πίνακα.

[pman]

Στο πρόβλημα frog διαθέτετε λύση DP που να πιάνει 100?
Επίσης μπορεί κάποιος να αποδείξει γιατί δουλεύει πάντα η Greedy λύση;

[kernelpanic]

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

@pman:
Ποιά greedy;

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

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

[chris]

Στο πρόβλημα frog διαθέτετε λύση DP που να πιάνει 100?
Επίσης μπορεί κάποιος να αποδείξει γιατί δουλεύει πάντα η Greedy λύση;

Υπάρχει λύση O(1) νομίζω, αλλά γίνεται εύκολα O(N) αν βαριέσαι να ψάχνεις τύπους.

Δεν είμαι βέβαιος, αλλά νομίζω πως μια γρήγορη εξήγηση είναι αυτή:

Spoiler: show

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

[compileGuy]

@kernelpanic

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

[chris]

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

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;

[compileGuy]

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

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....