Entrenamiento 3 + 3.5

Entrenamiento OIA
#1

Continuamos con la siguiente tanda de problemas temáticos, esta vez todos de SPOJ:

La lista está ordenada muy subjetivamente por dificultad creciente.

En particular el problema de IOI “Mecho” conviene leerlo del PDF, ya que el enunciado de SPOJ tiene los “símbolos” perdidos. La única diferencia en SPOJ es que vienen varios casos por archivo en lugar de uno solo.

3 Me gusta
#2

¡Se suma el “3.5” o 3bis!

La mayoría de los problemas de este envío utilizaban la técnica de búsqueda binaria, o ideas relacionadas con ella. Se puede leer sobre búsqueda binaria en este artículo de la wiki:.

Además tiene dos artículos “satélite” más avanzados, uno muy importante sobre funciones unimodales y uno mucho menos importante pero interesante sobre búsqueda binaria separadora.

Estas ideas de búsqueda, además de para los problemas de este envío 3, sirven para estos dos problemas de IOI 2007 y de IOI 2017:

Se pueden enviar en este servidor ruso:

1 me gusta
#3
Comentario sobre "Copying Books"

Si tomamos

p_i = 2\cdot i+1

¿Qué problema (que ya apareció en el foro) nos queda?

Pista

Es un Desafío Ryckeboer, ¿cuál?

3 Me gusta
#4

Voy a intentar postear algunas soluciones:

Double Helix 
    #include <iostream>
    #include <vector>
    #include <stdio.h>
    #include <set>
    #include <queue>
    #include <algorithm>
    #include <string>
    using namespace std;
    #define ll long long
    ll binary(vector <ll>&vector,ll r){
    	ll low,high;
    	low=-1;
    	high=vector.size();
    	while(high-low>1){
    		ll mid=(high+low)/2;
    		if(vector[mid]==r){
    			return mid;
    		}
    		if(vector[mid]>r){
    			high=mid;
    		}
    		else{
    			low=mid;
    		}
    	}
    	return -1;
    }
    int main(){
    ll n;
    while(cin>>n){
    	ll m,paridad,a,b,ans,index,sum;
    	if(n==0){
    		break;
    	}
    	vector <ll> v;
    	vector <ll> v1;
    	vector <ll> indexs;
    	vector <ll> indexs1;
    	vector <ll> sum1;
    	vector <ll> sum2;
    	for(int i=0;i<n;i++){
    		cin>>a;
    		v.push_back(a);
    	}
    	cin>>m;
    	for(int i=0;i<m;i++){
    		cin>>a;
    		v1.push_back(a);
    		index=binary(v,a);
    		if(index!=-1){
    			indexs1.push_back(i);
    			indexs.push_back(index);
    		}
    	}
    	indexs.push_back(v.size()-1);
    	indexs1.push_back(v1.size()-1);
    	index=0;
    	for(int i=0;i<indexs.size();i++){
    		sum=0;
    		for(int j=index;j<=indexs[i];j++){
    			sum=sum+v[j];
    		}
    		sum1.push_back(sum);
    		index=indexs[i]+1;
    	}
    	index=0;
    	for(int i=0;i<indexs1.size();i++){
    		sum=0;
    		for(int j=index;j<=indexs1[i];j++){
    			sum=sum+v1[j];
    		}
    		sum2.push_back(sum);
    		index=indexs1[i]+1;
    	}
    	ans=0;
    	for(int i=0;i<sum1.size();i++){
    		ans=ans+max(sum1[i],sum2[i]);
    	}
    	
    	
    	cout<<ans<<endl;
    }
     
     
    return 0;
    }
2 Me gusta
#5
Audition (Sin binary search) 
#include <iostream>
#include <vector>
#include <stdio.h>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <bitset>
using namespace std;
#define ll long long
#define mp make_pair
int const MOD = 1000000007;
 
int main(){
int t;
cin>>t;
while(t>0){
	long long n,k,actual,count,r;
	count=0;
	actual=0;
	cin>>n>>k;
 
	string a;
	cin>>a;
	if(k==0){
		for(int i=0;i<n;i++){
			if(a[i]=='0'){
				actual++;
			}
			else{
				count=count+actual*(actual+1)/2;
				actual=0;
			}
			
		}
		count=count+actual*(actual+1)/2;
		cout<<count<<endl;
		t--;
		continue;
	}
	vector <int> v(n+1,0);
	vector <int> v1(3000000,0);
	for(int i=0;i<n;i++){
		if(a[i]=='1'){
			actual++;
			v[i+1]=actual;
		}
		else{
			v[i+1]=actual;
		}
	}
	for(int i=1;i<=n;i++){
		v1[v[i]]++;
	}
	for(int i=1;i<=n;i++){
		r=k+v[i-1];
		count=count+v1[r];
	}
	cout<<count<<endl;
	t--;	
}
return 0;
	
}
Ayuda

Por si alguien tiene WA yo tuve muchos por el caso k=0 y por no usar long long

Ada and Field 
    #include <iostream>
    #include <vector>
    #include <stdio.h>
    #include <set>
    #include <queue>
    #include <algorithm>
    #include <string>
    #include <bitset>
    using namespace std;
    #define ll long long
    #define mp make_pair
    int const MOD = 1000000007;
     
    int main(){
    int t;
    cin>>t;
    while(t>0){
    	int n,m,q,p,r,total;
    	cin>>n>>m>>q;
    	set<ll>::iterator it;
    	set <ll> ver;
    	set <ll> hor;
    	ver.insert(0);
    	ver.insert(n);
    	hor.insert(0);
    	hor.insert(m);
    	multiset <ll> sver;
    	multiset <ll> shor;
    	sver.insert(n);
    	shor.insert(m);
    	int a,b;
    	for(int i=0;i<q;i++){
    		cin>>a>>b;
    		if(a==0){
    			if(ver.count(b)==1){
    				cout<<(*sver.rbegin())*(*shor.rbegin())<<endl;
    				continue;
    			}
    			ver.insert(b);
    			it=ver.find(b);
    			++it;
    			p=*it;
    			--it;
    			--it;
    			r=*it;
    			total=p-r;
    		
    			sver.erase(sver.find(total));
    			sver.insert(p-b);
    			sver.insert(b-r);
    			cout<<(*sver.rbegin())*(*shor.rbegin())<<endl;
    		}
    		else{
    			if(hor.count(b)==1){
    				cout<<(*sver.rbegin())*(*shor.rbegin())<<endl;
    				continue;
    			}
    			hor.insert(b);
    			it=hor.find(b);
    			++it;
    			p=*it;
    			--it;
    			--it;
    			r=*it;
    			total=p-r;
    			shor.erase(shor.find(total));
    			shor.insert(p-b);
    			shor.insert(b-r);
    			cout<<(*sver.rbegin())*(*shor.rbegin())<<endl;
    		}
    		
    	}
    	
    	
    	
    	t--;
    }
     
     
    return 0;
    	
    }
Comentario

Me parece que este problema es mas data structures que binary search

2 Me gusta