Информации за натпревари

[cYb3rc0re]

Јас на претходниот учествував и зедов маичка и ранче (бев 22-ро место).

На овај не почнав, а не знам ни дали ќе можам, пошто не бев на онлајн 1 рундата. Плус тоа, знам дека има јаки деца а и за овие алгоритми треба малце вежбање, не се баш нешто што го среќавам во обичниот „печалбарски“ програмерски јазик, така да освен ако не е подобар квалитетот на маичката и ранецот од лани, не се исплати втор пат . Шала.

Иначе честито на 2-ро место, за малце Иподчето ќе го земеше

 

[deXterche]

Прва елиминациона рунда, утре (20.04.2008) 12:00 - 14:00 часот.

Импресии од warmup: Ептен жустра битка. Иако беше мал бројот на учесници, битката за врвот беше неизвесна дури два дена после натпреварот. Имаше еден победник, па се откри грешка во една задача, па дојдоа два победници со ист број на поени, за да после два дена се утврди дека едниот бил 15 минути побрз од другиот. Тој другиот беше вашиот форумџија HsIlOmEdUs, за жал. Победникот е еден мој драг колега и team-mate за на ACM-ICPC - Никола Постолов.

За утре се очекува плејада од натпреварувачи и не толку компетента битка. Причината е нели - само 100 идат понатаму. Кој се нема регистрирано, сега му е мајката. И да да прашам: deXterche, Dr_ViRuS и останатите студенти информатичари, учествувате бе?

Till tomorrow... :pishtoldz

Сакав да учествувам но се погоди баш во колоквиумска недела (вчера ми заврши колоквиумската). Иначе честитки HsIlOmEdUs за второто место!

 

[back_rest]

HsIlOmEdUs пак под Постолов а ?? , нишо боње е од тебе (џаст кидин)
Иначе јас само надгледувам резултати и задачи, зашо јава е официален јазик а јас не сум имал контакт со тоа неможам да учествувам, не ја знам синтаксата
Овие тороман и трајче9 се фаворити за сеа а ?? или ке ги средите вие како електраши ?!

Хехе, ова предизвик е?
Интересно е сепак, на warmup-от различен спротивен беше резултатот, сега пак вака се погоди. Ќе одлучи понатака резултатот.

 

[Dr_ViRuS]

Далеко е Софија ако се оди пеш до Скопје ....ангажиран 100%
п.с мака ми е што не освои IPOD .
Поздрав до твојата блиска околина

п.с 2
Постирај ги барем задачите да видиме што дават?

 

[back_rest]

Далеко е Софија ако се оди пеш до Скопје ....ангажиран 100%
п.с мака ми е што не освои IPOD .
Поздрав до твојата блиска околина

п.с 2
Постирај ги барем задачите да видиме што дават?

- a????
- данкешен фор компашн
- поздравена!

За задачите, хммм.... не ќе да е лошо. Ај да ги присоберам. Објаснение, код или и двете?

 

[back_rest]

Codefu 2008 warmup round

1. Most used character pair

Return the character pair that appears most times in one sentence.

Character pair is a pair of consecutive characters in the sentence.
Words in the sentence are divided with blank (' ') characters.

There may be multiple consecutive blanks on the beginning, end or in the middle of the sentence.

Blank (' ') characters are not counted, but still separate the other characters.

e.g.

If two pairs show up in the same number of words, return the character pair
that comes up first alphabetically.

Remember: the return type is String of length two.

Задачата е straight-forward. For или while циклус за сите карактери и чување матрица од димензии 26x26 за повторување на секој пар карактери. Мада јас во решението малце ја искомплицирав.

public String mostUsed(String sentence) {
        int []numOccur= new int[((int)('z'-'a')+1)*((int)('z'-'a')+1)];
        int ch1, ch2;
        for (int i = 0; i < sentence.length()-1; i++) {
            if (sentence.charAt(i)==' '|| sentence.charAt(i+1)==' ') continue;
            ch1 = (int)(sentence.charAt(i))-'a';
            ch2 = (int)(sentence.charAt(i+1))-'a';
            numOccur[ch1*((int)('z'-'a')+1)+ch2]++;
        }
        int max=0;
        int maxInd=-1;
        for (int i = 0; i < numOccur.length; i++) {
            if (numOccur[i]>max)
            {
                max = numOccur[i];
                maxInd=i;
            }
        }
        
        return ""+(char)('a'+maxInd/((int)('z'-'a')+1))+(char)('a'+maxInd%((int)('z'-'a')+1));
    }

2. Mirrors

Find the number of words from one sentence that are mirrored in the second sentence.

One word is a sequence of characters which on it's beginning and end has either a
space, beginning or end of line.
e.g. "I am a nice little sentence"
has 6 words: "I", "am", "a", "nice", "little", "sentence"

Mirrored word is a completely reversed word
e.g. "sentence" mirrored is "ecnetnes"

If one word is mirrored multiple times, it still counts as one occurrence.

The words and mirror comparison must be case insensitive
e.g. "ecnetnes" and "EcNETnes" are both mirrors of "sentence"

И овде нема некоја филоСофија за мислење. Наједноставно е со користење на set структура на податоци (множество - не дозволува дупли податоци) да се среди проблемот за само едното појавување, а со претходно обраќање на вториот стринг, проблемот да се доведе само до споредување на елементи.

public int howMany(String sentence1, String sentence2) {
        sentence1=sentence1.toLowerCase();
        sentence2=sentence2.toLowerCase();
        Set<String> st1= new HashSet<String>();
        StringTokenizer stk = new StringTokenizer(sentence1);
        while (stk.hasMoreTokens())
            st1.add(stk.nextToken());
        Set<String> st2= new HashSet<String>();
        String sentence2a="";
        for (int i = sentence2.length()-1; i >=0 ; i--) {
            sentence2a+=sentence2.charAt(i);
        }
        stk = new StringTokenizer(sentence2a);
        while (stk.hasMoreTokens())
            st2.add(stk.nextToken());
        Object []ar = st1.toArray();
        int num=0;
        for (int i = 0; i < ar.length; i++) {
            if (st2.contains((String)ar[i]))
                    num++;
        }
        return num;
    }

3. Islands

We are given a map where 'X' defines the land and ' ' defines the sea.
Out task is to count the number of islands.

One piece of land is defined is an island with the whole land it connects.
The connection can be on each of the four sides of the land.

e.g. Following is one island
" XXX",
"X X",
"XX X",
"XXXXX"
e.g. Following are 4 islands
" XX ",
"X X",
"XX X",
"X XX "
shown with numbers
" 44 ",
"1 3",
"11 3",
"1 22 "
Two pieces of land are connected only if they are connected with one full side.
(only a corner connection is not enough).

Flood-fill техника. Два фор циклуси за сите полиња во полето и повик кон flood-fill за секое пронајдено "X". Flood-fill-от ги чисти полињата, а следствено на тоа само еднаш ќе биде повикан за еден остров. Броењето на истите повици го дава решението.

nt []dx={0, 1, 0, -1};
    int []dy={-1, 0, 1, 0};
    int numIslands;
    int [][]map;
    int maxX, maxY;

    public int howMany(String[] map) {
        
        numIslands=0;
        this.map = new int[map.length][map[0].length()];
        maxX = map.length;
        maxY = map[0].length();
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length(); j++) {
                this.map[i][j]=map[i].charAt(j)=='X'?1:0;
            }
        }
        
        for (int i = 0; i < maxX; i++) {
            for (int j = 0; j < maxY; j++) {
                if (this.map[i][j]==1)
                {
                    doIt(i, j);
                    numIslands++;
                }
            }
            
        }
        return numIslands;
}
    public void doIt(int x, int y)
    {
        int mx, my;
        map[x][y]=0;
        for (int i = 0; i < 4; i++) {
            mx = x +dx[i];
            my = y +dy[i];
            if (mx<0 || mx>=maxX) continue;
            if (my<0 || my>=maxY) continue;
            if (map[mx][my]==0) continue;
            
            doIt(mx, my);
        }
                
    }

4. Asteroids

We have a group of asteroid which are falling on the mars station.
The station has a length of N meters, and the shield can cover only M meters of this length.
The shield can move only 1 meter in each direction, and at the beginning it starts at the position of 0.

The asteroids are falling on a specific position and cover one exact meter.
For the ease of the task, the asteroids are falling on exact meter positions,
meaning they can't overlap parts of two meters of the station.
They also fall on the exact 0 second of the given minute.

Our task is to find the minimal number of the asteroids that will hit the station if we
optimize the movement of the shield to catch most of the asteroids.

Решението сеуште ми е сумљиво и доста дискутабилно. Точно е сепак. Значи, dynamic programming со состојба [време][позиција на штит].

int [][]numHitsAfter;
    boolean [][]numHitsGott;
    //[time][shPos]
    int []time;
    int []position;
    int shieldlength;
    int maxTime;
    int maxPos;
    public int hits(int length, int shieldlength, int[] time, int[] position) {
        numHitsAfter = new int[1000][1000];
        numHitsGott = new boolean[1000][1000];
        maxTime = 0;
        for (int i = 0; i < position.length; i++) {
            if (maxTime< time[i]) maxTime = time[i];
            if (maxPos< position[i]) maxPos = position[i];
        }
        maxPos = Math.min(length, maxPos);
        this.shieldlength = shieldlength;
        this.time = time;
        this.position = position;
        
        return doIt(0,0,0);
        //deka = 0-desno i vo mesto
        //1 - levo - vo mesto
        //2 - nasekade
    }
    int doIt(int timeA, int pos, int deka)
    {
        if (numHitsGott[timeA][pos]) return numHitsAfter[timeA][pos];
        //proverka za vo toa vreme
        int momHits=0;
        for (int i = 0; i < time.length; i++) {
            if (time[i]==timeA)
                {
                    if (position[i]<pos || position[i]>=pos+shieldlength)
                        momHits++;
                }
            
        }
        int a1, a2, a3;
        timeA++;
        if (timeA > maxTime)
        {
            a1=a2=a3=0;
        }
        else
        {
            a2 = doIt(timeA, pos,0); //vo mesto
            if (pos+1 > maxPos) a1=a2;
            else a1= doIt(timeA, pos+1, 0); // vo desno
            
            if (pos-1 < 0) a3 = a2;
            else a3 = doIt(timeA, pos-1,0); //vo levo
        }
        timeA--;
        numHitsGott[timeA][pos]=true;
        return numHitsAfter[timeA][pos]=Math.min(Math.min(a1, a2), a3) + momHits;
    }

 

[back_rest]

Codefu 2008 warmup round

5. Expression

Create the smallest expression in order to evaluate to a certain number.
The expression can contain only characters given in an input string.

e.g. We need an expression from "023*+" which evaluates to 15
2*3*3-3

The multiply "*" and add "+" operands are special that they are always producing at most 1000.
Meaning, whenever the result is more than 1000, they are always giving 1000 as result.
The division "/" is always returning the integer part of the division. e.g. 11/3 equals to 3.
The substraction "-" never returns negative numbers.
Meaning, whenever the result is a negative number, they are always converted to 0.

Note: Remember, * and / have precedence over + and -

Return the length of the smallest expression.
If the target number can't be expressed, return 0

Ова е задача чие решение е испитување на својствата на даденото и она што се бара. Огромен удел имаат ограничувањата (на 1000 и 0) кои се наведени во задачата. Тие го скратуваат множеството на решение во доволно мала мера за изведување на некое решение.
Значи целта е да се утврди правилниот редослед на градењето на изрази, а потоа да се градат комбинации. Редоследот е:
1. Цели броеви
2. Множење/делење
3. Собирање/одземање
Јасно станува од кодот.

public int []resBroj = new int[1001];
    public int []resMonom = new int[1001];
    public int []resPolinom = new int[1001];
    
    boolean []novBroj = new boolean[1001];
    boolean []novMonom = new boolean[1001];
    boolean []novPolinom = new boolean[1001];
    
    public int smallest(String allowed, int target) {
        boolean mPlus=false, mMinus=false, mPo=false, mDeli=false;
        for (int i = 0; i < allowed.length(); i++) {
            if (Character.isDigit(allowed.charAt(i)))
            {
                resBroj[(int)(allowed.charAt(i)-'0')]=1;
                novBroj[(int)(allowed.charAt(i)-'0')]=true;
            }
            else
            {
                switch (allowed.charAt(i))
                {
                    case '+':mPlus=true;break;
                    case '-':mMinus=true;break;
                    case '*':mPo = true;break;
                    case '/':mDeli = true;break;
                }
            }
        }
        
        boolean imaPromena = true;
        
        while (imaPromena)
        {
            imaPromena = false;
            for (int i=0; i<resBroj.length; i++)
            {
                if (resBroj[i]>0)
                {
                    [i]//novBroj=false;
                    for (int j=0; j<resBroj.length; j++)
                    {
                        if (resBroj[j] >0)
                        {
                            if (i!=0) imaPromena |= dodadiBroj(i*(resBroj[j]==4?10000:(resBroj[j]==3?1000:(resBroj[j]==2?100:10)))+j,resBroj[i]+resBroj[j]);
                            if (j!=0) imaPromena |= dodadiBroj(j*(resBroj[i]==4?10000:(resBroj[i]==3?1000:(resBroj[i]==2?100:10)))+i,resBroj[i]+resBroj[j]);
                            
                        }
                    }
                    
                }
            }
        }
        
        for (int i = 0; i < resMonom.length; i++) {
            if (resBroj[i]>0)
            {
                resMonom[i]=resBroj[i];
                novMonom[i]=true;
            }
        }
        imaPromena = true;
        while (imaPromena)
        {
            imaPromena = false;
            for (int i=0; i<resMonom.length; i++)
            {
                if (resMonom[i]>0)
                {
                    novMonom[i]=false;
                    for (int j=0; j<resMonom.length; j++)
                    {
                        if (resBroj[j] >0)
                        {
                            if (mPo) imaPromena |= dodadiMonom(i*j, resMonom[i]+resBroj[j]+1);
                            if (mDeli && j!=0) imaPromena |= dodadiMonom(i/j, resMonom[i]+resBroj[j]+1);
                        }
                    }
                    
                }
            }
        }
        for (int i = 0; i < resMonom.length; i++) {
            if (resMonom[i]>0)
            {
                resPolinom[i]=resMonom[i];
                novPolinom[i]=true;
            }
        }
        imaPromena = true;
        while (imaPromena)
        {
            imaPromena = false;
            for (int i=1; i<resPolinom.length; i++)
            {
                if (resPolinom[i]>0)
                {
                    [i]//novPolinom=false;
                    for (int j=1; j<resPolinom.length; j++)
                    {
                        if (resMonom[j]>0)
                        {
                            if (mPlus) imaPromena |= dodadiPolinom(i+j, resPolinom[i]+resMonom[j]+1);
                            if (mMinus) imaPromena |= dodadiPolinom(i-j, resPolinom[i]+resMonom[j]+1);
                            [i]//if (mMinus) imaPromena |= dodadiPolinom(j-i, resPolinom+resPolinom[j]+1);
                        }
                    }
                    
                }
            }
        }
        
        return resPolinom[target];
    }
    boolean dodadiMonom(int vred, int expr)
    {
        if (vred>1000) vred=1000;
        if (vred<0) vred=0;
        
            if (resMonom[vred]==0 || resMonom[vred]>expr)
            {
                resMonom[vred]=expr;
                novMonom[vred]=true;
                return true;
            }
        return false;
    }
    
    boolean dodadiPolinom(int vred, int expr)
    {
        if (vred>1000) vred=1000;
        if (vred<0) vred=0;
            if (resPolinom[vred]==0 ||resPolinom[vred]>expr)
            {
                resPolinom[vred]=expr;
                novPolinom[vred]=true;
                return true;
            }
        return false;
    }
    
    boolean dodadiBroj(int vred, int expr)
    {
        if (vred>1000) return false;
        if (resBroj[vred]>0) return false;
        resBroj[vred] = expr;
        novBroj[vred]= true;
        return true;
    }

Се изморив.

 

[loverboy]

Hasilomedus, Ти честитам за победата на codefu.
Се регистрирав овде пред се да ти честитам. Инаку јас сум igorkulev, освоив 8 место, но не е лошо бидејќи Java знам 3 дена пред рунда 1, специјално научив за натпреварот
ке дадам малм коментар за задачите, првата не беше тешка но сепак имаше да се напишат неколку услови и да се разгледаат неколку работи, и за 100 бода требаше добро да се разгледаат сите случаи. Јас имав 50 на таа, имав успешност 99/100 (само на еден ми падна) знам каде ми е грешката. Втората беше интересна задачата. Малку само требаше да се употреби логика на кој начин да се декоидра пораката. Третата ја знаев од порано, Polish notation е познат проблем, но касно ми текна на решението, се користат стрингови, само треба да се внимава на заградите. Во линеарно време се решава. А четвртата е класично динамичко програмирање. Се користи низа од [30][30][30][30]. Значи треба да се најде оптимално решение за секоја од можните комбинации. Само немаше шанси да го напишпам кодот за толку кратко време Значи уште еднаш честитки на Hsilomedus, колегата од електро
Драго ми е што првите тројца победници се од електро http://www.feit.ukim.edu.mk/student/homepage.html Се надевам дека ќе се видиме на подготовките за ACM,
Поздрав, Игор

 

[nelo]

Ке може ли некој подетално да ми објасни што точно се рабори на <codefu/>

 

[back_rest]

Hasilomedus, Ти честитам за победата на codefu.
Се регистрирав овде пред се да ти честитам. Инаку јас сум igorkulev, освоив 8 место, но не е лошо бидејќи Java знам 3 дена пред рунда 1, специјално научив за натпреварот
ке дадам малм коментар за задачите, првата не беше тешка но сепак имаше да се напишат неколку услови и да се разгледаат неколку работи, и за 100 бода требаше добро да се разгледаат сите случаи. Јас имав 50 на таа, имав успешност 99/100 (само на еден ми падна) знам каде ми е грешката. Втората беше интересна задачата. Малку само требаше да се употреби логика на кој начин да се декоидра пораката. Третата ја знаев од порано, Polish notation е познат проблем, но касно ми текна на решението, се користат стрингови, само треба да се внимава на заградите. Во линеарно време се решава. А четвртата е класично динамичко програмирање. Се користи низа од [30][30][30][30]. Значи треба да се најде оптимално решение за секоја од можните комбинации. Само немаше шанси да го напишпам кодот за толку кратко време Значи уште еднаш честитки на Hsilomedus, колегата од електро
Драго ми е што првите тројца победници се од електро http://www.feit.ukim.edu.mk/student/homepage.html Се надевам дека ќе се видиме на подготовките за ACM,
Поздрав, Игор

Игор, welcum` to kajgana mate! Фала на честитките, туку морам и на тебе да ти честитам пошо прва година јас бев dummy за вакви ствари, а камоли па 8 место да извадам. Големи работи се очекуваат од тебе дете . Плус и Валентина ми збореше добро за тебе .

Е сега, задачите. На место беа, солидни. Првата ако тргнавте со строга Java и библиотеките, брзо се решаваше. Ама изгледа само јас решавав така... Втората беше пенал, два фор циклуси. Третата да, комплицирана рекурзија само, се тргнуваше во обратна насока на стрингот. Додуша јас итеративно ја направив за да е појака. Четвртата dynamic programming, точно. Имаше flood-fill, еден чист, друг само со разгледување. Петата, ако го немаше тоа „исти по големина згради“ ќе ја решев, идеше divide & conquer. Вака, има некоја фркичка.

За ACM, шо се секираш, ќе биде. Догодина има гуруа да направиме од вас

Ке може ли некој подетално да ми објасни што точно се рабори на <codefu/>

http://www.codefu.com.mk/
Најкратко речено: алгоритамски натпревар во Java. Ти даваат проблеми, ти бараат решение. Толку.

 

[DuFFy]

Честито Hasilomedus, ко што сум слушал за Постолов по колегиве(тие шо го знаат) мислев дека нема шанси да го победи некој...ама ете не те знаеле тебе....

п.с. Знаеш некој C++ натпревар по нетов, немора награди да има или сл....чисто за занимација !?
ЕДИТ: Не го видов ова кајгана OpenCode

 

[back_rest]

Google CodeJam 2008
Започнува за 3 дена. Најдобрите 500 од првите рунди одат на локални натпревари во преставништвата на Google. Најдобрите 100 одат во главното седиште. Има и парични награди.

 

[back_rest]

<codefu/> Seasonal 2008 Autumn.

Види види.

 

[SkyDriver]

CodeFu 2009

Натпреварувачки рунди:
Онлајн Рунда 1: 26.04.2009 12:00-14:00
Онлајн Рунда 2: 17.05.2009 12:00-14:00
Финална рунда: 31.05.2009 12:00-15:00

 

[drle]

CodeFu 2009

Натпреварувачки рунди:
Онлајн Рунда 1: 26.04.2009 12:00-14:00
Онлајн Рунда 2: 17.05.2009 12:00-14:00
Финална рунда: 31.05.2009 12:00-15:00

Имав високо мислење за овај натпревар, но денес сите позитивни впечатоци од претходните натпревари се претворија во најголемо разочарување. Изгледа дека кај нас не може да функцинира нешто без никакви проблеми. Ова го пишувам додека чекам да се отвори третата задача. И сум попизден до даска. Со крајни сили се воздржувам да не почнам да редам се по список.