ManaSupo

Berlin Tegel - hostile for the unprepared

noreply@blogger.com (supo) — Tue, 08 May 2012 11:43:00 +0000

This is a little story of how the Berlin Tegel airport is awesome. NOT!

In Berlin they have this tiny conveyor belts just when you get of the plane and I managed to miss mine and walk to the other "room" from which they would not let me back to the belt. So I spent 15min negotiating with the security after which they decided to send me to a kind of lost&found office which was a NIGHTMARE to find because it is not marked and hidden in a maze of corridors. When I found it, the guy gave me a f*cking map of the airport with a path leading to the other side. The whole airport is a retarded maze of self-repeating hexagonal structures, where the only orientational point is the airport tower, which is about 5 meters tall :-D RIDICULOUS! I had to go outside of the airport to a shady backyard area and find a detached customs office located in a shed with nobody in it. It was an empty room with only a phone on the wall. The guy gave me a number I was supposed to call from this phone, so I did and I heard another man picking it up just behind a wall :-D I explained the situation to him and he was like "Alz rightz mizter Schvonawa, juzt a minute!". So I waited another quarter of an hour and then he appeared with my bag. I thanked him and started heading for the door and he went "Enschuldigung mizter Schvonawa, you havz to go thiz way!" pointing to another door. So I went and this room was darker and there were 2 officers siting behind a table. So I was like "nothing to do here" and I just walked to the exit on the other side. And they went "Ohoho mizter, pleaze comen sie here." They started interrogating me about why I came to Germany and just wouldn't understand what a "business trip for my startup" means. "Was is ze ztartup?" :-D After a while they asked me where I am coming from and they didn't seem to like "Zurich" as the answer.. after I gave them my Slovak passport they were totally confused and started asking about why I went to Zurich. After I told them that I live there they started LITERALLY laughing and pointing at the passport and saying "Rightz rightz.".
After I demonstrated that every millimeter of my backpack indeed only contains clothes, they let me go after which I spent another quarter hour finding my way to the bus stop on the airport.

Morale of the story: NEVER MISS THE FUCKING LUGGAGE BELT!

Gevent+Psycopg2 = execute cannot be used while an asynchronous query is underway

noreply@blogger.com (supo) — Sat, 03 Mar 2012 21:15:00 +0000

I am using a stack composed of, among others, Django + Gevent + Gunicorn + psycopg2 (greened with https://bitbucket.org/dvarrazzo/psycogreen/src).
Until recently, I was occasionally getting the following errors, if I rapidly reloaded our application that generates a couple of ajax calls on the startup:

ProgrammingError: execute cannot be used while an asynchronous query is underway
DatabaseError: execute cannot be used while an asynchronous query is underway

After getting the following versions:

Django 1.4 b1
Gunicorn 0.14
Gevent 0.13.6
psycopg2 2.4.4

And greening psycopg2 pre_fork like this (in the Gunicorn config):

worker_class = "gevent"
def def_pre_fork(server, worker):
    from psyco_gevent import make_psycopg_green
    make_psycopg_green()
    worker.log.info("Made Psycopg Green")
pre_fork = def_pre_fork

And using the gunicorn_django in a virtualenv to run the server from supervisor (instead of the manage.py shortcut):

[program:photobooks]
command=/path/bin/gunicorn_django -c /path/conf/photobooks_gunicorn.conf.py
directory=/path/src/photobooks
environment=PATH="/path/bin"

I was not able to reproduce the problem any more.

Chord progress in Celery

noreply@blogger.com (supo) — Thu, 01 Mar 2012 16:31:00 +0000

On our company blog I described the new server stack we use to run 47posters.com. One part of this stack is a distributed task queue Celery. We use it for 2 reasons:

hard task throttling - we have certain more processing heavy tasks, that if spawned by all Gunicorn processes at the same time would overwhelm the RAM of the server. With celery we can start them synchronously and use the --concurrency flag to control the number of heavy tasks processed in parallel

asynchronous tasks - we have one task that can take time in the order of minutes. This task is actually a collection of tasks that can be all done in parallel and then one synchronization tasks that runs after all the partial tasks are finished.
This synchronization task is done with chord and the collection of parallel tasks is modeled with a TaskSet.

There is only one tricky part - chord returns an AsyncResult corresponding to the synchronization task. If you then query the task_id given by this result, you can check for the cord completion. What you can't do is to track progress of the taskset completion. To do this, we have to create a new chord like this:

from celery.utils import uuid
from celery.task.chords import Chord
class progress_chord(object):
    Chord = Chord

    def __init__(self, tasks, **options):
        self.tasks = tasks
        self.options = options

    def __call__(self, body, **options):
        tid = body.options.setdefault("task_id", uuid())
        r = self.Chord.apply_async((list(self.tasks), body),
                                   self.options,
                                   **options)
        return body.type.app.AsyncResult(tid), r

(I highlighted the difference against the default celery.task.chord).
Now if you call the chord like this:

result_chord, result_set =
    tasks.progress_chord(taskSet)(syncTask.subtask(params))

You will be able to get both the result_chord.task_id and result_set.task_id.

Then what remains is to create a view that polls for the task status:

def check_batch_result(request):
  chord_result = AsyncResult(request.GET.get("chord_task_id",""))
  task_set_result = AsyncResult(request.GET.get("set_task_id","")).result
  response = {}
  response["tasks_completed"] = task_set_result.completed_count()
  response["tasks_total"] = len(task_set_result.results) 
  
  if chord_result.state == celery.states.PENDING:    
    response["status"] = "pending"
    
  elif chord_result.state == celery.states.STARTED:
    response["status"] = "started"

  elif chord_result.state == celery.states.RETRY:
    response["status"] = "retry"

  elif chord_result.state == celery.states.RETRY:
    response["status"] = "failure"
    
  elif chord_result.state == celery.states.SUCCESS:
    response["status"] = "successful"
    response["result"] = chord_result.result

  return Structure2JsonResponse(response)

pdfx.sty date conversion

noreply@blogger.com (supo) — Fri, 06 Jan 2012 15:00:00 +0000

Hi everybody,

there has been a bazillion changes in my life (finishing the Google internship and working in my startup fulltime) and I want to sum that up in another post. This is just a quick tip for people who want to generate PDF/X files with LaTeX.

Some resources:
http://ctan.org/tex-archive/macros/latex/contrib/pdfx
http://support.river-valley.com/wiki/index.php?title=Generating_PDF/A_compliant_PDFs_from_pdftex

From there, you want to make sure you handle your color profiles:
http://www.colormanagement.org/en/isoprofile.htm

One issue I run into with pdfx.sty a couple of times is a date conversion function, that in the original looks something like this:

\def\convertDate{\getYear}
{\catcode`\D=12
 \gdef\getYear D:#1#2#3#4{\edef\xYear{#1#2#3#4}\getMonth}
}
\def\getMonth#1#2{\edef\xMonth{#1#2}\getDay}
\def\getDay#1#2{\edef\xDay{#1#2}\getHour}
\def\getHour#1#2{\edef\xHour{#1#2}\getMin}
\def\getMin#1#2{\edef\xMin{#1#2}\getSec}
\def\getSec#1#2{\edef\xSec{#1#2}\getTZh}
\def\getTZh +#1#2{\edef\xTZh{#1#2}\getTZm}
\def\getTZm '#1#2'{%
    \edef\xTZm{#1#2}%
    \edef\convDate{\xYear-\xMonth-\xDay
      T\xHour:\xMin:\xSec+\xTZh:\xTZm}}
\expandafter\convertDate\pdfcreationdate

The problem with this piece of code is that it hard-codes the time format produced by \pdfcreationdate which seems to be different on different platforms (Miktex,Tex-live etc). This particular code expects the date to look like this:
D:20091202141420+05'00'

However people around the Internets are running into errors if their date has '-' instead of the '+' sign. The fix for that is simple, just substitute the sign in the above snippet. Btw the error looks like this:

! Use of \getTZh doesn't match its definition.
D:20120106132719Z

l.132 \expandafter\convertDate\pdfcreationdate

The time format that I've got from \pdfcreationdate was even more off:
D:20120106135936Z

To parse this, I had to rewrite the function entirely:

\def\convertDate{\getYear}
{\catcode`\D=12
 \gdef\getYear D:#1#2#3#4{\edef\xYear{#1#2#3#4}\getMonth}
}
\def\getMonth#1#2{\edef\xMonth{#1#2}\getDay}
\def\getDay#1#2{\edef\xDay{#1#2}\getHour}
\def\getHour#1#2{\edef\xHour{#1#2}\getMin}
\def\getMin#1#2{\edef\xMin{#1#2}\getSec}
\def\getSec#1#2#3{
    \edef\xSec{#1#2}
    \edef\convDate{\xYear-\xMonth-\xDay T\xHour:\xMin:\xSec}%
}
\expandafter\convertDate\pdfcreationdate

I will add to this article after I run the pdf through Distiller to check the PDF/X compliance.

opensubtitles.com pretending to be big

noreply@blogger.com (supo) — Sun, 11 Sep 2011 15:29:00 +0000

For one of my datamining projects, I decided to spend a weekend trying to find out how many subtitles you can actually get online for free. It took a bit of parallel python writing to scrape an entire website but I found a surprising discrepancy between the claimed database size and the actual number of subtitles they provide.

Opensubtitles.com claims to be and is addressed in various blogs as the biggest subtitle database online.

Claimed statistics:
68912 - movie count
1394569 - subtitle count

Actual statistics:
5486 - movie count
20003 - subtitle count

with top 5 languages being:
4029 English
2680 Polish
1876 Portuguese-BR
1643 Romanian
1061 Spanish

They are hiding the actual deficit in plain sight, check e.g.:

http://www.opensubtitles.org/en/search/sublanguageid-all/moviename-a/offset-1040

http://www.opensubtitles.org/en/search/sublanguageid-all/moviename-a/offset-1080

these are 2 consecutive pages in the list of subtitles they provide. Starting with the page 27 and 28 the rest of the 1438 pages provide identical contents.

On the other hand, this could be some kind of very strange bug on their part. But it seems very unlikely given the nature of the issue.

Looking for a job in Switzerland

noreply@blogger.com (mana) — Wed, 17 Aug 2011 14:09:00 +0000

My story

I came to Switzerland on the 15th of July and I already have a job, but I wouldn't say that it is easy to find a job here. It depends on your field, I'm structural engineer, so I'm writing from my point of view. I sent 22 emails and had 3 interviews until I got a job. I made a spreadsheet so I know where and when I sent an email, what they replied and more details (Danny's idea), very useful. I will write you some tips, which can help you to find a job.

Language

- if you speak German you have a BIG advantage (or French, Italian, depends on the part of Switzerland)

- if you don't speak, you have to learn as soon as possible

- http://www.radio24.ch/ radio with Swiss German

- http://zattoo.com/ online German channels

Curriculum Vitae

- https://europass.cedefop.europa.eu/ here you can create a good looking CV

Certificates

- if you have some certificates don't forget to scan them and attach to your application

Job offers

- http://www.jobwinner.ch/ on this website you can have your profile with all information about you and documents, so when you find an offer you like, you just write your cover letter and send an application with all information, which you have in your profile. But I prefer to write email directly to the company. Another advantage of this website is, that you can choose your field and new offers are sent to your email every day, that's really helpful

- http://www.jobs.ch/en/

- http://www.ingjobs.ch/de/ this is mostly for technical fields

- http://www.alpha.ch/

- of course there are more websites

Hiring

- many companies look for employees through recruiting agencies, which can be good, because they are trying to find a job for you, while they have money from that, but you don't know the company you are applying for

- better is to find offer of real company and check their website, do some research about their references and then you can make a better impression

Luck

- this is also very important part of looking for a job, so I wish you good luck ;)

Interning at Google - Week 2

noreply@blogger.com (supo) — Fri, 15 Jul 2011 21:47:00 +0000

The whirlpool is starting to spin and I am being pulled in. The infrastructure at our disposal is literally scary in both the scale and complexity of control and processes. Among the highlights of the second week, I had a lecture given by Bram Moolenaar the original author of our daily awesome Vim (shook his hand yay!) and the guy (can't remember the name:() who created the OO features in PHP proudly wearing this on his laptop.
Holding on :-)

Among the things I did during my Week 2 as a Software Engineer at Google are:

rock the medium difficulty on Battery by Metallica on drums in XBox Rock band
run a sequence of MapReduce tasks on 50T of data, using 2000 computing nodes
kick some ass and sometimes get my ass kicked in table tennis
come from work after midnight 3 days out of 5
get LOLs out of TONS of easter eggs hidden in various log/status outputs of various tools, that are stylized after various scify/fantazy franchises - you just hear people laughing in the office while they analyze a log dump from some random server/process/etc :-D
and last but not least, visit more classes than during a normal week at my old Uni.

I am starting to recognise some of the code-names people use in meetings and I am starting to see the real shape of what I'll be doing. So, so far so good ;-)

Fakulta Informatiky a Informačných technológií - FIIT

noreply@blogger.com (supo) — Sat, 09 Jul 2011 21:52:00 +0000

Pred pár týždňami som ukončil štúdium FIIT na STU v Bratislave, s titulom Ing. v obore Softvérové Inžinierstvo. Počas tých 5 rokov som stretlol nových ľudí, ktorí ma prekvapili aj v dobrom aj v zlom, starých známich som lepšie spoznal a čo-to nové som sa aj naučil. V tomto článku by som chcel zhrnúť moje pôsobenie na FIIT a zhruba načrtnúť stratégiu, ktorou som sa týchto 5 rokov riadil a na záver si dáme dolovanie v dátach zo sekcie Galéria študentov na webe fakulty ;-)

V prvom rade treba uviesť dôvody, pre ktoré som si FIIT vybral, po mojom štúdiu na Gymnáziu Jura Hronca (GJH). Jednak ma zaujala súťaž ProFIIT, ktorá sľubovala body extra na prímačky za riešenie programátorských úloh. Tiež som sa dozvedel, že na predmete TEAP sa dá dostať Á-čko za dobré umiestnenie na súťažiach www.topcoder.com/tc, aj ked pred nástupom na FIIT som mal absolvovaných len zopár súťaží. Otec mi raz povedal príhodu o Matfyzákovi, ktorý u nich vo firme nedokázal prakticky aplikovať svoje vedomosti a presadiť sa. Jasné, vytvoriť si názor na základe jedného človeka nie je správne. Moje rozhodnutie tiež ovplyvnili spolužiaci z GJH, ktorý, aspon čo sa týka našej triedy išli väčšina na FIIT. Aj keď FIIT nie je raj na zemi, teraz už viem, že som si vôbec nevybral zle.

Prvé dva roky na FIIT som strávil preliezaním povinných predmetov tak nejak aby sa nepovedalo a väčšinu voľného času som investoval do štúdia algoritmov a zadaní z programátorských súťaží. Na http://spoj.pl a podobných weboch som vyriešil stovky príkladov, na TopCoderi absolvoval stovku súťaží, prečítal desiatky článkov popisujúcich algoritmy zo všetkých možných oblastí informatiky. Prvý rok sa mi s Mišom Lohnickým nepodarilo postúpiť ani do regionálneho kola ACM, v Česko-Slovenskom kole sme skončili na 33 mieste, ako 6ty tím z FIIT. V druhom ročníku sme boli na ČR kole na 3. mieste a prvý z FIIT. Naše umiestnenie na regionálnom kole bolo samozrejme horšie, ale až do konca školi sme zostali prvý tím FIIT a aj prvý tím z tech. univerzít v ČR. Možno by to so súťažami dopadlo inak, keby sme sa tomu venovali celých 5 rokov. Trénovať algoritmy na FIIT nebolo v tej dobe jednoduché, lebo sme na to boli sami, neboli žiadne krúžky ani mentoring. Rovnako nebolo jednoduché presadiť sa medzi Matfyzákmi, ktorí už na strednej škole súťažili na medzinárodných olympiádach zatiaľ čo my sme jazdili na bicykli. V konečnom dôsledku však umiestnenie na súťažiach nie je až tak dôležité, aj keď fakt, že som bol v 2008 v Google Zurich na európskom finále Google Code Jam, vyzerá na CV dobre. Ovela viac som však prosperoval a prosperujem zo skúseností a nadhľadu, ktoré tréning na súťaže vytvoril.

V treťom ročníku nastal čas riešiť bakalárku a tak sme s Mišom dali dokopy tím s Martinom Labajom a Petrom Líškom a rok v kuse sme riešili študentskú softvérovú súťaž Imagine Cup organizovanú Microsoftom, v ktorej sme reprezentovali Slovensko na svetovom finále v Káhire. Projekt, ktorý nás posunul najmä v schopnosti predať sa, prezentovať a hovoriť s a pred ľudmi sa dá pozrieť tu.

V tomto období som už registroval tie dve skupiny ľudí a predmetov, ktoré sú okolo FIIT zformované:

Skupina PeWe, za kormidlom ktorej stojí Prof. Bieliková, sa zaoberá personalizovaním webu prostredníctvom výskumu (v NLP, user modelingu, odporúčacích, vizualizačných a vzdelávacích systémoch atp.), ktorý sa následne aplikuje a overuje prostredníctvom realizácie rôznych projektov, ktoré sú nasádzané či už na fakulte alebo mimo napr. v spoluprácii so SME. Skupina má veľký počet členov a tak podrobnosti hladajte na spomenutom odkaze. Členovia tejto skupiny sa často starajú o predmety Softvérového inžinierstva, procesov tvorby softvéru a pod.

Skupina na Ústave aplikovanej informatiky a príbuzných svoj výskum sústredí na oblasť umelej inteligencie, optimalizácie riešení rôznych NP úplnych problémov, strojového učenia, teórii hier a pod. Počas štúdia som sa viac stotožňoval práve s týmto táborom a snažil som sa pomôcť prípravou súťaže ProFIIT a trocha neskôr predmetu TEAP. Členovia tejto skupiny sa podielajú na predmetoch ako Maticové algoritmy, Tvorba efektívnych algoritmov a programov, Evolučné algoritmy, Umelá inteligencia a pod.

Počas leta medzi 4 a 5 ročníkom som bol vybratý na stáž Great Minds v IBM Research Zurich, kde som napísal svoj prvý vážnejší článok na medzinárodnú IEEE konferenciu ICDM 2010 a získal kopu zaujímavých skúseností a kontaktov. V poslednom roku som dokončil diplomovú prácu a článok ako výcuc z nej, ktorého prijatie na ICDM 2011 sa dozviem za pár mesiacov. V priebehu posledného ročníka som tiež podstúpil prijímací proces pre stáž v Google Zurich, na ktorú som práve v týchto dňoch nastúpil.

Nádskok a akýsi "image", ktorý som získal počas prvých 2 rokov školy a schopnosť predať sa, ktorú som vycibril v ročníku treťom mi pomoholi vo viacerých predmetoch a povinnostiach, vďaka čomu som štúdiu na FIIT ako takému nikdy nevenoval viac ako pár týždňov čistého času v rámci jedného semestra. Na väčšine predmetov sa dalo s vyučujúcimi rôzne dohodnúť keď videli, že učivo ovládam. Myslím si, že toto je dobrá stratégia na absolvovanie FIIT a vytvorí priestor aj na založenie firmy v neskorších ročníkoch, prípadne asi aj na prácu na full-time.

Dúfam, že sa mi podarilo ilustrovať jeden zo spôsobov, ako naložiť s 5 rokmi života počas štúdia na FIIT a dospieť k zaujímavému výsledku. Stretol som sa s ľudmi, ktorý si myslia, že takto je to možné len na Matfyze. Som rád, že sa mi podarilo ukázať, že je to hlavne o človeku. Chcel by som tiež poďakovať všetkým, s ktorými som sa na FIIT posunul dopredu.

Na záver som si dovolil stiahnuť 18 stránok zo sekcie Galéria študentov na www.fiit.stuba.sk, okrem pod-stránky s rozhovormi so študentami, pretože tieto rozhovory zväčša nadvezujú na úspech spomenutý v niektorej inej pod-stránke. Jednoduchým python skriptom som potom extrahoval zo surového html mená. V zásade ide o ľudí, ktorý sa nejakým spôsobom aktivizovali na fakulte (či už ako autori alebo supervisori úspešných článkov na IIT.SRC alebo ocenených záverečných prác, alebo ako súťažiaci v rôznych informatických súťažiach, od Cisco Olymp cez ACM SRC až po ACM ICPC). Niektoré veci ešte nie sú vyhodnotené pre tento školský rok a preto je poradie len približné ;-) Číslo v prvom stĺpci značí celkový počet výskytov daného mena.

16 Mária Bieliková
13 Michal Tvarožek
11 Daniel Švoňava
9 Michal Dobiš
8 Michal Barla
8 Michal Lohnický
7 Martin Labaj
6 Marek Tomša
6 Martin Adam
6 Richard Veselý
6 Vladimír Michalec
5 Jakub Šimko
5 Karol Rástočný
5 Marián Šimko
5 Michal Kompan
5 Márius Šajgalík
5 Peter Bartalos

Software Engineering at Google

noreply@blogger.com (supo) — Tue, 05 Jul 2011 20:43:00 +0000

For 2011 I wanted to try something new again and when I was approached by Google after the Google Code Jam 2011 (I just placed in top 500, nothing too special, but I got a t-shirt :-P) I agreed to start the interview process. After 2 technical interviews, I was offered a Software Engineering Intern position at the Google Zurich office, which I joyfully accepted. This is the first post about the experience, since I started just yesterday, on the 4th of July.

I will not be able to disclose any details of course, and will have to be super careful, because of how sensitive some information can be and how strict Google is about this.

In the one and half of a working day, I already managed to:

talk with about 50 people as I was testing the widely encouraged "butting into a conversation" at Google. Everywhere I butted in I was automatically included in the discussion, it really works :-)
taste food in every micro-kitchen (places around the office where you can make a coffee in a professional Italian machine, cornflakes with milk, bread with ham and vegies, find various fruits, sweets, drinks, sushi and other snacking items)
try dining a healthy vegetable salad (at least until a cook started grilling meat on the terrace :-D )
get instructed on how to use a professional coffee machine by two doctors and one professor, with the main speaker being Italian!

Sounds like a nice place to work so far? To top the cake, I was equipped by a cutting edge hardware to perform my work duties (PC and laptop that sum to 20GB of RAM, you can guess the rest ;-) ).

These days, I will be getting accustomed to the environment, play with MapReduce and brainstorming the final shape of the project I will be working on for the next 5+ months in the Place Page team within Google Maps.

Great Minds at IBM Research

noreply@blogger.com (supo) — Tue, 05 Jul 2011 19:43:00 +0000

For the sumer 2010, I was chosen to join the Great Minds programme for research-oriented computer science students, organized by IBM Research Laboratory in Zurich, Switzerland. This article is a small summary of my observations.

The environment and the atmosphere in the laboratory is a mixture of 2 seemingly un-compatible things:

commercial company optimizing all the processes, client cooperation and staff efforts to generate profit
academic institution seeking to produce cutting edge research results, where scientists work in small focused groups on the topics that or of interest to them

From my experience, the working time is divided between the work on a commercial project (either a self standing prototype, or on some "smart" part of a bigger IBM project) and the work on a research idea with possibly different team of people. The ratio of these two activities is of course different for different people, but in general it is ones responsibility to manage the time, to both meet the commercial project deadlines and to progress with researching, paper/patent writing etc.

I personally joined the group working on a business intelligence tool:

http://www.zurich.ibm.com/mcs/infoanalytics/marketing_sales.html

and I teamed up with a colleague from the Analytics group to write a paper about high-dimensional data visualization, that was accepted to ICDM 2010 (sub 20% acc. rate) and I presented it in Sydney in December:

http://www.computer.org/portal/web/csdl/doi/10.1109/ICDM.2010.71

All in all, I enjoyed the combination of having the freedom in choosing and pursuing research ideas while also being confronted with the real clients expecting a working tool and the overall context of commerce.

Ps:

I spoke about the experience from the perspective of finishing Master/Ing students at a local Computer Science conference, you can find the slides (albeit for some reason they got damaged by SlideShare and the presentation is in Slovak) here.

First team to win N games

noreply@blogger.com (supo) — Wed, 20 Apr 2011 18:10:00 +0000

This is just a quick post for "my" TEAP students who couldn't solve one problem and I promised to show some code (I normally don't do that ;-).

Problem
Two teams (A and B) are competing against each other. They proceed to play games in sequence until one of them wins exactly N times. This team is said to be the winner of the sequence.
We have the probability P of the team A winning a single game. Also there can never be a draw.
Given P and N, calculate the probability of A winning the game.

Solution
The simplest way to solve this is by recursion. We define a function that calculates the solution after A won a games and B won b games. I used Python to get the exact solution. Code:

def solve(a,b,N,P):
  #left something out here ;-) 
  return solve(a+1,b,N,P)*(P/Decimal(100)) + 
         solve(a,b+1,N,P)*(Decimal(1)-P/Decimal(100))

See how cool Python is? I believe that you can manage the rest of the solution on your own ;-)

Conversational style

noreply@blogger.com (supo) — Thu, 07 Apr 2011 18:09:00 +0000

The problem of using conversational style while communicating or publishing on the Internet is that if written down and consumed without the context of the given moment in time and environment, body language and relation to the writer, it often comes through as illiteracy bordering with rudeness.

Dynamic programming checklist

noreply@blogger.com (supo) — Mon, 04 Apr 2011 13:53:00 +0000

There are many articles that talk about this programming technique, but I have never seen complete and generic step by step tutorial on how to deal with Dynamic programming problems. So here I present mine suited to my personal taste, but you may still find it useful.

Analysis

Design the solution using a recursive function. Just use the first naive function that solves the problem. For this you should define:

arguments of the function, that wholly describe the problem you are trying to solve
recursive relation, that describes how the arguments are changed and fed to the recursive call of the function
trivial case, the set of arguments that represents an instance of your problem, that is trivial to solve (like maximum of single element set, or sum of the empty set of numbers etc.)

If the number of different sets of arguments is too big, you have to find a representation of your problem that reduces this number. Here you have to exploit properties of the problem and ask yourself, do I really need X to represent the problem? Are all the bits of X used in the computations that the function does? Try to throw most of the X away and maybe introduce other small 'helper' arguments if that helps. Here are some common ways to reduce the number of different arguments:

Isn't it enough to pass X modulo something?
What about only the first and last char/digit/number of X?
Or store the original problem in a global variable and pass only an index into it and maybe some other small argument Y.

Implementation

This simple step turns your ugly exponential recursive function into a neat polynomial one (or at least less ugly exponential one), trading the time for memory.

Implement that function as you designed it.
Introduce a global variable DP in which you will map already calculated results to corresponding arguments of the function.
Add a check at the start of your recursive function that searches for current arguments in DP. If the result has been already calculated for them, just return it.

This should be it, you are basically done. But there are times, when you are not quite there yet. What follows is:

Optimization

In some cases, recursion is too slow. Every call of the recursive function takes some time, the memory on the stack needs to be assigned and so on. In this case, it may help to transform your recursion into iteration.

In other cases, the recursive tree can be too deep, causing your stack to overflow. You can transform your solution to iteration, or if you are lazy like me, there is one other thing you can do. Try to find out, for which arguments the recursion tree is deep and for which shallow. Like for example your arguments are numbers up to one million and you find out that for high number inputs the recursion is more shallow than it is when dealing with lower numbers. What do you do? Just iterate from one million downwards and call the function on the numbers as you go!

Next, the memory requirements for the global cache variable can be just a little too big. In this case it helps to do a kind of a BFS instead of the DFS your recursive function uses naturally. It can be done by converting to iteration and then storing only a limited portion of the global variable in the memory. This case applies usually when the recursive function moves 'slowly' in some dimension. For example consider function like this, where y moves only in jumps of 1 and 2:

int f(int x,int y)
{
  if (DP[x][y].is_computed()) return DP[x][y];
  DP[x][y]=f(x+m,y+1)+f(x+n,y+2);
  return DP[x][y];
}

In this case, after converting to iteration, just 3 columns of the DP table are enough to be kept in the memory at the same time, regardless of the values of m and n.

Finally, there is one more trick I would like to discuss. In some problems, that are solvable by DP, sometimes one dimension of the state space is ridiculously big (like 10⁹). This is a dead giveaway of the technique so called Matrix Multiplication Boost (ok, I've just made the name up ;-) ). MMB is applicable in cases, where the transitions between states of the problem have linear properties. Then, you can embed the whole state space (without the big dimension) in a vector V. Next, encode the transitions in the form of a matrix M. If everything works fine, the solution of M * V is a vector, that describes the same space as V, except moved one step forward in terms of the big dimension mentioned before. Now, to move K steps forward, you can just calculate M^K * V. See it? Instead of having to iterate over whole K, you just rise M to the K^th power. Matrix exponentiation can be calculated in O(M³ * log(N) ) where N is the bigger dimension of M.

Gridder - Humongous spatial data visualization

noreply@blogger.com (supo) — Mon, 04 Apr 2011 01:49:00 +0000

I designed the Gridder algorithm as a part of my diploma thesis and I've been playing with it for some time now. I am trying to find datasets and use-cases for it, so if you get any ideas just leave a comment ;-)

102,000 worlds biggest cities, plotted as dots. Applied mild edge glow filter for kicks.

Without going into any sort of detail, the algorithm basically takes a set of spatial data points (coordinates + other data attributes) and creates a representation that:

allows visualization of data attributes in the spatial context
provides exploratory navigation
does so very fast ( pre-process: O(N log N), interaction: O(1) )

That may seem a bit confusing so let me present an example. Imagine you take all the Earths cities with population greater than 1000, which there are about 102,000. For each city, you obtain coordinates, name label and population count. What would you do if you wanted to visualize this dataset?

Well, if you just took those 102k points and plotted them as small dots to a 2D plane, you would get something like the plot above.

It might be an interesting picture, but it is clear that you can not visualize the individual cities, let alone their labels this way, at least on this level of abstraction or "zoom". Sure, things would appear cleaner once you zoomed all the way to a particular city. The thing is, how do you know where to zoom? With this example data, you know approximately where to zoom because you know the data. With Gridder, I want to visualize data that you have never seen hence I need to provide a way to explore the data and give the user as much useful information as I can, on multiple levels of abstraction or resolution.

Let's see an example of Gridder output for the above data at the given resolution combined with the satellite data visualization:

Gridder output with city attributes (see bellow)

Here we notice a couple of things:

general spatial characteristics (shape) of the data is preserved, especially for important (big) clusters
points are "normalized" to a relatively small number of rows and columns to reduce clutter and simplify interaction
grid intersections represent clusters of data, where for each cluster we see:

the name of the representing city (biggest in the cluster population wise)
population of the representing city (green circle)
total number of cities in the cluster (yellow circle)

Some more examples on this dataset (different resolutions and grid sizes):

The coast of Australia, New South Wales and Sydney (16x16)

Something more complex, lots of big cities
The coast of China and Taiwan (16x16)

World view at 8x8

This last example reveals 3 interesting things about the data, that I (due to my general ignorance) never realized:

The cluster of Europe is labeled Istanbul. I went to wikipedia and realized that in fact Istanbul is the 3rd most populated city in the world and hence takes the place of the representative.
The cluster of US southeast is labeled Havana. It is actually a tad bigger then Huston and a lot bigger than Atalanta and other big cities in this area.
The European yellow dot is huge, it actually is the biggest one on the map. We have a lot more cities per square km than say USA (I am too lazy to confirm with some independent data). Note that my data only contains cities above 1000 inhabitants, if we took even smaller settlements Europe might be even further ahead.

Last plot, with an overlay of the actual data points:

A part of Western Europe
Here the overlay lets you observe the difference
between the actual coordinates and Gridder approximation

MySql job failed to start

noreply@blogger.com (supo) — Thu, 31 Mar 2011 00:47:00 +0000

I've got this message from MySQL, after importing some data and building indexes. The DB stopped responding and hitting the

/etc/init.d/mysql restart

gave me the aforementioned very non-descriptive error. My problem was that the DB didn't have enough disk space for some temp files, so increasing that solved the problem.

Pizza box architecture

noreply@blogger.com (supo) — Sun, 27 Mar 2011 22:03:00 +0000

Some pics from a brainstorming for my fathers new project after the jump - notice how we simulated the startup atmosphere by drawing on the pizza box ;-)

SSL-HTTPs fails TortoiseHg

noreply@blogger.com (supo) — Mon, 21 Mar 2011 23:40:00 +0000

There is a quick and dirty hack that you can use to be able to access repositories behind self-signed SSL with Mercurial 1.1.7 and beyond. On Windows, edit the file:

PATHTO\TortoiseHg\hgrc.d\Paths.rc

to make it look like this:

[web]
cacerts=

ProFIIT finals under way

noreply@blogger.com (supo) — Sat, 19 Mar 2011 08:44:00 +0000

Future FIIT students fighting for the spotlight & problem setters prepping the judge solutions presentation and making sure everything runs smoothly...

Python multiprocessing utility

noreply@blogger.com (supo) — Thu, 17 Mar 2011 22:20:00 +0000

This article talks about a simple python command line utility that lets you run your existing programs in parallel, feeding them input and collecting their output to utilize the power of a multi-core processor.

Problem:
We have an Windows executable that reads some input (from stdin), performs a calculation based on this input and prints some output (to stdout). Since the computation for different inputs is independent, it makes sense to run this executable in multiple processes, each one processing their own input file and then in the end, we append all their results (note that you should include the input data in the output, to be able to reconstruct the "Question to the answer" ;-).

Solution:
Here you can find a python script that does the process management in a bit more clever way for you.
It takes 2 command line parameters, the input file and the output file. It then reads the input file line by line, assuming that each line holds single instance of the input parameters you want to feed to your executable (you can easily tweak this input behavior, just check the code and/or ask in comments).
The script is keeping track of the running processes (number of which you can set in the class constructor) and as soon as some process finishes, it takes the next input instance and spawns a new process, that gets the input instance to its stdin. The stdout of the process is mapped to a temporary file. The scripts creates the same number of temp. files as there are processes and it circulates the file handles in a way that prevents from 2 processing writing in a single file at a single moment.
Eventually the content of temp. files is collected in the desired output file and the temp. files are deleted.

What you need to know:

The process spawning is rather slow (couple of milliseconds), so you should make sure the individual computations take at least a couple of seconds to make the spawning time negligible.
Each instance is calculated in a separate process, so memory leaks should not cause a problem (process releases memory to OS once it finishes).
Include the input description in the output of the executable, so that you can map outputs to inputs (in other words, the output file doesn't contain the solutions in the same order as the inputs in the input file).

Let me know if you find this useful ;-)

import ctypes, subprocess, sys, time, os

class Manu:
  def __init__(self,app,numwork):
    self.SYNCHRONIZE=0x00100000
    self.INFINITE = -1
    self.numwork = numwork
    self.workers={}
    self.app=app

#######################################    
############# Timer stuff #############

  def start_timer(self):
    self.t=time.time()
  def get_time(self):
    return time.time()-self.t

#######################################    
############# File stuff  #############
  
  def init_files(self,out_file):
    self.out_file=out_file    
    self.free_files=set()
    self.taken_files={}
    for i in range(self.numwork):
      self.free_files.add(open("_proces_file"+str(i)+".tmp","w+"))    

  def free_file(self,proc_handle):
    self.free_files.add(self.taken_files[proc_handle])
    del self.taken_files[proc_handle]

  def close_files(self):
    for f in self.free_files:
      f.seek(0)
      s=f.read(1048576)
      while s!="":
        self.out_file.write(s)
        s=f.read(1048576)                
      f.close()

    self.out_file.close()
    for i in range(self.numwork):
      os.remove("_proces_file"+str(i)+".tmp")    
      

#######################################    
############# Process stuff ###########
  def print_status(self,solved_items):
    avg_yet=(self.get_time()/solved_items)
    print >> sys.stderr, "Solved item: %3d Time: %5ds End in: %5ds Exp. total: %5ds "%(solved_items,self.get_time(),(len(data)-solved_items)*avg_yet,len(data)*avg_yet)


  def work(self,data,out_file):
    print >> sys.stderr, "Work started for",len(data),"items"
    self.init_files(out_file)
    self.start_timer()
    solved_items=0

    for i,dat in enumerate(data):
      if len(self.workers) == self.numwork:
        self.get_finished()
        solved_items+=1
        self.print_status(solved_items)

      self.my_spawn(dat)
      
    while len(self.workers)>0:
      self.get_finished()
      solved_items+=1
      self.print_status(solved_items)
      
    
    print >> sys.stderr, "Finished. Total time:",self.get_time(),"Avg. time:",self.get_time()/len(data)
    self.close_files()


  def my_spawn(self,data):
    f=self.free_files.pop()
    p = subprocess.Popen([self.app], stdout=f, stdin=subprocess.PIPE, shell=False)    
    h = ctypes.windll.kernel32.OpenProcess(self.SYNCHRONIZE, False, p.pid)      
    p.stdin.write(data+"\n")

    self.taken_files[h]=f    
    self.workers[h]=p


  def get_finished(self):
    arrtype = ctypes.c_long * len(self.workers)
    handle_array = arrtype(*self.workers.keys())
    ret = ctypes.windll.kernel32.WaitForMultipleObjects(len(self.workers), handle_array, False, self.INFINITE)
    h = handle_array[ret]

    ctypes.windll.kernel32.CloseHandle(h)
    self.free_file(h)
    del self.workers[h]


#Example usage:
in_file=sys.argv[1]
data=[ x.strip() for x in open(in_file).readlines()]
out_file=sys.argv[2]
a=Manu(r"wrapper.exe",8)
a.work(data,open(out_file,"w"))

Octopus merge

noreply@blogger.com (supo) — Wed, 16 Mar 2011 18:25:00 +0000

Code merging session with miso @ my place. I really need 3 screens ;)

Monitor your server on the go

noreply@blogger.com (supo) — Sun, 13 Mar 2011 19:37:00 +0000

After finishing the VPS setup more or less successfully, I started looking into options of how to monitor what is happening with the machine when I am not at the PC. I downloaded ConnectBot to my HTC Desire HD and used it to connect to the machine. There I have installed htop to display various stats like CPU and RAM utilization and running processes interactively and in the real time. Few tips on how to work htop without a hardware keyboard on your phone:

swipe up/down on the left half of the screen to scroll the process list
swiping on the right side scrolls the whole terminal
swiping left/right switches between active terminals
activate the keyboard by pushing bottom right corner of the screen and type:

q to quit (or close the left sidebar)
emulating function keys is a bit harder - press the on-screen ctrl, then activate the keyboard and press a number key ( for e.g. to change the sorting order, press ctrl then 6 on the keyboard, then use the on-screen arrows to navigate up/down in the sidebar. Selected sorting criterion is confirmed with enter )

For more tips head on to the websites of the software I mentioned (check this for more keyboard shortcuts - awesome for the software keyboard), there is some more cool stuff waiting for you ;-) Here is a picture of how this setup looks on my 4.3 inch screen (together with my G9x for the size comparison):

Battle: Los Angeles

noreply@blogger.com (supo) — Sat, 12 Mar 2011 14:06:00 +0000

I read multiple complaints about the jerkiness of the camera in this one - and yes it was really like the blair-witch project, maybe even worse. But it was consistent with the situation and even though we sat close to the screen, it was watchable. If you have problem, just sit further...

The plot starts good but then it reaches a plateau in the part where it gets a little repetitive. The biggest bummer is again the poor strategic thinking on the alien part. There is no way a race capable of traveling between stars with an experience of conquering planets (there were hints, like the soldiers had surgically implanted weapons) allows to have a single point of failure in their strategy - however strong it might be.

Bottom line, although the plot is very simplistic and long-winded at times, the execution, effects and cast (Michelle Rodriguez baby!) save the day. I only recommend this movie to sci-fi/war movie fans.

Photo-walk at Slavín, Bratislava

noreply@blogger.com (supo) — Thu, 10 Mar 2011 11:43:00 +0000

Hi all,

yesterday we managed to escape from all the busy-ness and go to a place where I haven't been before, although it is in my home city. This place is called Slavín and it is memorial to soviet soldiers who died while fighting to free Slovakia from German oppression in April 1945. It is basically a mass grave with 6845 bodies.

Direct link to the gallery:

http://photos.manasupo.com/p417317495

Some notes about the shoot:

The setting sun gave us a nice warm look and shadows for some depth in pictures. I just added some more of that warmth in the post to make it even more evident. Also in some pictures, I desaturated the whole picture and then saturated some particular colors, to clean them up a bit (red railing, green trashcan).

Majority was shot with the Canon 100mm f2.8 macro and some wide angles. Surprisingly, the 4^th picture was shot with the Canon 50mm f1.4, which sometimes nails the focus for me, but sometimes starts back-focusing and I need to micro-adjust on the spot. The wide shots are done with my favorite Tokina 11-16mm f2.8.

From webhosting to VPS

noreply@blogger.com (supo) — Wed, 09 Mar 2011 02:07:00 +0000

Hi all,

I have started a migration of our startup-ish project from a basic webhosting at http://www.webfaction.com to a linode 512 account over at http://www.linode.com today, which is a VPS with root access and all the related perks. The project is Django based and uses MySQL as well as some C++.
I was really afraid of the configuration, but so far it is turning out quite easy, although I am a COMPLETE noob. The steps I took so far:

Use the one click StackScript - this installs essential components of your application stack, which is Apache with mod_wsgi, MySQL (other databases available too) and some other stuff
For database interface install phpmyadmin, which is immediately accessible when you point your browser to IP_of_your_linode/phpmyadmin
```
sudo apt-get install phpmyadmin
```

Note here, that the DB itself is configured by the StackScript, so in the install pick the option that doesn't reinstall the database

Added some helpful aliases to ~/.bash_aliases (this gets automatically loaded on relog, or by typing bash, also you may need to change paths):

alias memhttpd="ps -u $LOGNAME -o pid,rss,command | grep httpd | grep -v -e mpm | awk 'BEGIN {sum=0} {sum=sum+\$2} END {printf(\"%f MB\n\",sum/1024)}'"
alias memtotal="ps -u $LOGNAME h -o rss | grep -e mpm -v | (tr '\n' +; echo 0) | bc"
alias memtot="~/webapps/misc/mem/check_mem_console"
alias memcheck="ps -u $LOGNAME -o pid,etime,rss,command | grep -v -e mpm"
alias memcheckhttpd="ps -u $LOGNAME -o pid,etime,rss,command | grep httpd | grep -v -e mpm"
alias apache_restart="/etc/init.d/apache2 restart"

Configure your virtualhosts. It is generally known that you should not serve static content with Django, so you should pick a directory outside of the Django folder and create a virtualhost record for it in:
```
/etc/apache2/sites-available/yourwebsitename
```

Check general, subdomains, ...
Don't forget to restart Apache to see the changes in configuration. You can do so by using the apache_restart alias we registered one step above

I have started adding some more StackScripts, which allow me to simplify some tasks (like starting a django project). To keep things clean, I created a folder ~/stackscripts, where I just copy them. Then for each, I add a line to the end of my .bashrc:
```
. ~/stackscripts/scriptname
```
which includes them in. Just type bash in the command line and enjoy. Especially neat feature is that bash auto-completes functions defined in .bashrc and you can tab over them. Nice!
Now this is no longer chronological, but next tip is that if you install a library like OpenCV, that you intend to use with python, you will need to put the OpenCV/lib folder in the python path (sys.path). For this, I found that the easiest thing to do is to put a .pth file in a folder that already is in the python path and list folders you want to add each on a separate line. Then upon execution of python, these folders get added to sys.path by site.py.
... to be continue

Programátorské súťaže - návod

noreply@blogger.com (supo) — Tue, 08 Mar 2011 22:10:00 +0000

Programátorské súťaže sú v podstate druh športu, v ktorom si ľudia porovnávajú schopnosti s otatnými. Existuje veľa druhov programátorských súťaží, nás momentálne zaujímajú tie zamerané na algoritmy. Vo všeobecnosti v nich ide o to, že súťažiaci v limitovanom čase riešia presne definované a ohraničené problémy a na základe kvality svojho riešenia sú nakoniec zoradení.

Základné elementy programátorskej súťaže:

zadania - množina jasne definovaných úloh, ktoré sa počas súťaže programátori snažia vyriešiť
vyhodnocovač - stroj, ktorému súťažiaci posielajú svoje riešenia a on ich vyhodnocuje
pravidlá - definujú, akým spôsobom budú súťažiaci zoraďovaný vo výslednom poradí danej súťaže a čo majú povolené a zakázané na súťaži vyvádzať

Zadania

Základný princíp každej úlohy je vždy rovnaký. Ide o premenu nejakých vstupných dát na výstupné dáta. Každá úloha vždy, spravidla v tomto poradí, definuje:

Špecifikácia úlohy

Popis charakteru premeny vstupných dát na výstupné. Ak je úloha jednoduchá, nachádza sa tu presný popis čo má váš program so vstupnými dátami urobiť aby vypočítal prislúchajúci výstup. Príkladom takejto úlohy je napr. „Dvojicu čísiel na vstupe ščítajte a vypíšte na výstup“.

Náročnejšie úlohy môžu trebárs povedať, čo so vstupnými dátami treba urobiť, ale opíšu tento proces tak, že keby sme ho priamo implementovali do programu, mal by ten program nejaký problém. Napríklad by pre vstup daného rozsahu bežal niekoľko rokov, potreboval by 1 TB pamäte a pod.

Takéto v zásade nesprávne riešenie, ktoré nás napadne hneď po prečítaní riešenia je však často dobrý odrazový bod na ceste za dostatočne efektívnym riešením. Súťažiaci musí v tomto prípade nájsť spôsob, akým dosiahne ekvivalentnú transformáciu efektívnejšie.

V iných prípadoch je spôsob transformácie vstupu na výstup uplne skrytý a po prečítaní zadania netušíme, čo so vstupom robiť, aby sme dostali požadovaný výstup. Ani vtedy netreba hádzať flintu do žita. V týchto prípadoch odporúčam opätovne prečítať zadanie aspon zo 3 krát, či sme náhodou neprehliadli nejaký fakt, ktorý daný problém zjednodušuje dosť na to aby sme sa vedeli pohnúť dalej.

Ak sme v zadaní nič nenašli, pozrieme sa na vzorový vstup a skúsime na papier odkrokovať, čo by sa s ním malo diať aby sme dostali správny výsledok. A posledná finta, keď neviem vyriešiť nejaký príklad, uistím sa, že v danej súťaži nie je nejaký iný, lahší príklad. Veľmi často sa stáva, že človek sa zasekne na ťažšom príklade a potom nestihne doriešiť jednoduchšie. Keďže aj v TEAP súťažiach aj v MFF súťažiach rozhoduje v prvom rade počet vyriešených príkladov, takáto chyba vie drasticky ovplyvniť výsledné umiestnenie.

Vstup

Dáta v textovom formáte, ktoré budú poskytnuté vášmu programu, keď ho bude vyhodnocovať testovať. Váš program sa k nim dostane cez štandardný vstup, čo je inými slovami to isté, ako keby ste dáta čítali z klávesnice. Napr:

cin>>x
scanf("%d",&x)

Zadanie presne definuje ako budú dáta na vstupe organizované, aké informácie sa budú nachádzať na jednotlivých riadkoch vstupu a pod. Pokiaľ špecifikácia úlohy nepovie inak, môžete predpokladať, že vstupné dáta, ktoré dostane váš program od testovača budú presne spĺňať špecifikáciu zo zadania.

Z toho vyplíva, že je zbytočné aby ste kontrolovali, či bolo naozaj zadaných 5 čísiel a nie náhodou 6, alebo či dané čísla sú naozaj len kladné a nie je medzi nimi náhodou aj 0.

Výstup

Dáta, ktoré váš program musí vrátiť vyhodnocovaču. Predáte mu ich tak, že ich jednoducho vypíšete na štandardný výstup, čo je presne to isté ako keby ste ich vypisovali do konzoly. Napr:

cout<<x
print("%d",x)

Formát výstupných dát je tiež vždy presne daný v zadaní. Na to, aby boli výstupné dáta vášho programu uznané vyhodnocovačom za správne, musia presne kopírovať formát, ktorý je vysvetlený v zadaní. Takže keď budete mať na jednom riadku vypísať číslo X, značiace počet jabĺčok na strome, nebude výstup vášho programu vyzerať nejak nasledovne:

Jablcok na strome : X

ale jednoducho len

Je dôležité podotknúť, že nie je nutné, aby váš program načítal VŠETKY dáta, ktoré sa nachádzajú na vstupe a až potom začal písať dáta na výstup. Tieto dve činnosti sú nezávyslé a môžu byť realizované v ľubovolnom vzájomnom poradí. Napr:

cin>>x
cout<<x+x
cin>>y
cout<<y+y

je to isté ako

cin>>x
cin>>y
cout<<x+x
cout<<y+y

Vyhodnocovač

Ok, program je hotový, čo teraz? Aj MFF aj náš testovač fungujú v podstate rovnako. Prihlásite sa na webstránku, cez ktorú sa dajú vyhodnocovaču riešenia dopraviť, preklikáte sa v menu, vyznačíte zadanie, ktoré váš odovzdávaný program rieší a pripojíte zdrojový kód vášho programu.

Prvá vec čo sa stane s vaším programom je kontrola použitých knižníc a funkcií. V prípade, že je nájdené niečo, čo je v rozpore s pravidlami súťaže, vyhodnocovač vám vráti hlášku Security exception, prípadne náš TEAP-ácky dokonca aj niečo konkrétnejšie.

Ak je všetko v poriadku, vyhodnocovač váš program u seba skompiluje a spustí ho na svoje tajné testovacie vstupy, ku ktorým súťažiaci nemajú z pochopiteľných dôvodov priamy prístup. Ak váš program beží a beží a beží a vyhodnocovač sa rozhodne, že už beží pridlho, zastaví ho a vám sa na webstránke zobrazí odpoveď Time limit exceeded.

Druhou možnosťou je, že program počas svojho behu spraví nejakú nepovolenú operáciu, napríklad vydelí nulou alebo pristúpi do pamäte, ktorá mu nebola pridelená. Vtedy vyhodnocovač zahlási Runtime exception. Predpokladajme teda, že váš program sa sám štastne ukončil.

V takom prípade testovač zoberie výstup, ktorý sa vášmu programu podaril vyprodukovať a overí, či naozaj ide o správne riešenie danej úlohy. Ak sa mu zdá, že nie, dá to vedieť hláškou Wrong answer.

Ak sa mu zdá, že to je skoro ono, len sú tam navyše medzery, prípadne nejaká čiarka atď, poskytne vám hlášku Presentation error.

Poslednou možnosťou je hláška Accepted, po zhliadnutí tejto hlášky sa tešíte, pretože ste zadanie úspešne vyriešili a bol vám pripočítaný bod.

Pravidlá

Pred tým ako sa dáte do súťaženia, je dôležité si prejsť pravidlá danej súťaže. Okrem zoznamu zakázaných funkcií a knižníc a dĺžky trvania súťaže (v rádoch niekoľkých hodín), by ste v nich hlavne mali nájsť algoritmus zoraďovania súťažiacich.

U nás aj na MFF je toto rovnaké. Súťažiaci sú počas súťaže radený primárne podľa počtu vyriešených (Accepted) príkladov. Ak majú dvaja súťažiaci rovnaký počet príkladov, rozhoduje súčet časov, ktoré potrebovali na vyriešenie všetkých nimi úspešne vyriešených príkladov. Napríklad, ak som 10 minút od začiatku súťaže úspešne odovzdal príklad A a 50 minút nato príklad B, bude môj celkový čas 10+50=60. Ak Jožo vyriešil A za 20 minút, na B potreboval ďaľších 30 minút a C skúsil odovzdať ale dostal späť Wrong answer, bude v poradí danej súťaže nižšie ako ja, pretože jeho súčet časov je až 20+50=70. Z toho okrem iného vyplíva, že optimálna stratégia je riešit príklady v poradí od tých najlahších, ktoré budete mať hotové za krátky čas až po tie najťažšie.

Verím, že po zhliadnutí tohoto riešenia sa všetci prestanú báť a budú veselo súťažiť. :-)

http://ksp.sk/~acm/
https://profiit.fiit.stuba.sk/login.php