10020 - Minimal coverage

mgavin2 · Post by **mgavin2** » Sat Nov 17, 2012 8:31 pm

Yay brianfry713, I can always count on you

It seems my approach to this problem is awkwardly wrong... I really need to start over and come up with a new way of thinking... but it's tough :\
because for now, instead of trying to do it correctly (which I'm not somehow) , I'm trying to patch in special case handling... argh

brianfry713 · Post by **brianfry713** » Tue Nov 20, 2012 3:05 am

Greedily choose the next segment that covers the most additional points to the right of those already covered. You're choosing the maximum length segment instead, which as I pointed out in my test case, won't work.

mgavin2 · Post by **mgavin2** » Mon Nov 26, 2012 9:43 pm

brianfry713 wrote:Greedily choose the next segment that covers the most additional points to the right of those already covered. You're choosing the maximum length segment instead, which as I pointed out in my test case, won't work.

omg. yay. "yay"*1000

thank you so much for your continued help

DiegoTrivino · Post by **DiegoTrivino** » Thu Dec 13, 2012 1:16 am

I would like to know which case this code in Java does not work. I have tried several cases and no meeting which is failing. Can you help me telling which case fails?

The code Java is:

Code: Select all

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

// uva code 10020
class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args){
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String linea;
		ArrayList<String> intervalos;
		int casosPrueba;
		try {
			casosPrueba = Integer.parseInt(br.readLine());
			for(int i=0;i<casosPrueba;i++)
			{
				intervalos = new ArrayList<String>();
				br.readLine();
				ArrayList<String> solucion = new ArrayList<String>();
				int segmentoM = Integer.parseInt(br.readLine());
				while(!(linea = br.readLine()).equals("0 0"))
					intervalos.add(linea);
				solucion=voraz(segmentoM,intervalos);
				if(solucion.size()==0)
					System.out.println("0");
				else{
					System.out.println(objetivo(solucion));
					for(int j=0;j<solucion.size();j++)
						System.out.println(solucion.get(j));
				}
				if(i+1!=casosPrueba)System.out.println();
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	static ArrayList<String> voraz(int M,ArrayList<String> intervalos) {
		ArrayList<String> solucion=new ArrayList<String>();
		int conexion=0;
		boolean haySeleccion = true,haySolucion;
		while(!(haySolucion=solucion(solucion,M)) && haySeleccion){
			String nuevoElemento=seleccioneIntervalo(conexion,intervalos),numeros[];
			if(nuevoElemento!=null)
			{
				solucion.add(nuevoElemento);
				numeros=nuevoElemento.split(" ");
				conexion=Integer.parseInt(numeros[1]);
			}
			else{
				haySeleccion=false;
			}
		}
		if(!haySolucion)solucion = new ArrayList<String>();
		return solucion;
	}

	static String seleccioneIntervalo(int conexion, ArrayList<String> intervalos) {
		int posicion = -1,tamanoIntervalo=0;
		String solucion=null;
		for(int i=0;i<intervalos.size();i++){
			String lineas[]=intervalos.get(i).split(" ");
			int l=Integer.parseInt(lineas[0]),r=Integer.parseInt(lineas[1]);
			if(seEncuentraEnIntervalo(conexion,l,r) && r-conexion>tamanoIntervalo){
				posicion=i;
				tamanoIntervalo=r-conexion;
			}
		}
		if(posicion!=-1){
			solucion=intervalos.get(posicion);
			intervalos.remove(posicion);
		}
		return solucion;
	}

	static boolean solucion(ArrayList<String> solucion, int M) {
		int conexion=0;
		boolean hayErrores=true;
		String lineas[];
		if(solucion.size()!=0)
		{
			lineas=solucion.get(solucion.size()-1).split(" ");
			if(seEncuentraEnIntervalo(M,Integer.parseInt(lineas[0]),Integer.parseInt(lineas[1])))
				hayErrores=false;
			for(int i=0;i<solucion.size()&&!hayErrores;i++){
				lineas=solucion.get(i).split(" ");
				if(seEncuentraEnIntervalo(conexion,Integer.parseInt(lineas[0]),Integer.parseInt(lineas[1])))
					hayErrores=false;
				conexion=Integer.parseInt(lineas[1]);
			}
		}
		return !hayErrores;
	}

	static boolean seEncuentraEnIntervalo(int numero,int l, int r){
		return (l<=numero && numero<=r);	
	}

	static int objetivo(ArrayList<String> solucion) {
		return solucion.size();
	}

}

a.elbashandy · Post by **a.elbashandy** » Wed Mar 06, 2013 11:16 pm

What's wrong with my code ? it solves all the test cases correctly.

Code: Select all

Removed after AC

brianfry713 · Post by **brianfry713** » Thu Mar 07, 2013 3:22 am

Input:

Code: Select all

AC Output:

Code: Select all

a.elbashandy · Post by **a.elbashandy** » Thu Mar 07, 2013 1:45 pm

AC. Thanks a lot brianfry713

tridorje · Post by **tridorje** » Mon Oct 07, 2013 8:11 pm

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

long itest, ntest;
long m, pt;
long r, l;
bool thoat, brk;
long len[120000];
long a[120000];

struct data
{

long l;
long r;
};
data luu[200000];

void out(long tt)
{

long i;

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

for(i = 1; i <= tt; i++)
printf("%ld %ld\n", luu[ a ].l, luu[ a ].r);
}

void input()
{

thoat = true;
bool si;
si = false;
scanf("%ld", &m);
pt = 0;

luu[0].l = 0;
luu[0].r = m;

while(1)
{

scanf("%ld %ld", &l, &r);

if(l == 0 && r == 0)
break;

if( !(l >= r || r <= 0 || l >= m ) )
{

if(si == false)
thoat = false;

if(l <= 0 && r >= m && si == false)
{

thoat = true;
printf("1\n%ld %ld\n", l, r);
si = true;
}

if(si == false)
{
++pt;
luu[pt].l = l;
luu[pt].r = r;
}
}
}

if(thoat == true && si == false)
printf("0\n");
}

int check(long truoc, long sau)
{

if( !( luu[sau].l > luu[truoc].l && luu[sau].l <= luu[truoc].r ) )
return 0;

if( !( luu[sau].r >= luu[truoc].r ) )
return 0;

return 1;
}

long dq(int vt)
{

long i, best, tmp;
best = 999999;
bool si;
si = false;

if(check(0, vt) == 1)
{

len[vt] = 1;
return 1;
}

for(i = 1; i <= pt; i++)
{

if(i != vt && len > 0 && len <= 100000 && check(vt, i) == 1)
{

tmp = len + 1;
best = min(best, tmp);
}

if(i != vt && len == 120000 && check(vt, i) == 1)
{

tmp = 1 + dq(i);
best = min(best, tmp);
}
}

if(best > 100000)
{

len[vt] = 999999;
return 999999;
}

len[vt] = best;
return best;
}

void dq_out(long vt, long tt, long gt)
{

int i;

if(gt == 0)
{

out(tt - 1);
brk = true;
return;
}

for(i = 1; i <= pt; i++)
{

if(i != vt && len == gt && check(vt, i) == 1)
{

a[tt] = i;
dq_out(i, tt + 1, gt - 1);

if(brk == true)
break;
}
}
}

void solve()
{

long i, bestmin, xp;
bestmin = 999999;
xp = 0;

for(i = 0; i < pt + 5; i++)
len = 120000;

for(i = 1; i <= pt; i++)
{

if(len == 120000 && luu.l <= 0)
len[i] = dq(i);

if(luu[i].l <= 0)
{

bestmin = min(len[i], bestmin);

if(len[i] == bestmin)
xp = i;
}
}

if(len[xp] <= 100000)
{

a[1] = xp;
dq_out(xp, 2, len[xp] - 1);
}
else
printf("0\n");
}

int main()
{

//freopen("10020.inp", "r", stdin);
//freopen("10020.out", "w", stdout);

scanf("%ld", &ntest);

for(itest = 0; itest < ntest; itest++)
{

if(itest != 0)
printf("\n");

input();

if(thoat == false)
solve();
}

return(0);
}

tridorje · Post by **tridorje** » Mon Oct 07, 2013 8:19 pm

Can some body help my. I don't know about Greedy

. In 10020 problem, in the maximum test case - (Each test case in the input should contains an integer M(1<=M<=5000), followed by pairs "Li Ri"(|Li|, |Ri|<=50000, i<=100000), ) i = 100000, may I use Depth first search with Dynamic programing.

brianfry713 · Post by **brianfry713** » Tue Oct 08, 2013 12:51 am

brianfry713 wrote:Greedily choose the next segment that covers the most additional points to the right of those already covered.

tridorje · Post by **tridorje** » Tue Oct 08, 2013 3:21 am

brianfry713 wrote:
brianfry713 wrote:Greedily choose the next segment that covers the most additional points to the right of those already covered.

Thank !

TryCatchMe · Post by **TryCatchMe** » Thu Jun 19, 2014 1:16 am

brainfry - Thank you so much for all of your sample IO. You have helped me so much over the past month or so since I started these problems. I really appreciate it.

Anyways, to the rest of the people who read this... the description does not say the input will be integers, BUT I used a greedy algorithm like everyone else ( with a few optimizations ) and only used int's and got AC.

dhruba07 · Post by **dhruba07** » Mon Jun 30, 2014 11:47 pm

I have followed this algorithm of the blog :

Code: Select all

Sort by the starting coordinate of each segment
Set shouldBeCovered = 0,
while(shouldBeCovered < M)  
    get the max covering length (segment.end - shouldBeCovered + 1) segment that segment.start <= shouldBeCovered
    If segment found
        add to the segments that are in the solution
        update shouldBeCovered = segment.end
    else
        No solution can be found

got AC. The main thing about the problem is that you should output the answer as you have chosen , not at the order as they are in the input. If brianfry's input makes the correct output the code will produce an accepted result

Happy Coding

OJ Board

10020 - Minimal coverage

Re: 10020 - Minimal Coverage

Re: 10020 - Minimal Coverage

Re: 10020 - Minimal Coverage

Re: 10020 - Minimal Coverage

Re: 10020 - Minimal Coverage

Re: 10020 - Minimal Coverage

Re: 10020 - Minimal Coverage

Re: 10020 - Minimal Coverage.I got TLe with DP Dynamic progr

Re: 10020 - Minimal Coverage

Re: 10020 - Minimal Coverage

Re: 10020 - Minimal Coverage

Re: 10020 - Minimal Coverage

Re: 10020 - Minimal Coverage