Úloha A3

[Xellos]

kto opravuje 3-ku?

[mišof]

(07.02.2012 18:49:26)Xellos.myopenid.com/ Napísal:  kto opravuje 3-ku?

Žaba a Kozza.

[jodik]

Dobrý deň,

práve som si prečítal vzorové riešenie tretieho príkladu (kat. A, keď som videl O(d),hneď v deň riešenia vedel som že to mám dobre a nečítal som ho) a je v skutku nemožné aby som zaň mal iba tri body , ako fakt tam mám úplne to isté(skoro (ako že v popise je to trochu iné), ale princíp úplne rovnaký(pocet, vyskyty[] všetko (inak pomenované) tam mám)) preto by som sa chcel spýtať či nenastala nejaká chyba (písal som to na 2 listy (4 strany), alebo po mne niekto nevedel prečítať, alebo sa niečo nevymenilo), pretože je to fakt nemožné, aby som to mal za tri, iba ak by som tam niečo fakt prehliadol, ale to si nemyslím (mal som tam aj kód)

Za skorú odpoveď ďakujem.[/align]

[jodik]

No a aby som vysvetlil čo som mal iné tak majme príklad:
3 7
1 1 1 2 3 1 1
tak vo vzorovom programe to funguje, tak že nájdete
1 1 1 2 3 a pripočítate d-p +1 čiže 3
potom odstránite jednu jednotku:
1 1 2 3, ale furt je pocet==n čiže zase pripočítate tri a ešte raz odstránite jednotku a zase pripočítate tri, avšak môj program nájde najmenšiu časť to jest 1 2 3 a potom vynásobí zvyšok na (pravej strane + 1(samotné 1 2 3) (to jest dve jednotky a 1 2 3) zvyškom na ľavej +1) čiže kebyže pred tým neboli dve jednotky bolo by to tri takto to je 9 čiže sa to rovná no a potom Váš program odstráni ďalšiu jednotku zistí že pocet != n tak pridá ďalšie číslo zprava a už bude pocet == n , tak pripočíta d-n+1 čiže 2 môj program takisto nájde najmenšiu časť 2 3 1 a vynásobí ľavý zvyšok +1, avšak to nie je úplne odľava ale od začiatku minulého takéhoto najmenšieho úseku +1, čiže v tomto prípade je ľavý zvyšok 0 a teda (0+1)* pravý plus jedna tak to je 1*2 čiže 2 výsledok je tak isto jedenásť, dalo by sa povedať že v praxi by to mohlo byť aj o čosi rýchlejšie keďže nejdem po jednom ale pripočítavam naraz všetko (násobením) a mám to tam O(d) a takisto aj všetky chyby/výnimky pokryté, ak to niekto nepochopil tak sa ospravedlňujem, ale proste je vylúčené aby som mal za vzorové riešenie 3 body!!!

[Koniiiik]

(09.02.2012 12:57:55)jodik.myopenid.com/ Napísal:  No a aby som vysvetlil čo som mal iné tak majme príklad:
3 7
1 1 1 2 3 1 1
tak vo vzorovom programe to funguje, tak že nájdete
1 1 1 2 3 a pripočítate d-p +1 čiže 3
potom odstránite jednu jednotku:
1 1 2 3, ale furt je pocet==n čiže zase pripočítate tri a ešte raz odstránite jednotku a zase pripočítate tri, avšak môj program nájde najmenšiu časť to jest 1 2 3 a potom vynásobí zvyšok na (pravej strane + 1(samotné 1 2 3) (to jest dve jednotky a 1 2 3) zvyškom na ľavej +1) čiže kebyže pred tým neboli dve jednotky bolo by to tri takto to je 9 čiže sa to rovná no a potom Váš program odstráni ďalšiu jednotku zistí že pocet != n tak pridá ďalšie číslo zprava a už bude pocet == n , tak pripočíta d-n+1 čiže 2 môj program takisto nájde najmenšiu časť 2 3 1 a vynásobí ľavý zvyšok +1, avšak to nie je úplne odľava ale od začiatku minulého takéhoto najmenšieho úseku +1, čiže v tomto prípade je ľavý zvyšok 0 a teda 0+1* pravý plus jedna tak to je 1*2 čiže 2 výsledok je tak isto jedenásť, dalo by sa povedať že v praxi by to mohlo byť aj o čosi rýchlejšie keďže nejdem po jednom ale pripočítavam naraz všetko (násobením) a mám to tam O(d) a takisto aj všetky chyby/výnimky pokryté, ak to niekto nepochopil tak sa ospravedlňujem, ale proste je vylúčené aby som mal za vzorové riešenie 3 body!!!

Som OT a k veci priamo neprispievam, ale nemôžem si odpustiť… Wow. A to ja som si myslel, že to občas preháňam s dĺžkou a zložitosťou súvetí. Ale v tejto vete mám ešte aj ja problém sa zorientovať a nejak z nej vydolovať, čo sa snaží povedať.

[jodik]

(09.02.2012 14:27:30)Koniiiik Napísal:  

(09.02.2012 12:57:55)jodik.myopenid.com/ Napísal:  No a aby som vysvetlil čo som mal iné tak majme príklad:
3 7
1 1 1 2 3 1 1
tak vo vzorovom programe to funguje, tak že nájdete
1 1 1 2 3 a pripočítate d-p +1 čiže 3
potom odstránite jednu jednotku:
1 1 2 3, ale furt je pocet==n čiže zase pripočítate tri a ešte raz odstránite jednotku a zase pripočítate tri, avšak môj program nájde najmenšiu časť to jest 1 2 3 a potom vynásobí zvyšok na (pravej strane + 1(samotné 1 2 3) (to jest dve jednotky a 1 2 3) zvyškom na ľavej +1) čiže kebyže pred tým neboli dve jednotky bolo by to tri takto to je 9 čiže sa to rovná no a potom Váš program odstráni ďalšiu jednotku zistí že pocet != n tak pridá ďalšie číslo zprava a už bude pocet == n , tak pripočíta d-n+1 čiže 2 môj program takisto nájde najmenšiu časť 2 3 1 a vynásobí ľavý zvyšok +1, avšak to nie je úplne odľava ale od začiatku minulého takéhoto najmenšieho úseku +1, čiže v tomto prípade je ľavý zvyšok 0 a teda 0+1* pravý plus jedna tak to je 1*2 čiže 2 výsledok je tak isto jedenásť, dalo by sa povedať že v praxi by to mohlo byť aj o čosi rýchlejšie keďže nejdem po jednom ale pripočítavam naraz všetko (násobením) a mám to tam O(d) a takisto aj všetky chyby/výnimky pokryté, ak to niekto nepochopil tak sa ospravedlňujem, ale proste je vylúčené aby som mal za vzorové riešenie 3 body!!!

Som OT a k veci priamo neprispievam, ale nemôžem si odpustiť… Wow. A to ja som si myslel, že to občas preháňam s dĺžkou a zložitosťou súvetí. Ale v tejto vete mám ešte aj ja problém sa zorientovať a nejak z nej vydolovať, čo sa snaží povedať.

To som písal viac menej pre toho kto ma k dispozícií moje riešenie , ak by bol problém rozpíšem to lepšie, ale v princípe je to to isté ako vzorák len je to trochu kratšie lebo to násobím no tjj. , ak si to prećítaš viac krát pochopíš

---

Rozhodol som sa to vysvetliť ešte raz, keďže sa môže zdať že je to úplne iné, keďže je ten príspevok pred tým neprehľadný (píšem popri tomto aj SoČ):

Kód:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, d; cin >> n >> d;
    vector<int> vstup(d);
    for (int i=0; i<d; ++i) { cin >> vstup[i]; --vstup[i]; }
    
    vector<int> vyskyty(n,0)
    int pocet = 0;
    long long vysledok = 0;
    
    for (int zaciatok = 0, p=0; zaciatok<d ; ++zaciatok)
    {
        while (p<d && pocet<n) {
        if (vyskyty[vstup[p]]==0) ++pocet;
        ++vyskyty[vstup[p]];
        ++p;
}
if (pocet==n) vysledok += d-p+1;
--vyskyty[vstup[zaciatok]];
if(vyskyty[vstup[zaciatok]]==0) --pocet;
}
cout << vysledok << endl;
}

To je vzorový program a teraz sa posnažím byť jednoduchý:
Moje riešenie robí v zásade to isté len v tom while ešte testuje, ak je vyskyty[vstup[zaciatok]]>1, tak zaciatok:=zaciatok+1 a vyskyty[zaciatok] sa tiež zmenšia a takto to robím až dokým vyskyty[vstup[zaciatok]]==1 a taktiež zvyšujem nejakú premennú dajme tomu "kolko" a potom v pasáži if (pocet==n) mám vysledok:=vysledok+(kolko+1)*(d-p+1), to je celé akokeby také "zjednodušenie", stále to je O(d) a v princípe je to to isté amám za to 3 body!!!!! to keď som uvidel skoro som spadol zo stoličky, čakal som 10 (a stále čakám)(aspoň okolo 10). jedine v čom môže byť problém, že sa stratil jeden z tých dvoch listov, alebo že tomu niekto nepochopil, keďže som to zozačiatku písal trochu chaoticky, ale inak neviem.
P.S.: Samozrejme si nepamätám ako som pomenoval tie premenné v skutočnosti, ale v princípe to robí toto.

Edit (Koniiiik): Kód patrí do [code] d-:

[Xellos]

upravil som vzorakovy program podla toho co si povedal, tu je (komentar "tu" je pri tom co som pridal podla tvojho popisu): http://ideone.com/vvIH2
oprav ma ak som daco zle pochopil

spustil som ho aj na svojej sade nahodne (seed: systemovy cas) vygenerovanych vstupov, tam je jeden z nich; pracuje to spravne aj dost rychlo, ale ty hovoris ze co by si doplnil ku vzoraku, pricom to co si tam mal napisane mozno bolo mierne ine...

sadu vstupov v najblizsom case tiez dodam (a doplnim, chce to aj velke AJ porovnatelne n a d)

[jodik]

(09.02.2012 15:46:02)Xellos.myopenid.com/ Napísal:  upravil som vzorakovy program podla toho co si povedal, tu je (komentar "tu" je pri tom co som pridal podla tvojho popisu): http://ideone.com/vvIH2
oprav ma ak som daco zle pochopil

spustil som ho aj na svojej sade nahodne (seed: systemovy cas) vygenerovanych vstupov, tam je jeden z nich; pracuje to spravne aj dost rychlo, ale ty hovoris ze co by si doplnil ku vzoraku, pricom to co si tam mal napisane mozno bolo mierne ine...

sadu vstupov v najblizsom case tiez dodam (a doplnim, chce to aj velke AJ porovnatelne n a d)

Ono takto hento som písal len princíp, tam to bolo jednak v pascale a bol to úplne iný program, ale aj toto by malo fungovať aspoň čo na to tak kukám, mohol by si teda niekde dať tie vstupy, pls? Ja som testoval len príklady tie boli dobre, nedáva to logiku malo by to fungovať, bol by som vďačný za tie vstupy

---

(09.02.2012 15:46:02)Xellos.myopenid.com/ Napísal:  upravil som vzorakovy program podla toho co si povedal, tu je (komentar "tu" je pri tom co som pridal podla tvojho popisu): http://ideone.com/vvIH2
oprav ma ak som daco zle pochopil

spustil som ho aj na svojej sade nahodne (seed: systemovy cas) vygenerovanych vstupov, tam je jeden z nich; pracuje to spravne aj dost rychlo, ale ty hovoris ze co by si doplnil ku vzoraku, pricom to co si tam mal napisane mozno bolo mierne ine...

sadu vstupov v najblizsom case tiez dodam (a doplnim, chce to aj velke AJ porovnatelne n a d)

Buď som totálne slepý, alebo ja neviem čo toto bolo, ale ja som videl v tomto tvojom príspevku, že so srdcom mi hovoríš že to na najväčšom vstupe dalo o tri rady zlý výsledok a tak som aj komentoval hento minulé, terza fakt neviem ći mám halucinácie, ale čo sa týka hentoho 100% som to mal tak aj tma ale v pascale iný program ale 100% môžeš si to prečítať

---

Buď som už prepracovaný alebo čo ale toto.....fakt si pamätám celý text a kukám na to akokeby ich niekto vymenil, ale osm rád že si postrehol že to je dobré, dúfam že príde aj opravujúci a prehodnotí svoje rozhodnutie

---

Aby som to upresnil ja som nehovoril čo by som doplnil do vzoráku, ale na akom princípe funguje moje riešenie v pascale na papieroch z KK

[Xellos]

ta chyba bola moja, odflakol som rozsahy premennych

hovoril si co by si doplnil do vzorakoveho programu aby robil v zasade to co tvoj (myslel som ze si domyslis co tym chcem povedat, btw doplnenie = napisem nejake dalsie znaky do suboru)

[jodik]

(09.02.2012 17:04:19)Xellos.myopenid.com/ Napísal:  ta chyba bola moja, odflakol som rozsahy premennych

hovoril si co by si doplnil do vzorakoveho programu aby robil v zasade to co tvoj (myslel som ze si domyslis co tym chcem povedat)

Jo, jo, ale to aj robí (to som si istý(možno nejaká premenná alebo čo sa nevynuluje, ale to proste keď sa kukneš na ten program tak je ti jasné čo to robí + text, to proste nemôžu byť tri body )), ako kukám 2. ku si mal za 10 (klobúk dole), ale toto iba za 4, ti to nejak nevyšlo, či čas?

[Xellos]

po OI (asi 1-2 hodiny po) som si napisal program na kompe podla toho co som si o rieseni na papieri pametal (predtym co som videl vzorak), a teraz ho otestoval tiez na tej sade vstupov... dava spravnu odpoved
pritom si uz ani nepametam co som napisal do riesenia, ale co som si pozeral vzoraky tak som medzi mojimi uvahami a vzorakymi nenasiel odlisnosti

tak tu su vstupy: https://rapidshare.com/files/516620386/vstupy3.rar
a moj program http://ideone.com/IgYS1

[jodik]

(09.02.2012 17:22:45)Xellos.myopenid.com/ Napísal:  po OI (asi 1-2 hodiny po) som si napisal program na kompe podla toho co som si o rieseni na papieri pametal (predtym co som videl vzorak), a teraz ho otestoval tiez na tej sade vstupov... dava spravnu odpoved
pritom si uz ani nepametam co som napisal do riesenia, ale co som si pozeral vzoraky tak som medzi mojimi uvahami a vzorakymi nenasiel odlisnosti

Zvláštne, tak preto si sa pýtal kto opravuje trojku.

[jodik]

(09.02.2012 17:22:45)Xellos.myopenid.com/ Napísal:  po OI (asi 1-2 hodiny po) som si napisal program na kompe podla toho co som si o rieseni na papieri pametal (predtym co som videl vzorak), a teraz ho otestoval tiez na tej sade vstupov... dava spravnu odpoved
pritom si uz ani nepametam co som napisal do riesenia, ale co som si pozeral vzoraky tak som medzi mojimi uvahami a vzorakymi nenasiel odlisnosti

tak tu su vstupy: https://rapidshare.com/files/516620386/vstupy3.rar
a moj program http://ideone.com/IgYS1

Ak to dáva správne výsledky tak nechápem tie 4 body za O(d).

[mišof]

jodik: Mozem zodpovedne prehlasit, ze priciny, pre ktore ma Xellos 4
body a pre ktore mas ty 3 body su uplne nesuvisiace
Vecer by sem mal napisat niektory z opravovatelov 3ky o tom tvojom rieseni.

[jodik]

(09.02.2012 20:29:44)misof.myopenid.com/ Napísal:  jodik: Mozem zodpovedne prehlasit, ze priciny, pre ktore ma Xellos 4
body a pre ktore mas ty 3 body su uplne nesuvisiace
Vecer by sem mal napisat niektory z opravovatelov 3ky o tom tvojom rieseni.

fíha to som zvedavý

[_jano]

Hehe,

sa to celkom rozbehlo na tom fóre..

najskôr vyriešime jednoduchí prípad.. Xellosa
Xellos, máš to samozrejme správne a nemáme voči tvojmu riešeniu žiaden väčšie výhrady.
Ale keďže až do istého dátumu je výsledkovka neoficiálna, prečo tam na náhodné miesta nedopísať náhodné hlúposti.
Pôvodne sme chceli vedieť Sysľove reakcie na zvláštne body, ale tak aby chudák nebol sám, zadávací uškriatok ti dočasne zadal do neoficiálnej výsledkovky 4 body.
pssst, ale neprezraďte to Sysľovi.
Neboj sa, objaví sa tam niekedy aj správne číslo

Čo sa týka Teba Jodik,
dostali sme všetky tvoje papiere, ale myslíme si, že tvoje riešenie nie je správne.
Viac sa dozvieš v ďalšom príspevku vo fóre.
Počkaj pár minút.

Jeden z Opravovateľov Trojky

[jodik]

(09.02.2012 21:53:47)_jano Napísal:  Hehe,

sa to celkom rozbehlo na tom fóre..

Čo sa týka Teba Jodik,
dostali sme všetky tvoje papiere, ale myslíme si, že tvoje riešenie nie je správne.
Viac sa dozvieš v ďalšom príspevku vo fóre.
Počkaj pár minút.

Jeden z Opravovateľov Trojky

o to som viac zvedavý, keďže som presvedčený o opaku

[Xellos]

Ja osobne som voci tomu co napisem do rieseni dost skepticky, pretoze uz som dokazal vypotit riesenia ktore sa dost silno nezhodovali s tym co som nimi chcel povedat (ceresnicka na torte je iste moje riesenie ulohy
z FX, v ktorom boli rozumne asi prve 2 vety )

ale toto spravit, to je zlomyselnost ktoru si musim zapametat a ak budem mat moznost tak dotiahnut do vacsieho extremu a zopakovat *diabolsky smiech*

[_jano]

Prečo Tvoje riešenie, Jodík, nefunguje?

Podľa toho, čo si odovzdal a čiastočne dovysvetlené tým, čo si napísal na fórum používaš vo svojom riešení isté pole uzbolo typu boolean. Vždy keď nájdeš nejaký 'najkratší' úsek, tak do tohoto poľa napíšeš jednotky, na mieste, kde bol tento úsek.

Potom (podľa pochopenia tvojho riešenia), ak nájdeš ďalší najkratší úsek, tak pri svojom násobení 'dolava' x 'doprava' uvažujes 'dolava' nie po začiatok poľa, ale po prvú jednotku.

Teda ak máš vstup
3 10;
2 1 1 1 1 1 1 3 1 2,
tak máš dva najkratšie úseky, "21111113" a "312" a asi zistíš prečo ti to nefunguje.

Tvoje riešenie sme čítali asi 3 krát a bolo z neho veľmi ťažké zistiť, čo robíš.

Totiž, tvoje riešenie je naozaj veľmi nečitateľné, od písma až po skladbu viet.

Ale
Potom ako si napísal, prečítali sme si tvoje riešenie znova ešte 2krát a teraz som si to prečítal ešte raz
z veľkou snahou a použitím silnej dávky dešifrovania som prečítal vetu
"pole uzbolo nám netreba, zabudnite všetko čo som o ňom písal"

Táto veta dosť zmenila význam celého tvojho riešenia. Až dokonca vlastne môže byť správne

Tak som to prečítal celé znova, už som vynechal tú časť o tom poli,
Pochopil som, že to 'dolava' počítaš úplne inak. A mohlo by to aj fungovať.

Dostaneš teda 9 bodov, máš to skoro správne, ale sú tam drobné nezrovnalosti a máš strašný a nečitateľný popis.

Ospravedlňujem sa, za tie predošlé tri body, ale musíš uznať, že nepíšeš pekne.
Keby som hodnotil spôsobom "ak sa slovo nedá na tri pokusy prečítať, prekočím ho" tak máš nulu.
Nabudúce keď zistíš, že nejaká časť popisu je nesprávna a vysvetľuje tvoje riešenie inak ako naozaj funguje, zachovaj sa inak.
Buď ju preškrtni.
Alebo viditeľne napíš, že "toto je odveci a nesúvisí s riešením". Keď to napíšeš o vyše stranu ďalej nenápadne a nečitateľne, opravovatelia to môžu prehliadnuť.
Skús prosím nabudúce písať aj zrozumiteľnešie.
Snaž sa opravovateľov zmiasť čo najmenej.

Aj tento post by bol určite zrozumiteľnejší, keby som hneď na začiatku napísal, že máš spávne riešenie a nie vetu "Prečo Tvoje riešenie, Jodík, nefunguje?" však?

Jeden z Opravovateľov Trojky


Zhrnutie

Máš to dobre, len bolo treba viackrát čítať, a všimnúť si pár nenápadných viet. V dohľadnej dobe budeš mať napísaných vo výsledkovke 9 bodov.
Nabudúce píš čitateľnejšie a zrozumiteľnejšie.

[Trazzy]

Tak toto je asi najväčší prevrat v dejinách OI.