[es] - MDCS Bubble Cup 2011

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6042

+4631 Profil

Re: MDCS Bubble Cup 2011

^{03.04.2011. u 15:15 - pre 159 meseci}

Ne moze tako, sve i da je smisleno. Duzina svake deonice je arbitrarna. Masis poentu, nije poena dal odrediti koja je duzina na kojoj pobewdjuje, vec dal moze da se nameste duzine tako da igrac pobedi, sama duzina deonice moze da bude daleko daleko veca od bilo koje racunarske reprezentacije brojeva :) Da nije tako, bio bi to uslov zadatka.

Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić

Odgovor na temu

chaami
Goran Petrović
nezaposlen
Beograd

Član broj: 262685
Poruke: 84
77.243.20.*

+28 Profil

Re: MDCS Bubble Cup 2011

^{04.04.2011. u 09:03 - pre 159 meseci}

Da. U pravu si. Potpuno sam promasio poentu. Treba uporediti brzine takmicara. Staza je nebitna.

Odgovor na temu

Dr NIK
Novakovic Marko
BG

Član broj: 19744
Poruke: 132
*.uwaterloo.ca.

Sajt: www.mnovakovic.info

+1 Profil

Re: MDCS Bubble Cup 2011

^{04.04.2011. u 21:08 - pre 159 meseci}

Definitivno jako zanimljiv zadatak. Nazalost deluje mi kao da ne moze da se resi uz znanje "out of the box" (iliti common sense) moraju da se koriste fensi stvarcice.

Odgovor na temu

jaso19

Član broj: 263197
Poruke: 4
62.113.4.*

+1 Profil

Re: MDCS Bubble Cup 2011

^{10.04.2011. u 12:06 - pre 158 meseci}

Prijavio sam se na BubbleCup i pokusao rijesiti zadatak Visits, na dva testa program radi dobro, ali kad se pokrene na serveru dobijem WRONG ANSWER na testu 9. Ako moze neko da mi pokaze gdje grijesim. Unaprijed zahvaljujem.

Code:

#include <iostream>
#include <cmath>
#include <exception>
using namespace std;
class Visits {
    public:
        int izracunaj() throw (exception) {
            int n;

            cin >> n;
            if (n < 2 || n > 100000)
                 throw exception();
            int duzina = 0;
            int** niz = new int*[n];

            for(int i=0; i < n; i++)
                niz[i] = new int[2];
            for (int i = 0; i < n; i++) {
            int unosX;
            int unosY;
            cin >> unosX;
            cin >> unosY;

            if (unosX < 1 || unosX > 1000000)
                throw exception();
            if(unosY < 1 || unosY > 1000000)
                throw exception();

            niz[i][0] = unosX;
            niz[i][1] = unosY;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    duzina += abs(niz[i][0] - niz[j][0])
                            + abs(niz[i][1] - niz[j][1]);

                }
            }
        }
        return (int)duzina / (n*(n-1));
        }
};
int main() {

    try {
            Visits v;
    cout << v.izracunaj();
    } catch (exception e) {

    }
    return 0;
}

Odgovor na temu

Dr NIK
Novakovic Marko
BG

Član broj: 19744
Poruke: 132
*.uwaterloo.ca.

Sajt: www.mnovakovic.info

+1 Profil

Re: MDCS Bubble Cup 2011

^{10.04.2011. u 16:14 - pre 158 meseci}

Koliko ja vidim radis brute force resenje sto nikako ne bi trebalo da rezultira u losem resenju.

However, bas na testu 9 bi trebao da dobijes TLE - time limit exception (exception valjda) jer ti je resenje neoptimalno. Takodje, obrati paznju da ti duzina nije int nego long. Ne znam koje su velicine tipova u bitovima u C++-u, ali u javi je int <= 2^15. Long je <=2^31.

Odgovor na temu

jaso19

Član broj: 263197
Poruke: 4
62.113.4.*

+1 Profil

Re: MDCS Bubble Cup 2011

^{10.04.2011. u 16:31 - pre 158 meseci}

Hvala na savijetima @Dr Nik, nadam se da cu skontat do cega je. :D

Odgovor na temu

Dr NIK
Novakovic Marko
BG

Član broj: 19744
Poruke: 132
*.uwaterloo.ca.

Sajt: www.mnovakovic.info

+1 Profil

Re: MDCS Bubble Cup 2011

^{10.04.2011. u 16:41 - pre 158 meseci}

btw, kada kazem duzina mislim na tvoju promenljivu koju si nazvao duzina. Sa obzirom da posle imas return (int)duzina / (n*(n-1)); mozes pretpostaviti da za n = 1000, duzina je najmanje 1000^2 sto vec prelazi Java-in Integer.MAX_VALUE

Odgovor na temu

jaso19

Član broj: 263197
Poruke: 4
62.113.4.*

+1 Profil

Re: MDCS Bubble Cup 2011

^{12.04.2011. u 12:35 - pre 158 meseci}

Pokusao sam zamijeniti ugnjezdenu for petlju sa rekurzijom ali sad dobijem "Memory limit exceeded"

Code:

public static long rekurzivno(int i, int j, int n) {
        if (i == n)
            return 0;
        if (j == n - 1)
            return Math.abs(niz[i][0] - niz[j][0])
                    + Math.abs(niz[i][1] - niz[j][1])
                    + rekurzivno(i + 1, 0, n);
        if (i != j)
            return Math.abs(niz[i][0] - niz[j][0])
                    + Math.abs(niz[i][1] - niz[j][1])
                    + rekurzivno(i, j + 1, n);
        else return rekurzivno(i, j + 1, n);
    }

Odgovor na temu

Dr NIK
Novakovic Marko
BG

Član broj: 19744
Poruke: 132
*.uwaterloo.ca.

Sajt: www.mnovakovic.info

+1 Profil

Re: MDCS Bubble Cup 2011

^{12.04.2011. u 21:23 - pre 158 meseci}

Pa to je i ocekivano posto je rekurzivno bruteforce resenje zahtevnije od iterativnog. Deveti test je ogroman, pa mozes da pretpostavis sta se desava kada imas stek od par hiljada rekurzivnih poziva.

Resenje ne mogu da ti dam, ali sve sto mogu da kazem je da ti trenutno imas quadratic execution time a da bi ti resenje proslo mora da bude linearno. Nadam se da to moze da pomogne :)

Ja sam se zapeo na Ministry of Truth ne mogu nikako da izvalim gde je greska sve sto probam radi, ali opet imam WA na petom testu. To su najgore muke

Odgovor na temu

peka
Beograd

Član broj: 3947
Poruke: 124
*.dynamic.sbb.rs.

+2 Profil

Re: MDCS Bubble Cup 2011

^{13.04.2011. u 03:13 - pre 158 meseci}

WA na petom?

Cini mi se da sam i ja to dobijao na istom. Greska je bila sledeca: kada nadjes rec u ulaznom stringu, ne treba index da pomeras do sledeceg praznog mesta (razmaka), nego samo za jos jedan karakter, jer i on moze postati razmak. Primer:

Code:
elitesecurity rules
elite ecur

Kad nadjes prvu rec('elite'), index ne pomeras do sledeceg razmaka (na 13), nego samo preskocis 1 mesto, tj. nastavljas od index 6 (karakter 's' postaje razmak).

IRC is just multiplayer notepad.

Odgovor na temu

Dr NIK
Novakovic Marko
BG

Član broj: 19744
Poruke: 132
*.uwaterloo.ca.

Sajt: www.mnovakovic.info

+1 Profil

Re: MDCS Bubble Cup 2011

^{13.04.2011. u 03:30 - pre 158 meseci}

Jel ovo dobijes kao rezultat?

elite_ecur___ _____

To ja dobijem

Ali DJaba :/

Odnosno, i ja predjem na sledece slovo kada trazim, bas kao sto si i rekao. Algoritam je vrlo jednostavan posto je u pitanju samo gomila substring poziva. E sada jedino so meni pada napamet da ne valja je kako tretiram whitespace... Jel ti radis nesto tipa firstLine.trim().replaceAll(" +", " ")

_{[Ovu poruku je menjao Dr NIK dana 13.04.2011. u 04:40 GMT+1]}

Odgovor na temu

peka
Beograd

Član broj: 3947
Poruke: 124
*.dynamic.sbb.rs.

+2 Profil

Re: MDCS Bubble Cup 2011

^{13.04.2011. u 12:58 - pre 158 meseci}

Da, to je trazeni rezultat. I nema potrebe za obradom ulaznog stringa. Okaci kod pa da vidimo.

IRC is just multiplayer notepad.

Odgovor na temu

Dr NIK
Novakovic Marko
BG

Član broj: 19744
Poruke: 132
*.uwaterloo.ca.

Sajt: www.mnovakovic.info

+1 Profil

Re: MDCS Bubble Cup 2011

^{14.04.2011. u 19:26 - pre 158 meseci}

Pa ne bih da kacim moj code to bi bila velika pomoc mislim da nije fer, daj da probam da resim ovako.

Ajde mi reci sta dobijas za ovaj test case:



elitesecurity rules

     elite             ecur

Za moje resenje, meni je ovo isto sto i



elitesecurity rules

elite ecur

Odgovor na temu

peka
Beograd

Član broj: 3947
Poruke: 124
*.dynamic.sbb.rs.

+2 Profil

Re: MDCS Bubble Cup 2011

^{14.04.2011. u 23:28 - pre 158 meseci}

Moj program pukne (izbaci exception) za taj ulaz. A inace prolazi sve testove (accepted). Tako da to nije moguc ulaz. Uostalom, iz postavke zadatka

Citat:

The words in both utterances are separated with exactly one space; there are no leading or trailing spaces in each line.

Nazalost, ne mogu da ti pomognem, stvarno je glupo sto nisu dali vise testova, meni sad na desetom zadatku izbacuje WA na testu #21, dva dana se nerviram pokusavajuci da resim...

IRC is just multiplayer notepad.

Odgovor na temu

Dr NIK
Novakovic Marko
BG

Član broj: 19744
Poruke: 132
*.uwaterloo.ca.

Sajt: www.mnovakovic.info

+1 Profil

Re: MDCS Bubble Cup 2011

^{17.04.2011. u 06:28 - pre 158 meseci}

Posle 2 dana i ko zna koliko submitova i trazenja sam shvatio da je peti test u Ministry of Truth takav da je prva linija jaaako dugacak string (60000+ karaktera) a druga linija je prazna. A ja naravno nisam stavio guard za prazan string u drugoj liniji :/

Sada imam WA na devetom testu. Nadam se da ce se to uskoro resiti ...

Odgovor na temu