Challenge24 2015 writeup

Правка en3, от ArtDitel, 2015-07-02 11:01:38

Hi all, we participated in challenge24 as aimfund team (zeliboba, ArtDitel,Zhukov_Dmitry), took 6th place and here is my writeup. We really love challenge24 and 24-hour format, thank you guys for making it, and we are waiting for the next year. But I should say that writeup will be mostly negative because of overall impression.

UPD Psyho's 1st place writeup with solutions: http://codeforces.me/blog/entry/19023

 .

The first negative moment was not the fact of a postpone, but the unknowing of exact schedule and orgs silence. We think it happened because of sponsor issue.

Next strange stage was the onsite network test and team placement. There were no seating chart so we picked the random room with 3/5 russian teams. There were no test targets too, we had neither server ip nor checklist, the only thing we did was setting switch and checking power adapters.

At the contest day we came in the same room and waited for the start. It was really unexpected to find only 6 tasks in problemset, we thought more would come, but it didn't. By the way, submit interface didn't work for the first 2-3 hours.

A, D and E were pretty straightforward tasks and almost every team solved them. Tests for 'E' were broken, and it took 2-3 hours to fix them.

F task meant to be online game with all teams competing each other in 20 rounds. But what we found was: incomplete statement, it looked like someone forgot to include 2 or 3 pages, and offline server, which went online only after 6-10 hours of competition. Next 6-8 hours jury was trying to fix it and finally they changed literally the whole tasks 4 hours before the end! I think it was one of the worst moments of the contest. Last thing to mention is the scores, which appeared 3-4 hours after the round end.

C task was the best one, but it wasn't enough to save the contest. In this task you have assembly language with: in, out, mov, rmov, jmp, jz, jnz, jneg, add, sub, div, xor, mul. You were given assembly compiler, binary runner and 3 binaries (without asm code, so you should decompile or reverse them somehow) and the task was to optimize the size and run-time of these binaries. Sounds tasty. We started optimising first binary, because it had no input, only output. Overall idea was to optimize the algorithm and then make constant micro optimisations. For example in second binary you should implement the sorting algo.

But there was a problem too: the scoring system. You could spend hours writing good solution (nlogn head-sort or merge-sort), optimize initial binary by ten times and get... ONE point of 400. It happened because of strange formula and unknowing what input data is used by the jury. It is a big array or small? How many tests do they have? We implemented 4 different algorithms, combined them and got 50 points only.

# simple insertion sort
mov 0, array_ptr
read_loop:
  in 4
  jz 4, end
  rmov 4, *0

  mov 8, 0
  mov 12, 8
  sub 12, four
  swap_loop:
    mov 4, *12
    jz 4, swap_end
    sub 4, *8
    jneg 4, swap_go
    jmp swap_end
    swap_go:
      mov 4, *12
      mov 16, *8
      rmov 16, *12
      rmov 4, *8
      sub 12, four
      sub 8, four
  jmp swap_loop
  swap_end:
  add 0, four
jmp read_loop

end:
mov 0, array_ptr
print_loop:
  mov 4,*0
  jz 4, 0
  out 4
  add 0, four
jmp print_loop

four:
dw 4
array_ptr:
dw array
zero:
dw 0
array:

B task was the worst one. It's a task with a physical construction with a video stream of it. You controll the fan that moves around the field with ping-pong ball on it, and your target is to lead the ball into the hole. Your team have 16 attempts: 4 unrated, 4 without obstacles, 8 with them. One ball will cost you around 100 points, it's a difference between 4th, 5th and 6th places.

last rounds for task B

I think jury expected that someone will use video recognition but no one did. All teams just watched the video and played with a keyboard. And every team did almost the same thing every round, so the score was mostly the matter of luck and agility.

I understand how difficult it is to make such an event and I want to participate in the next ch24, so I hope that jury will look at this writeup and will try to avoid/overcome all mentioned issues in the future.

P.S. And thanks for massage, it's really great feature for such event ;) And here you can find photos

20 minutes of massage

Теги ch24, challenge24, 2015, writeup, budapest

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский ArtDitel 2015-07-02 11:01:38 92 Tiny change: 'ression.\n*UPD* Psyho's ' -> 'ression.\n\n**UPD** Psyho's '
en2 Английский ArtDitel 2015-07-01 11:50:33 66
en1 Английский ArtDitel 2015-07-01 11:46:38 4541 Initial revision (published)