MDCS Bubble Cup 2011

Re: MDCS Bubble Cup 2011 03.04.2011. u 16:15 · pre 189 meseci #21

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.

Potpis

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ć

Re: MDCS Bubble Cup 2011 04.04.2011. u 10:03 · pre 189 meseci #22

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

Re: MDCS Bubble Cup 2011 04.04.2011. u 22:08 · pre 189 meseci #23

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.

Re: MDCS Bubble Cup 2011 10.04.2011. u 13:06 · pre 189 meseci #24

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

Re: MDCS Bubble Cup 2011 10.04.2011. u 17:14 · pre 189 meseci #25

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.

Re: MDCS Bubble Cup 2011 10.04.2011. u 17:31 · pre 189 meseci #26

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

Re: MDCS Bubble Cup 2011 10.04.2011. u 17:41 · pre 189 meseci #27

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

Re: MDCS Bubble Cup 2011 12.04.2011. u 13:35 · pre 189 meseci #28

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

Re: MDCS Bubble Cup 2011 12.04.2011. u 22:23 · pre 189 meseci #29

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

1

Re: MDCS Bubble Cup 2011 13.04.2011. u 04:13 · pre 189 meseci #30

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

Potpis

IRC is just multiplayer notepad.

Re: MDCS Bubble Cup 2011 13.04.2011. u 04:30 · pre 189 meseci #31

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(" +", " ")

Re: MDCS Bubble Cup 2011 13.04.2011. u 13:58 · pre 189 meseci #32

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

Potpis

IRC is just multiplayer notepad.

Re: MDCS Bubble Cup 2011 14.04.2011. u 20:26 · pre 189 meseci #33

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

Re: MDCS Bubble Cup 2011 15.04.2011. u 00:28 · pre 189 meseci #34

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

Potpis

IRC is just multiplayer notepad.

Re: MDCS Bubble Cup 2011 17.04.2011. u 07:28 · pre 189 meseci #35

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

Re: MDCS Bubble Cup 2011 17.05.2011. u 01:12 · pre 188 meseci #36

Kako napredujete?
Sad je bese druga runda u toku...

Forum kao aplikacija na telefonu

Srodne teme