Λύσεις Β φάσης 29ου ΠΔΠ

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Λύσεις Β φάσης 29ου ΠΔΠ

Δημοσίευση από infinity » Τρί Μαρ 21, 2017 9:13 pm

Εδώ μπορείτε να αναρτήσετε και να συζητήσετε τις λύσεις σας για τα προβλήματα της Β φάσης.

Καλή επιτυχία και καλή συνέχεια σε όλους :D

Άβαταρ μέλους
Sinnosuke
Δημοσιεύσεις: 8
Εγγραφή: Τετ Αύγ 24, 2016 12:23 am

Re: Λύσεις Β φάσης 29ου ΠΔΠ

Δημοσίευση από Sinnosuke » Τετ Μαρ 22, 2017 3:55 am

Αλγόριθμος Prim με priority_queue
Πολυπλοκότητα O(nlogn)

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

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <fstream>
using namespace std;

class Graph{
	int V;
public:
	vector<vector<pair<int,int> > > adj;
	Graph(int a);
	void addEdge(int u, int v, int w);
};

Graph::Graph (int a){
	V=a;
	adj.resize(V);
}

void Graph::addEdge(int u ,int v ,int w){
	adj[u].push_back(make_pair(v,w));
	adj[v].push_back(make_pair(u,w));
}

int main() {
	ifstream fin ;
	ofstream fout;
	fin.open("uflights.in");
	fout.open("uflights.out");

	int n,m;

	fin>> n >> m;

	Graph g(n);

	for(int ii=0;ii<m;ii++){
		int u,v,w;
		fin>>u>>v>>w;
		u--;
		v--;
		g.addEdge(u,v,w);
	}

	priority_queue< pair<int,int>, vector <pair<int,int> > , greater<pair<int , int > > > priority_q;
	vector<int> dist (n,INT_MAX);
	vector<bool> used (n,false);
	priority_q.push(make_pair(0,0));
	dist[0]=0;

	long long int answer=0;
	while(priority_q.empty()==false){
		int u=priority_q.top().second;
		if(used[u]==false)answer+=priority_q.top().first;
		priority_q.pop();
		used[u]=true;
		for(int ii=0;ii<g.adj[u].size();ii++){
			int v=g.adj[u][ii].first;
			int w=g.adj[u][ii].second;
			if(used[v]==false && dist[v]>w){
				dist[v]=w;
				priority_q.push(make_pair(w,v));
			}
		}
	}

	fout << answer << endl;

	return 0;
}

qsort
Δημοσιεύσεις: 2
Εγγραφή: Δευ Μαρ 20, 2017 11:30 pm

Re: Λύσεις Β φάσης 29ου ΠΔΠ

Δημοσίευση από qsort » Τετ Μαρ 22, 2017 5:06 pm

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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <list>

#define p2Int pair<int,int>
#define pIntP2Int pair<int,p2Int>
#define Nmax 1000001

using namespace std;

int edges , N ;
bool counter[Nmax] = {false};
typedef struct node {
	int x , y ;
	int weight ;
}node;
list<node> p ;

bool lessthan(const node& a,const node& b){
	return a.weight < b.weight ;
}

int mst(void){
	int minc = 0;
	while(!p.empty()){
		for(list<node>::iterator i = p.begin() ; i !=p.end() ; i++){
			if(counter[i->x] && counter[i->y]){
				p.erase(i);
				break ;
			}else if(!counter[i->x] && !counter[i->y]){
				continue ;
			}else{
				counter[i->x] = counter[i->y] = true ;
				minc += i->weight ;
				p.erase(i);
				break;
			}
		}
	}
	return minc ;
}

int main()
{
	printf("edges: ");
	scanf("%d",&edges);
	printf("nodes: ");
	scanf("%d",&N);
	int x,y,weight ;
	printf("write me the nodes syntax : ( weight(cost) , node a , node b )-:\n");
	for(int i = 0 ; i < N ; i++){
		scanf("%d %d %d",&x,&y,&weight);
		node temp ;
		temp.weight = weight ;
		temp.x = x ;
		temp.y = y ;
		p.push_back(temp);
	}

	p.sort(lessthan);
	printf("minimum cost is : %d\n",mst());
	return 0 ;
}

qsort
Δημοσιεύσεις: 2
Εγγραφή: Δευ Μαρ 20, 2017 11:30 pm

Re: Λύσεις Β φάσης 29ου ΠΔΠ

Δημοσίευση από qsort » Τετ Μαρ 22, 2017 9:52 pm

για το γυμνάσιο:

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

#include <cstdio>
int 	N,K,A[1000001]={0},
	C[100001]={0},minC=2000000;
using namespace std;

int main(){
	FILE *in=fopen("colors.in","r"),*out=fopen("colors.out","w");
	fscanf(in,"%d%d",&N,&K);
	for(int R=1,L=1,nC=0;R<=N;R++){
		fscanf(in,"%d",A+R);
		if(C[A[R]]==0)
			nC++;
		C[A[R]] = R;
		if(nC == K){//are we colorful?
			while(L<R && C[A[L]]>L)
				L++;
			if(R-L+1 < minC)
				minC = R-L+1;
		}
	}
	fprintf(out,"%d\n",minC<=N?minC:0);
	return 0;
}
Τελευταία επεξεργασία από το μέλος Κηπουρίδης την Πέμ Μαρ 23, 2017 11:29 am, έχει επεξεργασθεί 1 φορά συνολικά.
Λόγος: Αίτημα του χρήστη qsort.

giorgosgiapis
Δημοσιεύσεις: 2
Εγγραφή: Σάβ Δεκ 31, 2016 5:50 pm

Re: Λύσεις Β φάσης 29ου ΠΔΠ

Δημοσίευση από giorgosgiapis » Τετ Μαρ 22, 2017 10:29 pm

Για το Λύκειο (αλγοριθμος Kruskal):

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

#include <bits/stdc++.h>
#define fastIo ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
using namespace std;

//#define LOCAL
#ifdef LOCAL
	#define DEBUG(x) do { cout << #x << ": " << x << '\n'; } while (0)
#else
	#define DEBUG(x) 
#endif

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

inline int read(){  
	register int c = getc_unlocked(stdin);  
	int x = 0;  
	for(; (c < 48 || c > 57); c = getc_unlocked(stdin));  
	for(; (c > 47 && c < 58); c = getc_unlocked(stdin)){ x = (x << 1) + (x << 3) + c - 48; } 
	return x;
}  

struct Edge{
	int from, to;
	int weight;
	Edge(int from, int to, int weight)
		: from(from), to(to), weight(weight) {}
};

bool cmp(const Edge& a, const Edge& b){
	return a.weight < b.weight;
}

int id[100005], Rank[100005];

void Init(int n){
	for(int i = 0; i < n; i++){
		id[i] = i;
		Rank[i] = 0;
	}
}

int Find(int u){
	while(u != id[u]){
		id[u] = id[id[u]];
		u = id[u];
	}
	return u;
}

void Union(int u, int v){	
	int i = Find(u), j = Find(v);
	if(Rank[i] < Rank[j]) id[i] = j;
	else if(Rank[i] > Rank[j]) id[j] = i;
	else{
		id[i] = j;
		Rank[j]++;
	}
}

vector<Edge> edges;

int main(){

	freopen("uflights.in", "r", stdin);
	freopen("uflights.out", "w", stdout);

	int n = read();
	int m = read();

	int a, b, w;
	for(int i = 0; i < m; i++){
		a = read(), b = read(), w = read();
		a--, b--;	
		edges.pb(Edge(a, b, w));
	}

	sort(all(edges), cmp);

	Init(n);

	int ans = 0;
	for(int i = 0; i < edges.sz(); i++){
		int u = edges[i].from, v = edges[i].to;
		if(Find(u) != Find(v)){
			Union(u, v);
			ans += edges[i].weight;
		}
	}

	printf("%d\n", ans);

	return 0;
}
Για το Γυμνάσιο:

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

#include <bits/stdc++.h>
#define fastIo ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
using namespace std;

//#define LOCAL
#ifdef LOCAL
	#define DEBUG(x) do { cout << #x << ": " << x << '\n'; } while (0)
#else
	#define DEBUG(x) 
#endif

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

int col[1000005];
map<int, int> freq;

int main(){

	freopen("colors.in", "r", stdin);
	freopen("colors.out", "w", stdout);

	int n, k;
	cin >> n >> k;

	for(int i = 0; i < n; i++) cin >> col[i];

	int l = 0, count = 0, ans = 10000009;
	for(int i = 0; i < n; i++){
		if(freq[col[i]] == 0) count++;
		freq[col[i]]++;
		if(count == k){ // Eαν στο διαστημα [l, i] εχουμε ολα τα χρωματα
			while(freq[col[l]] > 1) freq[col[l]]--, l++; // Αυξανουμε το l οσο η συνθηκη διατηρειται 
			ans = min(ans, i - l + 1);
		}
	}

	if(ans == 10000009) cout << "0\n";
	else cout << ans << '\n';

	return 0;
}
BTW τα αποτελέσματα ποτε περίπου θα βγουν?
Εικόνα

infinity
Δημοσιεύσεις: 38
Εγγραφή: Σάβ Νοέμ 26, 2011 4:08 pm

Re: Λύσεις Β φάσης 29ου ΠΔΠ

Δημοσίευση από infinity » Τρί Μαρ 28, 2017 2:04 pm

Βγήκαν τα αποτελέσματα! Πολλά συγχαρητήρια στους επιτυχόντες :D

Άβαταρ μέλους
Κηπουρίδης
Δημοσιεύσεις: 298
Εγγραφή: Παρ Φεβ 05, 2010 5:05 pm

Re: Λύσεις Β φάσης 29ου ΠΔΠ

Δημοσίευση από Κηπουρίδης » Τρί Μαρ 28, 2017 4:27 pm

Στο γυμνάσιο βλέπω έχετε βρει τη γραμμική λύση, συγχαρητήρια!

Σχετικά με το λύκειο, προσέξτε ότι κάνοντας Kruskal δε χρειάζεται να ταξινομήσετε κατά βάρος τις ακμές αφού το βάρος τους είναι πολύ μικρό (μέχρι 100). Αρκεί να κάνετε 100 πίνακες, έναν για κάθε διακριτό βάρος, και να βάλετε την κάθε ακμή στον κατάλληλο πίνακα.
Έτσι έχετε "ταξινομήσει" σε γραμμικό χρόνο, φεύγει λοιπόν το logN από την πολυπλοκότητα. Ο υπόλοιπος Kruskal τρέχει (στην πράξη) γραμμικά (στη θεωρία N*α(N) όπου α(Ν) είναι η inverse ackermann συνάρτηση, που για κάθε Ν που μπορείτε να φανταστείτε (πχ 2^(1.000.000.000.000) ) είναι μικρότερη του 5).

Θερμά συγχαρητήρια σε όλους τους διαγωνιζόμενους!
Εικόνα

Απάντηση