Category → cs

Jam-Packed Fun and Games

Did I say “fun”? That was short for function calls. Which are fun too, admittedly. Blah, I always go to such lengths to come up with snappy yet justified post titles and end up achieving neither.

One more complimentary breakfast later:

This is it.

Google Code Jam World Finals. [Google Code Jam 2015 name tag with my name and handle and country] Let me take a moment to reflect. Seriously. I do not know how I made it this far this year. I guess I might be a top-500-ish competitive programmer globally, maybe even top-150-ish, but definitely not top-25-ish. And Log Set, the hard problem that got me through Round 3, doesn’t seem like it plays to my forte particularly either. It’s a bit mathy, but the math bits aren’t the hard part; I think it’s largely implementation, with one psychological hurdle where you have to realize that, because of how few distinct integers there are in S′, you can efficiently solve the subset-sum instances you need to produce the lexicographically earliest answer. I’m actually kind of impressed I got that. It seems like the sort of hurdle I usually get stuck on. How did this happen?

Maybe randomness. Maybe I was just particularly clear-minded during the round and wrote less buggy code than usual, because I had no expectation of making it whatsoever and so could look at the contest detachedly (until midway through the contest I accidentally noticed that my rank was under 20, and even then I tried very very hard not to think about it, and it kind of worked).

But it happened, and now I’m here. Time to roll.

In some emails much earlier in the Code Jam logistical process, Google had asked for “requests for changes and/or additions” to the software that would be installed on our competition computers, and I had sent them a long list:

Hi,
Here are some things I’d like if they were installed, in decreasing order of priority:

  1. The Vim plugin syntastic ( https://github.com/scrooloose/syntastic )
  2. a Haskell compiler (probably Haskell Platform 2014.2.0.0 https://www.haskell.org/platform/ even though it’s a year old)
  3. the Haskell package hdevtools ( https://hackage.haskell.org/package/hdevtools ) so that the above two may be integrated
  4. (I don’t have enough Linux experience to name a specific thing to install, but command-line utilities that are the equivalent of pbcopy and pbpaste on Mac OS X, which allow me to redirect text into or out of the clipboard from the command line easily)
Of course, this is my first Code Jam and I don’t know how reasonable these requests are. Any nontrivial subset would be appreciated.

A*

Nope, still no meaningful post today. Instead here is a pretty diagram of the A* search algorithm (A-star in English, for my search crawler overlords). At least, I hope it is; I spent more time fiddling with the pretty colors than making sure the algorithm I implemented was actually A*. It looks right, though? In the background, red component measures traversed distance from start, (inverted) green component measures difference between the traversed distance plus heuristic distance and the theoretically optimal heuristic distance from the start, blue component measures heuristic distance to goal.

Phone

tl;dr: anybody want to add me on Line or tell/remind me about other phone chat apps? betaveros as always.

Wow, talk about uninspired post titles.

I got a new phone today. Or, well, it’s second-hand, actually. I try to make electronics last a long time, but I think this was justified given the state of my last phone’s screen:

old phone screen, with a visibly malfunctioning black patch

Besides, I’m going off to college and all. Anyway, the phone is pretty cool. It’s a slick shade of red, it came with a cover and everything, and it has one of those fancy 3x3-grid locks. How secure are those again?

Well, we could just find the answer on StackOverflow, but that’s boring.

Chi Banner

Okay, I think I’m figuring this out. When I make a filler post for the streak, it should be an unabashed filler post, so I can accumulate some of the blogging time I find each day to work on a serious post (and for doing the other important stuff I should be doing!) instead of wasting it right away. Life. I’m programming something for Dad involving a parser using Jison, and one of the tasks involved stuffing a custom lexer into the parser.

College Emails

(Frivolous blog content, posted as part of a daily posting streak I have openly committed to; standard disclaimers apply)

Out of boredom and curiosity, I graphed how many emails colleges sent me, excluding the colleges I actually applied to. I am being extremely polite and just calling them emails. I’ve wanted to make this for a long time, but it wasn’t until I saw this post about an email experiment on waxy.org/links that I understood which tools I could use to quantify my emails. (And then I actually made it and procrastinated posting it here for two months. If you look at my GitHub page or activity you might have seen it already, though. Oops.)

I don’t think the results were expected. Other than saying that, I leave the interpretation up to the reader because I’m on a tight blogging schedule. Cool? Cool.

Puzzle 46 / Fillomino [LITS + Extra Region + Walls + Anti-Walls + Inequality + Tapa + Masyu]

5:27 PM phenomist: do you use gridderface to make pretty puzzles?

5:52 PM phenomist: actually nvm excel is probably easier lol

Okay I’m sorry this is a horrible puzzle where the rules don’t make sense and I didn’t even get it testsolved. I just wanted an image to concisely demonstrate the capabilities of gridderface, my puzzle marking and creation program, for the project homepage, after somebody expressed interest in using the program to write a puzzle. Then I got tremendously carried away.

C/C++ to D

Some notes.

I’m assuming you want to use D largely, but not entirely, for competitive programming. That’s me right now.

Basics

Syntax is very similar. Function definitions, semicolon-terminated statements, variable declarations, and so on. You can declare int main() {...} or void main() {...} or something with arguments.

Basic types like bool and int and double are all there. Wonderfully, long is 64 bits. Instead of unsigned whatever, just prefix a u, e.g. uint.

Arithmetic operators and bit operators are all there too, including unsigned right shift >>>. Although ^ is still xor, D has exponentiation as ^^. Sadly, % is still same-sign remainder; there’s no true mod.

import std.stdio;

Casts look like cast(int) x;

Control Flow

if, while, for, do, and even switch all work as you’d expect, along with break and continue.

foreach is the nice addition though. Not only can you iterate over arrays and stuff, but range loops go like:

HOJ 226: CP (中)

This post was written in Traditional Mandarin Chinese for my fellow competitive programmers in Taiwan.

題目在這裡,HOJ 226

有關的題目出現於NPSC 2014 高中組決賽pD。

前置要求:treap (split, merge)跟在上面實作區段操作(請參考資訊枝幹)。

這裡沒有完整的解答code,因為AC是要用血汗換來的才值得 :-)

Treap

我討厭單字母l的變數名稱(跟1太像了。我沒有被這個雷過,這只是自己對自己程式碼可讀性的要求),所以我的子樹叫做lc(left child),rc(right child)。

struct Treap {
Treap * lc;
Treap * rc;
unsigned pri;
char val;
int size;
};
int size(Treap * a) { return a ? a->size : 0; }
void pull(Treap * a) {
if (a) a->size = 1 + size(a->lc) + size(a->rc);
}

[IOI 2014 Part 2] One Line to Solve Them All

I started trying to sleep at 9 the night before the contest, tossed and turned in bed until 10, then fell asleep and got up at 3:35 in the morning. Blah. At that point, I went to the bathroom and applied some chapstick before trying to go back to sleep until 6. After breakfast, I grabbed a few minutes of sleep on the bus to the convention center where our contest would be, then slept on a sofa outside the actual contest hall alongside most of the rest of our team as we waited for a very long time until it was okay for us to enter. Competitions really mess with one’s sleep schedule.

Then, much too soon, we could enter. Day 1 of the contest was about to start.

The laptops were as yesterday, although they were protected with a white screensaver that indicated my name and ID as well as a countdown to the start of the contest. I was glad to see that my mousepad and all my writing utensils had survived without me. Somebody had the sense of humor to project an online stopwatch with an animated bomb fuse onto the screens to indicate the remaining time, which, once again, there was a lot of.

I conferred briefly with Paul (TZW (alphaveros (?))) about vim settings for a bit, but there were still fifteen minutes left or so. I idly stretched, practiced typing my .vimrc on an imaginary keyboard, and watched as the US dude two tables to my left unplugged his laptop’s mouse and rearranged absolutely everything on his table using the surface under his chair as swap space. (Well, that was how I mentally described it at the time, pending further revelations. (hint hint))

Then it began.

[IOI 2014 Part 0] Waiting

Yes, I know day 1 of the contest already ended and is probably a more interesting topic to blog about, but I finished writing this last night just before the internet was cut off to quarantine the contestants from the leaders, who received the problems and began translating them. I didn’t know about this until it was too late, which is why I’ve been waiting since yesterday to post this.

To provide a counterpoint to the last post, one of the many, many advantages of entering an international competition is that you get to meet a lot more people you already know, so there’s less time spent being socially awkward. While waiting for stuff to happen, aside from all the expected time spent with the Taiwan team, I also talked to, played games with, and otherwise entertained a whole lot of people I already knew, including my schoolmates (no less than fourteen of them were volunteers) and some of the college students who had shepherded us around during olympiad training.

Which is a good thing, too, because there was a lot of waiting.

First I waited for my teammates; my parents had decided to take me to the hotel (Fullon Shenkeng) directly, since I had a lot of stuff, and I had arrived early. This took about an hour, after which we had lunch. Then I waited for the hotel to give us our room cards, which took about five hours, after which we had dinner. Finally, at night, I waited for the Codeforces system tests. Very nerve-wracking. But I’m getting ahead of myself.