Naloga iz Putka - UPM

Pozdravljeni, imam težave pri naslednji nalogi:
http://putka.upm.si/tasks/2008/2008_2ko...
Krvno maščevanje.

Da na kratko razložim shemo vhodnih podatkov.
8 število vaščanov
1 3 1ka je otrok, 3ka njegov starš
3 6 3ka otrok, 6ka njegov starš
4 5
6 2
4 6
8 1
0 0 zaključek naštevanja vezi
3 žrtev
8 žrtev
KRI če bo še en primer oz. VODA če je primer zadnji.

TAKOLE BI IZGLEDALA SHEMA
http://shrani.najdi.si/?f/6l/1vYcHTHd/s...

Ker sta žrtvi 3 in 8, mora program vrniti osumljence 4,5 in 7. (niso direktno potomci/predniki)

Vse lepo in prav, dela mi na teh vhodnih podatkih, vendar sem več kot očitno vse skupaj zakompliciral,
ker mi v preverjanju porabi okoli 6sekund, dovoljeno pa je 5 sekund.

MOJA IDEJA je bila naslednja:
Najprej seveda ustrezno preberem vhodne podatke
Otrok-starš bi dal v seznam [otrok, starš]
Število vaščanov bi šlo v seznam vaščanov, če je več primerov(ki se ne povezujejo) je ta seznam ustrezno daljši

1. del KODA PREBERI VNOS

 

# PUTKA
# Krvno maščevanje

def krvnoMascevanje():
    steviloVascanov = []
    seznamPrimerov = []
    seznamUbitih = []
    while True:
        vascanov = int(input())
        primer = []
        ubitih = []
        while True:
            vnos = input()
            if vnos =="VODA" or vnos == "KRI":
                break
            elif vnos =="0 0":
                pass
            else:
                try:
                    ubitih += [int(vnos)]
                except:
                    vascan1,vascan2 = vnos.split()
                    primer += [[int(vascan1),int(vascan2)]]
        seznamPrimerov.append(primer)
        seznamUbitih.append(ubitih)
        steviloVascanov.append(vascanov)
        if vnos =="VODA":
                break

# SEZNAM prvi in drugi primer [[1, 3], [3, 6], [4, 5], [6, 2], [4, 6], [8, 1]]  in
# [[1, 2], [3, 2], [1, 4], [3, 4], [2, 6], [5, 2],[5, 4]]
# UBITI [[3, 8], [2, 5]]  # 3,8 v prvem   in 2,5 žrtvi v drugem primeru
# VAŠĆANI [8, 6]   8 za prvi in 6 za drugi primer

Potem pa sem definiral funkcije, ki bi za določeno žrtev poiskale vse potomce in prednike.
Za vsako žrtev bi potem našla še osubmljence in jih primerjala z osumljenci druge žrtve oz. več žrtev
Potem pa samo še presek teh osumljencev da končno rešitev.

 

def potomciUbitega(oseba,seznam):
    """Potomci, to bodo prvi v paru"""
    sezPotomcev = []
    for par in seznam:
        if par[1] == oseba:
            sezPotomcev.append(par[0])
            potomci = potomciUbitega(par[0],seznam)
            # to je seznam
            for clan in potomci:
                sezPotomcev.append(clan)
    return sezPotomcev

def prednikiUbitega(oseba,seznam):
    sezPrednikov = []
    for par in seznam:
        if par[0] == oseba:
            sezPrednikov.append(par[1])
            predniki = prednikiUbitega(par[1],seznam)
            # to je seznam
            for clan in predniki:
                sezPrednikov.append(clan)
    return sezPrednikov

def prednikiInPotomci(oseba,seznam):
    sez = [oseba]
    sez.extend(potomciUbitega(oseba,seznam))
    sez.extend(prednikiUbitega(oseba,seznam))
    return sorted(sez)

def osumljenci(oseba,seznam,vascanov):
    """Izpiše seznam osumljenih"""
    sezOsumljenih = []
    sezVezi = prednikiInPotomci(oseba,seznam)
    for clovek in range(1,vascanov+1):
        if clovek not in sezVezi:
            sezOsumljenih.append(clovek)
    return sezOsumljenih

def presekSeznamov(seznamSeznamov):
    """Naredi presek"""
    presek = set.intersection(*map(set,seznamSeznamov))
    if len(presek) == 0:
        print(0)
    else:
        niz = ""
        for element in presek:
            niz+= str(element)+" "
        print(niz[:-1])

krvnoMascevanje()

Program, ki vse skupaj poveže in je del prvega dela (KrvnoMascevanje())
pa je tole:

            
    i = 0 #indeks za žrtve in vaščane
    for primer in seznamPrimerov:
        # vsak primer obdela posebej
        zrtve = seznamUbitih[i]
        osumljeni = []
        for zrtev in zrtve:
            osumljeni.append(osumljenci(zrtev,primer,steviloVascanov[i]))
        presekSeznamov(osumljeni)
        i+=1 

UPAM DA SE NAJDE KDO, ki bi pomagal tole z optimizirati.
Verjetno je že v štartu kaj narobe zastavljeno, pa bi bilo bolj pametno s slovarji??
Samo nimam ideje več.

Zagotovo bi bilo dobro uporabiti asociativna polja (v pythonu dictionary).

To je datoteka in preverjanje dela (6s :( )
https://www.dropbox.com/s/o1sj59cpfhy7q...
Hvala za nasvete, bom poskusil jutri

Tko kot je Mavrik reku, kako kompliciranje s slovarji.

	public static void main(final String[] args) {
		uglySolution(8, new int[] { 1, 3, 3, 6, 4, 5, 6, 2, 4, 6, 8, 1 }, new int[] { 3, 8 });
	}

	public static void uglySolution(final int num, final int[] connections, final int[] murdered) {
		final Person[] graph = new Person[num];
		for (int i = 0; i < graph.length; i++) {
			graph[i] = new Person();
		}
		for (int i = 0; i < connections.length; i += 2) {
			graph[connections[i] - 1].parents.add(graph[connections[i + 1] - 1]);
			graph[connections[i + 1] - 1].children.add(graph[connections[i] - 1]);
		}
		for (final int murder : murdered) {
			graph[murder - 1].markParents().markChildren();
		}
		boolean noSuspects = true;
		for (int i = 0; i < graph.length; i++) {
			if (graph[i].suspect) {
				System.out.print(" " + (i + 1));
				noSuspects = false;
			}
		}
		if (noSuspects) {
			System.out.println("0");
		}
	}

	public static class Person {
		List<Person> children = new ArrayList<LOL.Person>();
		List<Person> parents = new ArrayList<LOL.Person>();
		boolean suspect = true;

		Person markChildren() {
			this.suspect = false;
			for (final Person child : children) {
				child.markChildren();
			}
			return this;
		}

		Person markParents() {
			this.suspect = false;
			for (final Person parent : parents) {
				parent.markParents();
			}
			return this;
		}
	}

am a so moji popravki vidni ali ne? ko dam popravi imam popravljen tekst v editorju in ko kliknem shrani mi pokaze popravljen tekst v postu. ko pa refresham page pa izginejo popravki.

weird

Zdaj sem nekoliko upošteval nasvete, ampak še vedno je 6 sekund?

ZDAJ:
- vsak primer obdeluje zase, samo na koncu počaka na izpis
- ko prebira podatke naredi obenem slovar kjer je ključ otrok, vrednosti pa starši
- in slovar kjer je ključ starš, vrednost pa otroci

TAKOLE IZGLEDAJO SLOVARJI ZA PRVI PRIMER:
http://shrani.najdi.si/?22/hA/2mgkjP3r/...



A je rekurzija potomci/predniki počasna al kaj?
Kaj več kot slovarji in vse nazaj in nismo jemali.

def krvnoMascevanje():

    izpis = []
    
    while True:
        vascanov = int(input())
        potomci = {}
        predniki = {}
        ubitih = []
        for x in range(1,vascanov+1):
            potomci[x] = []
            predniki[x] = []
        while True:
            vnos = input()
            if vnos =="VODA" or vnos == "KRI":
                break
            elif vnos =="0 0":
                pass
            else:
                try:
                    # gre za mrtvece
                    ubitih += [int(vnos)]
                except: # gre za par otrok - stars "x y"
                    otrok = int(vnos.split()[0])
                    stars = int(vnos.split()[1])

                    predniki[otrok].append(stars)
                    potomci[stars].append(otrok)

        osumljeni = []
        for zrtev in ubitih:
            # za vsako žrtev poiščemo osumljence
            osumljeni.append(osumljenci(zrtev,potomci,predniki,vascanov))
        # potem pa naredimo presek seznama osumljeni
        izpis.append(presekSeznamov(osumljeni))
        if vnos =="VODA":
                break

    # za konec izpišemo
    for niz in izpis:
        print(niz)
        
def potomciUbitega(oseba,slovar):
    sezPotomcev = []
    potomciOsebe = slovar[oseba]
    if len(potomciOsebe) == 0:
        return sezPotomcev
    sezPotomcev.extend(potomciOsebe)
    for clan in potomciOsebe:
        sezPotomcev.extend(potomciUbitega(clan,slovar))
    return sezPotomcev

def prednikiUbitega(oseba,slovar):
    sezPrednikov = []
    prednikiOsebe = slovar[oseba]
    if len(prednikiOsebe) == 0:
        return sezPrednikov
    sezPrednikov.extend(prednikiOsebe)
    for clan in prednikiOsebe:
        sezPrednikov.extend(prednikiUbitega(clan,slovar))
    return sezPrednikov

def osumljenci(oseba,potomci,predniki,vascanov):
    """Izpiše seznam osumljenih"""
    sezOsumljenih = []
    # Vezi predstavljajo potomci in njihovi potomci ter starši, stari starši, itd... 
    sezVezi = potomciUbitega(oseba,potomci) + prednikiUbitega(oseba,predniki) + [oseba]
    for clovek in range(1,vascanov+1):
        if clovek not in sezVezi:
            # potem je kandidat za osumljenca
            sezOsumljenih.append(clovek)
    return sezOsumljenih

def presekSeznamov(seznamSeznamov):
    """Naredi presek med n seznami, ki so v seznamu"""
    presek = set.intersection(*map(set,seznamSeznamov))
    if len(presek) == 0:
        return 0
    else:
        niz = ""
        for element in presek:
            niz+= str(element)+" "
        return niz[:-1] #brez presleka na koncu
        
krvnoMascevanje()

Upam da se vidijo popravki :(

Evo komplet verzija z eno optimizacijo.

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class LOL {

	public static void main(final String[] args) throws NumberFormatException, IOException {
		final Scanner sc = new Scanner(System.in);
		while (solveNextCase(sc)) {
			System.out.println();
		}
	}

	public static boolean solveNextCase(final Scanner sc) throws NumberFormatException, IOException {
		final int num = sc.nextInt();
		final Person[] graph = new Person[num];
		for (int i = 0; i < graph.length; i++) {
			graph[i] = new Person();
		}
		{
			int child = 0;
			while ((child = sc.nextInt()) != 0) {
				final int parent = sc.nextInt();
				graph[child - 1].parents.add(graph[parent - 1]);
				graph[parent - 1].children.add(graph[child - 1]);
			}
			sc.nextInt();
		}

		while (sc.hasNextInt()) {
			graph[sc.nextInt() - 1].murder();
		}

		boolean noSuspects = true;
		for (int i = 0; i < graph.length; i++) {
			if (!graph[i].grievingChild && !graph[i].grievingParent) {
				System.out.print((noSuspects ? "" : " ") + (i + 1));
				noSuspects = false;
			}
		}
		if (noSuspects) {
			System.out.println("0");
		}
		sc.nextLine();
		return "KRI".equals(sc.nextLine());
	}

	private static class Person {
		List<Person> children = new ArrayList<LOL.Person>();
		boolean grievingChild = false;
		boolean grievingParent = false;
		List<Person> parents = new ArrayList<LOL.Person>();

		void markChildren() {
			if (grievingChild) {
				return;
			}
			grievingChild = true;
			for (final Person child : children) {
				child.markChildren();
			}
		}

		void markParents() {
			if (grievingParent) {
				return;
			}
			grievingParent = true;
			for (final Person parent : parents) {
				parent.markParents();
			}
		}

		void murder() {
			markParents();
			markChildren();
		}
	}

}

tukaj je zelo pomembno, da uporabis set(), ker "in" poizvedba na setu je O(1) na listu pa O(n)
preprosto prevec razlicnih listov imas in podvajas si delo. vsak append stane, vsak range() stane. vsaka pretvorba list -> set stane. tam pri iskanju intersekcij imas tudi ogromno overheada.

razmisljaj v tej smeri: najdi vse "vezi" kot ti temu pravis ampak naj bo set in ne seznam, plus tega zdruzi za vse zrtve vezi v en set. ko imas to pa imas set vseh vascanov, kateremu odstejes set vezi. ne rabis nobenih intersekcij. ce jaz to naredim tvojemu programu da preprosto nadomestim liste s seti in odstranim for zanko in intersekcije pride tvoj program na 1.3 sekunde.

moj program pa racuna 0.3 sekunde

Ne morem verjet kakšna razlika samo pretvorba iz lista v set na parih mestih.
Hvala vsem...
Sedaj me samo še pravilen izhod zajebava na putki (sem znotraj časovno in spominsko)
Lists : 6s
Sets : 1,4s

Če komu rata kljukica naj sporoči ;)

Sedaj so spremenili vidim ja. prej je bilo 5 sekund.
Moja ostaja na 1,4sekund, bolje ne znam.
http://pastebin.com/LTAeTYQ6

Da ne odpiram nove teme, bom vprašanje zastavil kar tukaj.
Sedaj imam težave na preverjanju programa prek Kattisa.
Gre za nalogo: https://kth.kattis.com/problems/rationa...
Navodilo bolj razumno:
http://shrani.najdi.si/?T/bd/ap7dIha/na...

V prvi vrstici vnesemo koliko imamo računov
Potem pa v vsaki ločimo števec in imenovalec ulomka s presledkom, med oba ulomka
pa vrinemo operacijo. In vrniti moramo okrajšan poračunan ulomek.

Najprej sem poskušal nekaj z Eval vendar vrne numerično.

Potem pa sem spisal malo daljšo kodo, načeloma se mi zdi, da bi moralo vse delati,
vendar ne vem kaj hoče testni program od mene, da javi napačen odgovor.
slika:
http://shrani.najdi.si/?5/T6/2psf8RgM/n...

def poračunaj():
    """Funkcija v prvem delu ustrezno prebere podatke,
    v drugem delu pa glede na operacijo pokliče pomožno funkcijo."""
    
    izpis = []
    
    stOperacij = int(input())
    while stOperacij > 0:
        
        vrstica = input().split()
        
        prva = int(vrstica[0])
        druga = int(vrstica[1])
        operacija = vrstica[2]
        tretja = int(vrstica[3])
        četrta = int(vrstica[4])

        if operacija =="+" or operacija =="-":
            izpis.append(plusMinus(prva,druga,operacija,tretja,četrta))
            
        elif operacija =="*":
            izpis.append(kratDeljeno(prva,druga,tretja,četrta))
        else:
            #gre za deljenje
            #menjava tretje in četrte
            izpis.append(kratDeljeno(prva,druga,četrta,tretja))
            
        stOperacij -= 1
        
    # za konec izpišemo    
    for rezultat in izpis:
        print(rezultat)

def plusMinus(prva,druga,operacija,tretja,četrta):
    """Funkcija glede na operacijo +/- izračuna in vrne
    okrajšan rezultat v obliki predpisanega niza"""
    # najmanjši skupni večkratnik =
    # a*b / gcd(a,b)
    imenovalec = druga*četrta / evklidovAlgoritem(druga,četrta)
    # popravimo še števce
    prva*= imenovalec/druga
    tretja*= imenovalec/četrta
    
    if operacija == "+":
        števec = int(prva + tretja)
    else:
        števec = int(prva - tretja)
    if števec ==0:
        imenovalec = 1
    return str(števec)+" / "+str(int(imenovalec))

def kratDeljeno(prva,druga,tretja,četrta):
    """Funkcija izračuna produkt med ulomkoma prva/druga
    in tretja/četrta in ga ustrezno pokrajša, če je možno."""
    števec = prva*tretja
    imenovalec = druga*četrta
    # pogledamo če se števec in imenovalec lahko še krajšata
    skupniDelitelj = evklidovAlgoritem(števec,imenovalec)
    
    števec = števec/skupniDelitelj
    imenovalec = imenovalec/skupniDelitelj
    return str(int(števec))+" / "+str(int(imenovalec))

def evklidovAlgoritem(a,b):
    """Evklidov algoritem,
    vrne največji skupni delitelj števil a in b."""
    while b != 0:
        a, b = b, a % b
    return a
    
poračunaj()

Še koda na pastebinu, če je bolj pregledna tam:
http://pastebin.com/DdeNR3XE

Že vidim kje je problem, prosim za izbris.

Sem že rešil, narobe sem zastavil nekje vmes. Bi izbrisal post, pa ne gre.
Hvala.