[ ~Pavle~ @ 29.03.2011. 11:01 ] @


Bubble Cup je timsko takmičenje u rešavanju algoritamskih problema namenjeno studentima i srednjoškolcima u Srbiji i regionu. Cilj takmičenja je popularizacija programiranja među mladima i poboljšanje uspeha ekipa naše zemlje na međunarodnim takmičenjima, tipa ACM i sličnim. Takmičenje organizuje Informaciono društvo Srbije, a glavni pokrovitelj i organizator tehničkog dela takmičenja (osmišljavanje zadataka, realizacija takmičarskog sistema, web sajta itd) je Microsoft Development Center Serbia.
Možete pogledati pravila na adresi http://www.bubblecup.org/index.php?page=rules, ukoliko ne ispunjavate pravila i dalje se možete takmičiti radi zabave i treninga.
Danas je dostupna “Nulta runda” (“Round Zero”), jednostavan problem za one koje žele da se upoznaju sa Timus online sistemom. Ovaj problem (A+B problem) možete resiti na adresi http://www.bubblecup.org/index.php?page=problems. Pre nego što počnete sa rešavanjem problema molimo vas da se registrujte na adresi http://www.bubblecup.org/index.php?page=competitor. Nulta runda nije obavezna, ali preporučujemo da svi učesnici reše ovaj problem.

Napomena: Ukoliko se neko od vas već takmičio na BubbleCup-u, nemojte zaboraviti da se ponovo registrujete za ovogodišnji BubbleCup, četvrti po redu.

Za više informacija o takmičenju, posetite www.bubblecup.org, takođe možete nas „pratiti“ na Twitter-u (http://twitter.com/bubble_cup) i na Facebook-u (http://www.facebook.com/group.php?gid=55209439436)

Odlična priprema za vas može biti zbirka rešenih zadataka sa Bubble Cup v.3, koju možete preuzeti sa stranice http://msacademic.rs/eBooks ili direktno sa http://msacademic.rs/download/bubbleBook.pdf.
Možete se registovati odmah! Takmičenje zvanično počinje 1-og Aprila, a zadatke je potrebno „dostaviti“ do 25-tog Aprila (kada je zvanično kraj prve runde - „Round 1“).
Ovo znači da nije kasno da se prijavite čak ni do 24-tog aprila, ali to ne preporučujemo! Ništa vas ne ograničava da se registrujete što pre, i da polako krenete sa rešavanjem zadataka.

Registruj se i pobedi!
The Bubble Cup Team
www.bubblecup.org
[ Nedeljko @ 29.03.2011. 11:13 ] @
Je li ovo neka sprdnja? Na ulazu su dati a i b, a na izlazu treba da se dobije a+b. Ah, da, postoje i ograničenja. Sme se koristiti najviše 16 MB u radu i račun ne sme da traje duže od sekunde. Pffff...
[ mmix @ 29.03.2011. 11:22 ] @
Pa nazalost ne bih rekao da je sprdnja, ako pogledas na tom sajtu problem set listu, ovaj problem je listed kao broj 1000 i prihvaceno je samo 50% predatih resenja :). Pretpostavljam da se svakakvi pacijenti javljaju na ove free konkurse pa valjda prve dve online runde sluze da se otkloni sut, a ova nulta runda je mozda i namerno toliko jednostavna da bi se ucesnici upoznali sa sistemom predavanja resenja. Ostali problemi vec od 1001 nisu tako prosti mada nisu ni komplikovani, doduse treba imati u vidu i uzrast takmicara i skillset koji mogu da imaju u tom uzrastu.

http://acm.timus.ru/detail.aspx?space=1&num=1000

Da se ne shvati pogresno, thumbs up za bubble cup, odlicna ideja da se angazuju momci i devojke za nesto sto nije reality tv ili derivat.
[ mmix @ 29.03.2011. 12:17 ] @
Dodao sam temu u izdvojene teme na naslovnoj strani, nadam se da ce to doprineti dolasku novih ucesnika.
[ stevan_nk @ 29.03.2011. 14:13 ] @
Mozete li samo navesti sa kojim programskim jezicima mozemo da dostavljamo resenja ?
[ stevan_nk @ 29.03.2011. 16:24 ] @
C, C++, Pascal, Java i C#.NET.
EDIT: ja se ponadao ima python :)

[Ovu poruku je menjao stevan_nk dana 29.03.2011. u 21:15 GMT+1]
[ Picsel @ 29.03.2011. 19:17 ] @
Kao ucesnik svih dosadasnjih Bubble Cup takmicenja, imam samo reci hvale. Organizacija je dobra a samo takmicenje je veoma izazovno.
Kao sto je receno, runda 0 je tu samo za upoznavanje sistema.
Prave kvalifikacione runde su mnogo teze, runda 2 nesto teza od runde 1. Problemi koji se resavaju su ozbiljniji algoritamski problemi, posebno u drugoj rundi gde se nadju i ekstremno teski zadaci (primer jednog takvog iz 2010. http://acm.timus.ru/problem.aspx?space=1&num=1369). Na sajtu postoji arhiva ranijih takmicenja, pa se detaljnije moze tamo pogledati.
Nakon online kvalifikacija, najbolji timovi se pozivaju na petocasovno finale koje je istog tipa kao i ACM ICPC takmicenje.

U svakom slucaju, definitivno preporucujem svim zainteresovanim za resavanje algoritamskih problema.
[ mmix @ 29.03.2011. 20:28 ] @
Sve, sve ali kako probijes 16Mb limit na rundi 0

Ajde timeout da razumem, neka mrtva petlja na citanju ulaza, ali 16Mb rama, kako to zauzems sa A+B problemom A 745 prijava je probilo
[ maksvel @ 29.03.2011. 21:57 ] @
Te što su probili angažuju kao beta testere.
[ TasmanF1 @ 29.03.2011. 23:06 ] @
Ovo je smešno
Evo uradio ovaj problem "1000" čitsto radi reda, podignem tamo i on mi kaže da je status "Crash"
Ovo je smešno koliko je prosto, sad više ne znam ko je lud

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace A_B
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Uneti prvi broj:");
            int a = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Uneti drugi broj:");
            int b = Convert.ToInt32(Console.ReadLine());
            int c = a + b;
            Console.WriteLine("Rezultat je: "+c);
            Console.ReadKey();
        }
    }
}
Vreme izvršavanja: 0.093    
Zauzeta memorija: 2.272 KB

Probao sam samo da im pošaljem kod u main delu ali onda mi izbaci error pri kompajliranju, a kad im pošaljem ceo kod onda Crash
Inače ovako kad je pokrenem radi normalno naravno

Ovde podižem
[ mmix @ 29.03.2011. 23:21 ] @
Nemoj nista da pises po konzoli sem resenja

http://acm.timus.ru/help.aspx?topic=csharp
[ Dr NIK @ 01.04.2011. 19:31 ] @
Nije mi jasno cemu sprdnja oko zadatka a + b. Poenta je da se upozna kako sistem radi, tj. kako se cita input i ispisuje output koji sistem moze da prepozna. Sve se odigrava u istom okruzenju u kom ce biti izvrsavani zadaci iz runde 1 i 2.

I naravno, mislim da je jako pametno imati ovakav zadatak jer sa obzirom da ima toliko neuspelih resenja, ocigledno da ljudima treba par proba dok ne ukapiraju kako sistem radi.

Kako napredujete sa rundom 1?
[ Rato iks de @ 03.04.2011. 10:47 ] @
Da je lako, nije. Izgleda da ove programe nije tesko otkucati kad skontas o cemu se radi i sta traze. Moja ekipa je rjesila dva zadatka i prihvaceni su. Medjutim, naisli smo na problem u prvom zadatku. Znamo o cemu se radi i sto se tice prevoda tu nismo pogrjesili, ne mozemo da skontamo zasto je za neka rjesenja izlaz DA a za neka NE. Zasto je za 10 2 6 izlaz DA, kako doci do toga?

HVALA
[ mmix @ 03.04.2011. 11:35 ] @
Pa recimo da su deonice 1000, 1 i 1000 pobedice 10,2,6

A sad kako resii, zar t one bi bilo varanje?
[ chaami @ 03.04.2011. 11:36 ] @
Ako je, na primer, duzina prve sekcije 55%, druge 5% a trece 40% svakako da ce prvi takmicar biti najbrzi. Mislim da je ukupna duzina konstantna a da ti mozes da menjas samo duzinu sekcija. Ako je tako onda ti tri petlje brzo resavaju problem.
[ mmix @ 03.04.2011. 11:43 ] @
Do koliko bi gurao petlje? I sta ce ako imas dva superbrza ucesnika sa istim brzinama ;), recimo 10, 10, 10. Iako su najbrzi nemoguce je odrediti duzine deonica da neko od njih dvoje pobedi.

[ chaami @ 03.04.2011. 11:51 ] @
Ako imas dva superbrza ucesnika odgovor ce za oba biti No.
Kolike petlje treba da budu? Mislis na duzinu cele staze... nemam pojma.... stasvi koliko god... samo da ti ne predje one dve sekunde i 16Mb.
Mislim da je 10000 vise nego dovoljno.
[ mmix @ 03.04.2011. 12:46 ] @
Ja znam da treba da bude No, ali ako krenes resenjem sa petljama neces dobiti No, ispucaces petlju ili ces doterati do nekog overflowa ako ne spucas limit prvo. I ne nadasj se mnogo da ce ti petlje do 10000 biti dovoljne, resenje se uvek testira granicnim vrednostima da sprece bruteforce metodu. A realno mislim da bi spucao timeout na O(N4) resenju sa N=10000 veoma lako
[ Picsel @ 03.04.2011. 14:18 ] @
Deonice ne moraju biti celi brojevi, niti je ukupna duzina konstantna.
[ chaami @ 03.04.2011. 14:30 ] @
Mozda petlja nije dobro resenje... ne znam, nisam probao. U svakom slucaju pitanje je bilo zasto je odgovor DA u nekim situacijama i kako doci do njega. Sto se petlje tice ne znam kako ti racunas broj kombinacija i prolaza ali sa 10000 ih ima 9998+9997+9996+9995+.....+1=49985001
for(int i=1;i<9999;i++)
{
for(int j=1;j<(10000-i);j++)
{
for(int k=1;k<(10001-i-j);k++)
a 50 miliona prolaza i nije nesto preterano.
[ mmix @ 03.04.2011. 15:15 ] @
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.
[ chaami @ 04.04.2011. 09:03 ] @
Da. U pravu si. Potpuno sam promasio poentu. Treba uporediti brzine takmicara. Staza je nebitna.
[ Dr NIK @ 04.04.2011. 21:08 ] @
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.
[ jaso19 @ 10.04.2011. 12:06 ] @
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;
}

[ Dr NIK @ 10.04.2011. 16:14 ] @
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.
[ jaso19 @ 10.04.2011. 16:31 ] @
Hvala na savijetima @Dr Nik, nadam se da cu skontat do cega je. :D
[ Dr NIK @ 10.04.2011. 16:41 ] @
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
[ jaso19 @ 12.04.2011. 12:35 ] @
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);
    }
[ Dr NIK @ 12.04.2011. 21:23 ] @
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
[ peka @ 13.04.2011. 03:13 ] @
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).
[ Dr NIK @ 13.04.2011. 03:30 ] @
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]
[ peka @ 13.04.2011. 12:58 ] @
Da, to je trazeni rezultat. I nema potrebe za obradom ulaznog stringa. Okaci kod pa da vidimo.
[ Dr NIK @ 14.04.2011. 19:26 ] @
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


[ peka @ 14.04.2011. 23:28 ] @
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...
[ Dr NIK @ 17.04.2011. 06:28 ] @
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 ...
[ TasmanF1 @ 17.05.2011. 00:12 ] @
Kako napredujete?
Sad je bese druga runda u toku...