Osaisiko joku auttaa putkapostissa

Anonyymi

Osaisiko joku antaa vinkkiä, miten tehtävä sivulta https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=srl ratkeaa. Yritin kokeilla brute forcella, mutta jo kolmas tapaus meni pieleen. Tein Pythonilla ohjelman, joka katsoo ruutu kerrallaan, kummalle pala kuuluu. Koodi on osoitteessa https://pastebin.com/S3EcF1W5

8

<50

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Tarvitsee laskea vain toisen saama osa (vai saako vai laittaako ne niitä palikoita ihan sama).

      Aloituspisteitä yhdistävän janan keskinormaali tai mahdollisesti kaksi sellaista jakaa lipun haluttuihin osiin. Käy se suora läpi palikka kerrallaan. Laske siinä mennessä alapuolelle jäävien palikoiden lukumäärät (sin valk) (sehän saadaan: jos ollaan ristin keskikohdalla, niin kokonaan sinistä, muuten jos ollaan ristin alapuolella, niin pelkkää valkoista, jos taas ylä, niin koko leveydeltä ja jos sinisellä, niin korkeus- mistä risti pystysuunnassa alkaa tulee valkoisia ja sinisiä sitten loput sen sarakkeen osalta).

      Se lisäsääntöhän siinä vähän sekoittaa, että jos molempien pitää laittaa, niin toinen voittaa sinisellä ja toinen valkealla, mutta sellaista ei tapahdu kuin yhden keskinormaalin tapauksessa eli jos manhattanin metriikassa nämä kaksi alkuräjähdystä ovat parittoman päässä toisistaan. Jos taas parillisen, niin silloin riittää käydä alempi läpi ilman mitään erikoissääntöjä sillä vain toisen pelaajan lukumääräthän riittää laskea sillä toisen saadaan koko lipun palikoista jotka taas on helppo laskea.

    • Entäpä yleistys useammalle pelaajalle?!? Olisko Voronoi-tessalaatio mitä?

    • Ei se noin menekään kuin sanoin! Ne on pysty-, vaaka- ja diagonaalisuorien yhdistelmiä, ne erottavat käyrät. Eivätkä nekään koko totuutta kerro, vaan se erikoisehto kumpi voittaa sinisellä/valkoisella tekee siitä vähän sellaisen että kumpi lähtee missäkin alueessa liidaamaan, niinkuin jänis voittaa maalla mutta krototiili vedessä jne, jne...

      • Anonyymi

        Niin. Mietin aluksi brute forcea, mutta kun koetin, niin palvelin hyväksynyt ratkaisuani kaikkiin tapauksiin. Mietin myös, että voiko tuollaisia erottavien käyrien rajaaminen alueiden ruutujen määrää laskea Pickin kaavalla.


      • Anonyymi kirjoitti:

        Niin. Mietin aluksi brute forcea, mutta kun koetin, niin palvelin hyväksynyt ratkaisuani kaikkiin tapauksiin. Mietin myös, että voiko tuollaisia erottavien käyrien rajaaminen alueiden ruutujen määrää laskea Pickin kaavalla.

        Jos sen erottavan käyrän saa selville, niin eikös se sitten ole helppo laskea kuinka paljon jää sen alapuolelle kummankin laisia (vai ajattelenko taas liian hätiköidysti?)?

        Olisiko tästä apua säännönmukaisuuksien huomaamisessa: https://repl.it/@minkkilaukku2/Alligaattori-ja-Bambi

        Käyttöohje: valitse aloituspaikka A tai B hiirellä ja klikkaa sen jälkeen uutta paikkaa. Niitä voi myöskin raahata. Raahatessa ratkaisu lasketaan sitä mukaa kun aloituspaikan sijainti muuttuu, muussa tapauksessa klikkaa solve-nappia. Siinä voi myös valita näytetäänkö pienet numerot, jotka kertovat millä kierroksella kukin palikka on laitettu (sehän on Manhattan-etäisyys alkupisteestä eli toiselta nimeltään taksimiehen metriikka).

        Tein myös tällaisen Python-version: https://repl.it/@minkkilaukku2/Antilooppi-ja-Boa
        Ja brute-force on siis tämäkin. Esimerkki ainakin menisi oikein ja ekoille saan tällaisia:
        [36, 270, 268, 42, 212]
        [342, 8094, 21182, 20064, 22138]
        [648, 17838, 40032, 83250, 115488]
        ...
        Saatko samat?

        Jotenkin se "erottava käyrä" tulee siitä että ollaan Manhattin-etäisyydessä yhtä kaukana kummastakin pisteestä ja jos siinä rajalla ollaan sinisellä, niin sitten se kuuluu kummalle nyt kuulukaan siinä tapauksessa ja muuten toiselle. Tästä saisi lineearisessa ajassa toimivan ratkaisun, jos sen onnistuisi jotenkin parametrisoimaan tuon käyrän.

        Sellainen vaikuttaisi ainakin selvälle, että pisteen "taakse jäävä" suorakulmio kuuluu kokonaan sille itselleen, kun eihän toinen sinne voi mitenkään päästä sotkemaan. Mutta tämäkään ei kyllä auta hirveästi, jos pisteet eivät ole lähekkäin. Ja jos ne nyt ei ihan nurkassa ole, niin O(n^2):nahan se säilyy joka tapauksessa.


      • minkkilaukku kirjoitti:

        Jos sen erottavan käyrän saa selville, niin eikös se sitten ole helppo laskea kuinka paljon jää sen alapuolelle kummankin laisia (vai ajattelenko taas liian hätiköidysti?)?

        Olisiko tästä apua säännönmukaisuuksien huomaamisessa: https://repl.it/@minkkilaukku2/Alligaattori-ja-Bambi

        Käyttöohje: valitse aloituspaikka A tai B hiirellä ja klikkaa sen jälkeen uutta paikkaa. Niitä voi myöskin raahata. Raahatessa ratkaisu lasketaan sitä mukaa kun aloituspaikan sijainti muuttuu, muussa tapauksessa klikkaa solve-nappia. Siinä voi myös valita näytetäänkö pienet numerot, jotka kertovat millä kierroksella kukin palikka on laitettu (sehän on Manhattan-etäisyys alkupisteestä eli toiselta nimeltään taksimiehen metriikka).

        Tein myös tällaisen Python-version: https://repl.it/@minkkilaukku2/Antilooppi-ja-Boa
        Ja brute-force on siis tämäkin. Esimerkki ainakin menisi oikein ja ekoille saan tällaisia:
        [36, 270, 268, 42, 212]
        [342, 8094, 21182, 20064, 22138]
        [648, 17838, 40032, 83250, 115488]
        ...
        Saatko samat?

        Jotenkin se "erottava käyrä" tulee siitä että ollaan Manhattin-etäisyydessä yhtä kaukana kummastakin pisteestä ja jos siinä rajalla ollaan sinisellä, niin sitten se kuuluu kummalle nyt kuulukaan siinä tapauksessa ja muuten toiselle. Tästä saisi lineearisessa ajassa toimivan ratkaisun, jos sen onnistuisi jotenkin parametrisoimaan tuon käyrän.

        Sellainen vaikuttaisi ainakin selvälle, että pisteen "taakse jäävä" suorakulmio kuuluu kokonaan sille itselleen, kun eihän toinen sinne voi mitenkään päästä sotkemaan. Mutta tämäkään ei kyllä auta hirveästi, jos pisteet eivät ole lähekkäin. Ja jos ne nyt ei ihan nurkassa ole, niin O(n^2):nahan se säilyy joka tapauksessa.

        Ai niin joo, sullahan oli tuo koodi tuossa viestissä. Vähän eri tulos näyttäs tulevan sinisten kohdalla:

        (342, 7996, 21182, 20162, 22138)
        vs.
        [342, 8094, 21182, 20064, 22138]

        Hmmmm.. näyttääkös se ohjelmointiputka mitkä on oikein?


    • Sun koodissa jos muuttaa sen etäisyystestin hyväksymään myös yhtäsuuruuden, siinä tapauksessa että pala on sininen, niin sitten se antaa samoja tuloksia. Ja se on myös nopeampi kuin minun koodi, joka taitaa olla O(n^3) jopa :D!

      Refaktoroin myös vähän sitä tämmöiseksi: https://repl.it/@minkkilaukku2/Siniristilippu2

      Se laskee kaikki muutamassa minuutissa ainakin omalla koneellani meni. Mitenköhän nopea olisi PyPy ja tehokkaampi kone? Nopeampia ratkaisuja vois vielä miettiä. Eikös se pitäs periaatteessa olla vaan joku ihan kaava millä sen voi laskea...

      • Tähän "jos etäisyys pienempi, tai jos yhtä suuri ja sinisellä" -algoritmiin taitaa olla yksi erikoistapaus, jossa se ei toimi, nimittäin jos aloituspisteet ovat samalla diagonaalilla, tässä esimerkkikuva:

        https://aijaa.com/yv9779

        Sellaisia tapauksia ei tainnut noissa testeissä olla sillä läpi ne menee putkassa, testasin :D


    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Mielessäni vieläkin T

      Harmi että siinä kävi niinkuin kävi, rakastin sinua. Toivotan sulle kaikkea hyvää. Toivottavasti löydät sopivan ja hyvän
      Ikävä
      40
      1992
    2. Pupuhuhdasta löytyi lähes sadan kilon miljoonalasti huumeita

      Pupuhuhdasta löytyi lähes sadan kilon miljoonalasti huumeita – neljä Jyväskylän Outlaws MC:n jäsentä vangittu: "Määrät p
      Jyväskylä
      43
      1526
    3. Persut petti kannattajansa, totaalisesti !

      Peraujen fundamentalisteille, vaihtkaa saittia. Muille, näin sen näimme. On helppo luvata kehareille, eikä ne ymmärrä,
      Maailman menoa
      28
      1438
    4. Nellietä Emmaa ja Amandaa stressaa

      Ukkii minnuu Emmaa ja Amandaa stressaa ihan sikana joten voidaanko me koko kolmikko hypätä ukin kainaloon ja syleilyyn k
      Isovanhempien jutut
      6
      1431
    5. Ei luottoa lakko maahan

      Patria menetti sovitun ksupan.
      Suomen Keskusta
      19
      1427
    6. Nähtäiskö ylihuomenna taas siellä missä viimeksikin?

      Otetaan ruokaöljyä, banaaneita ja tuorekurkkuja sinne messiin. Tehdään taas sitä meidän salakivaa.
      Ikävä
      1
      1395
    7. Sinäkö se olit...

      Vai olitko? Jostain kumman syystä katse venyi.. Ajelin sitten miten sattuu ja sanoin ääneen siinä se nyt meni😅😅... Lis
      Ikävä
      2
      1367
    8. Housuvaippojen käyttö Suomi vs Ulkomaat

      Suomessa housuvaippoja aletaan käyttämään vauvoilla heti, kun ne alkavat ryömiä. Tuntuu, että ulkomailla housuvaippoihin
      Vaipat
      1
      1300
    9. Hyvää yötä ja kauniita unia!

      Täytyy alkaa taas nukkumaan, että jaksaa taas tämän päivän haasteet. Aikainen tipu madon löytää, vai miten se ärsyttävä
      Tunteet
      2
      1230
    10. Lepakot ja lepakkopönttö

      Ajattelin tehdä lepakkopöntön. Tietääkö joku ovatko lepakot talvella lepakkopöntössä ´vai jossain muualla nukkumassa ta
      5
      1217
    Aihe