» »

Naloga iz Putka - UPM

Naloga iz Putka - UPM

NejcSSD ::

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

Mavrik ::

Že v štartu imaš malo narobe zastavljeno - to je takšen zelo tipičen primer, ki se reši z grafi in z enim preprostim požrešnim algoritmom.

Torej - zgradiš disjunktni graf vseh odnosov (O(n)), potem pa samo "označiš" vse žrtve in njihove družine (O(n) ker ni ciklov), zatem pa izpišeš vse ki niso označeni (O(n)).

Verjetno se še da kaj hitreje rešiti, samo ti maš predvsem problem da v tvoji kodi zgeneriraš daleč preveč nekih seznamov :)
The truth is rarely pure and never simple.

jernejl ::

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

ragezor ::

btw mislim, da pri tej nalogi ne dela popravljalni sistem ali pa sem jaz kaj zajebal?

Tvoj izhod:
0
106 
... tle je se pol miljon cifer ...
Pravilen izhod:
<<<EOF>>>


drugace pa ja naredi si graf, po moznosti iz slovarjev (jaz sem si naredil dva, da sem potem enega pregledoval v eni smeri (potomce) in drugega v drugi smeri (predniki)) in potem pri zrtvah zacnes iskati v grafu in vse "node", do katerih lahko prides (jih obisces) si zapomnis in potem primerjas z vsemi ljudmi v vasi.

poguglaj depth first search in si ga implementiraj. to je like 5 vrstic kode.

aja mocno ti priporocam da vzames podatke iz enega primera, poracunas in izpises resitev in potem vzames podatke od drugega primera. bodo te pocakali. tako si prihranis zongliranje s seznami podatkov.

Zgodovina sprememb…

  • spremenil: ragezor ()

NejcSSD ::

To je datoteka in preverjanje dela (6s :( )
https://www.dropbox.com/s/o1sj59cpfhy7q...
Hvala za nasvete, bom poskusil jutri
PC : MAG B550 Tomahawk, Ryzen 5600X, 32Gb 3200Mhz CL16, 2x 1TB NVME, MSI 1070Ti

ragezor ::

ojoj, komaj po koncnici datoteke na dropboxu sem videl, da gre za python. prej sme mislil, da delas v javi :D

namesto seznamov uporabljaj set() kjer se da. bo hitreje.

Spura ::

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;
		}
	}

ragezor ::

mnja, ti mas seznam Personov, kateri drzijo seznam svojih parentov in childrenov.

isto je ko mas slovar kjer je key oseba, value je pa seznam childrenov (oziroma parentov)

in enkrat ko mas slovar je tudi bolj "naravno" implementirati depth first search

def search(graph, start):
    visited = set()
    visited.add(start)
    frontier = [start]
    while frontier:
        node = frontier.pop()
        visited.add(node)
        # razsirimo seznam ljudi, ki jih je treba preiskati s seznamom, ki ga dobimo iz grafa
        frontier.extend(graph[node])
    return visited


princip je pa isti kot v tvoji resitvi tako da ni glih kompliciranje (mogoce je delo s slovarji bolj nerodno v javi in se jih zato izogibate?)

Zgodovina sprememb…

  • spremenil: ragezor ()

ragezor ::

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

bajsibajsi ::

So vidni ja, hvala. To ST serje.

NejcSSD ::

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 :(
PC : MAG B550 Tomahawk, Ryzen 5600X, 32Gb 3200Mhz CL16, 2x 1TB NVME, MSI 1070Ti

Zgodovina sprememb…

  • spremenil: NejcSSD ()

Spura ::

Slovarji so pocasni in tvoj algoritem jih blazno uporablja.

Spura ::

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();
		}
	}

}

ragezor ::

problem imas v tej for zanki najverjetneje:

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


uporabljaj set()-e ze od vsega zacetka in ne liste in uporabljaj set operacije namesto tele for zanke.

also Spura tvoja koda se mi noce kompajlat na testerju. pa nobenega pametnega errorja ne vrze, da bi popravil.
daj pozeni tvojo kodo na putkinem testerju in prilepi rezultate prosim.

ragezor ::

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

Spura ::

 &gt; implying this shit works

&gt; implying this shit works

NejcSSD ::

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
:D
PC : MAG B550 Tomahawk, Ryzen 5600X, 32Gb 3200Mhz CL16, 2x 1TB NVME, MSI 1070Ti

ragezor ::

zelo verjetno je, da ocenjevalni program ne deluje na putki.

tudi meni vrze ven WA (wrong answer)

NejcSSD ::

Če komu rata kljukica naj sporoči ;)
PC : MAG B550 Tomahawk, Ryzen 5600X, 32Gb 3200Mhz CL16, 2x 1TB NVME, MSI 1070Ti

Randomness ::

Moja rešitev v C-ju si je uspela "prislužiti" kljukico.
Porabljen spomin: 1,512 MiB
Porabljen čas : 0,077 s

Aja, pa pri meni piše, da je čas omejen na 1 sekundo.

Zgodovina sprememb…

NejcSSD ::

Sedaj so spremenili vidim ja. prej je bilo 5 sekund.
Moja ostaja na 1,4sekund, bolje ne znam.
http://pastebin.com/LTAeTYQ6
PC : MAG B550 Tomahawk, Ryzen 5600X, 32Gb 3200Mhz CL16, 2x 1TB NVME, MSI 1070Ti

NejcSSD ::

Evo vse input() sm zamenjal z (najprej import sys) sys.stdin.readline()
in je 0,4sekunde
PC : MAG B550 Tomahawk, Ryzen 5600X, 32Gb 3200Mhz CL16, 2x 1TB NVME, MSI 1070Ti

NejcSSD ::

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.
PC : MAG B550 Tomahawk, Ryzen 5600X, 32Gb 3200Mhz CL16, 2x 1TB NVME, MSI 1070Ti

Zgodovina sprememb…

  • spremenil: NejcSSD ()

Randomness ::

Nisem pogledal tvoje kode, vendar kar mi ob pogledu na nalogo pade na pamet, je to, da bi lahko bil problem v prekoračitvi obsega celih števil (int). Mogoče bi bilo potrebno uporabiti aritmetiko z večjo (poljubno) natančnostjo. Glej Pythonova modula decimal in fractions.

Zgodovina sprememb…

NejcSSD ::

Sem že rešil, narobe sem zastavil nekje vmes. Bi izbrisal post, pa ne gre.
Hvala.
PC : MAG B550 Tomahawk, Ryzen 5600X, 32Gb 3200Mhz CL16, 2x 1TB NVME, MSI 1070Ti


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

python-rabim pomoč

Oddelek: Programiranje
162701 (931) rnla1973
»

Predstavitev dvojiškega drevesa z seznamom

Oddelek: Programiranje
141834 (1434) ktka
»

urejanje - python

Oddelek: Programiranje
51304 (1081) ktka
»

[C] kazalčni seznam

Oddelek: Programiranje
122943 (2757) MrBrdo
»

[java] funkcija ekvivalentna print_r v PHP

Oddelek: Programiranje
161621 (1384) sverde21

Več podobnih tem