Arterm's blog

By Arterm, history, 7 years ago, In English

Hello everyone!

Over last few years number of standard algorithms and structures (dfs, FFT, segment tree, suffix automaton, ... Gomory-Hu tree) didn't change much, at least in my perception. Most of fresh tasks require pure creativity (tasks on atcoder.jp being most prominent example) or unusual combination of well-known blocks. Some tasks are even pure combinatorics math problems (I'm a big fan of these).

But I think there still are room to bring some new "primitive" structures. Let's form a list of interesting stuff that are unpopular or unknown!

My first thoughts are palindromic tree and multipoint evaluation (computes values of polynomial of degree n in n points in time).

Full text and comments »

  • Vote: I like it
  • +204
  • Vote: I do not like it

By Arterm, history, 8 years ago, translation, In English

Hello everyone

I would like to invite you all to the March HackerEarth Clash starting in around 28 hours (link to register here, check your time zone here). The contest will last 24 hours.

There will be five algorithmic problems and one approximation (optimization) problem. Read the problems for details on partial scoring for easier subtasks. I tried to make this clash interesting and challenging for everyone. That's my first clash, so I hope I've chosen difficulty right =)

I would like to thank Lewin for all his help in testing, editing statements, and writing editorials, and belowthebelt for all his help with the round.

There will be prizes — t-shirts and Amazon gift cards.

Hope to see you all at the contest!

UPD: contest stars in 15 minutes!

Full text and comments »

  • Vote: I like it
  • +47
  • Vote: I do not like it

By Arterm, history, 8 years ago, In English

The 22-nd edition of Week of Code https://www.hackerrank.com/w22 starts soon: 8 August 07:00 UTC (note that the start time is unusual).

Monday to Sunday, every day one challenge will go live, easy to hard.

The maximal score decreases by 10% at the end of every 24 hours. Your submissions will run on hidden test cases at the end of every 24 hours.
Only the last submission time counts. It allows you to start late.

The contest is prepared by Arterm and tested by wanbo. Also thanks adamant for help in preparation.

The contest is rated and top 10 get T-shirts.

GL & HF

Full text and comments »

  • Vote: I like it
  • +89
  • Vote: I do not like it

By Arterm, 9 years ago, In English

Good day everyone.

Every programmer occasionally, when nobody's home, turns off the lights, pours a glass of scotch, puts on some light German electronica, and opens up a file on their computer. It's a different file for every programmer. Sometimes they wrote it, sometimes they found it and knew they had to save it. They read over the lines, and weep at their beauty, then the tears turn bitter as they remember the rest of the files and the inevitable collapse of all that is good and true in the world.
This file is Good Code. It has sensible and consistent names for functions and variables. It's concise. It doesn't do anything obviously stupid. It has never had to live in the wild, or answer to a sales team. It does exactly one, mundane, specific thing, and it does it well. It was written by a single person, and never touched by another. It reads like poetry written by someone over thirty.

(excerpt from http://www.stilldrinking.org/programming-sucks)

Do you have such code? For me it's code for binary power

long bin(long x, long a) {
   long y = 1;
   while (a) {
      if (a & 1)
         y = (y * x) % mod;
      x = (x * x) % mod;
      a >>= 1;
   }
   return y;
}  

and Gauss algorithms (the latter is longer than nine lines, so I don't post it here).

I'll be happy to see yours masterpieces!

Full text and comments »

  • Vote: I like it
  • +145
  • Vote: I do not like it