This script works for today’s SPOJ UI.

# A better mod_dirlisting for lighttpd

The default module is cool and fast, but i lacks some features like it doesn’t show the modes of the files, and not all tags are associated with class names which limits our usage in using an external css. So i made an attempt to add these to the default module.

as lighttpd runs based on a config file, you have to code the config file every-time or you can write a custom script with cmdline-args(for config) to do that for you, here’s mine

[link: https://gist.github.com/9b3e0a7daecdc0206305 ]

It starts a port scan from 9009 and searches for the available one to bind lighttpd, adds all known mimetypes(from python module) to the config, copies external css for mod_dirlisting. and of-course document root is current directory.

At first i tried to implement the features as mod_cgi – python using jinja which is obviously the easy way but unfortunately the mod_cgi – python is deadly slow, it decreased the speed from 360 requests / sec to 7 requests / sec. here’s my index.jinja2 and dir-generator.py.cgi

[link: https://gist.github.com/38d382872086e6bf154f]

For adding class names to the tags, we have to edit mod_dirlisting.c, system stat call will provide the modes of file.

[link: https://gist.github.com/bab0ae824bd526f17f0e]

If you want to test it on your computer, here’s my mod_dirlisting.c, and its git diff(just in case)

[mod_dirlisting.c: https://gist.github.com/f5fcf309c62beaae841b]

[git diff src/mod_dirlisting.c: https://gist.github.com/553cfd249bffef44369c]

[style.css: https://gist.github.com/6609af61d4fa2f1682fc] (most of it is from bootstrap.css)

screenshots:

# spoj main72 subset sum

the problem asks to compute sum of distinct subset sums of the given array of integers;

as the range of numbers in the array is 0 to 1000; and the size of arr is 100, we can assume that the number distinct values cannot be more than 1000*100, So complexity wise it is ok to compute all distinct subset sums. for which we can use a set.

https://gist.github.com/dfdad3667ba70be17e08

PS: i got tle for set but made it to ac by using unordered_set

# spoj ascdfib – Ascending Fibonacci Numbers

nice problem,

the usual algorithm works in C++ with counting sort. but if you want to make it in the python or to improve c++ speed, you have to use pisano number of 100000 which is 150000.

here’s my code

# spoj twends

easy dp problem.

# spoj IITWPC4I, Petya and Repairment of Roads

nice and easy graph problem,

the simple trick is to join all the milkman to a special extra node with 0 weighted edges. now we just have to find the minimum spanning tree for this new Graph.

# Generating nth Non-Fibonacci Number

**Fibonacci Sequence:**

1 1 2 3 5 8 13 21 ….

**Non-Fibonacci Sequence:**

4 6 7 9 10 11 12 14 15 16 17 18 19 20 …

Generating Non-Fibonacci Sequence is based on the fact that difference between adjacent Fibonacci numbers is also a Fibonacci number.

fibs[n] - fibs[n - 1] = fibs[n - 2]

So the number of Non-Fibonacci numbers between adjacent Fibonacci numbers is a Fibonacci Number

First of all lets find the sequence whose nth term is number of Non-Fibonacci Numbers between (n + 1)th fibonacci number and nth fibonacci number.

This sequence will look like: 0 0 0 1 2 4 7 12 …

lets crop that sequence to 0 0 1 2 4 7 12 …

this basically nth fibonacci number – 1, lets call this special sequence GAPS

now to find the nth fibonacci number one can easily do a linear search on the partial sum of the GAPS.

https://gist.github.com/9da4a824bb28efd7c6c8

for all practical values of n, linear search is better as nth of GAPS increases rapidly(nth term crosses 10**10 at 44th term itself), if there are lot of such queries then complexity wise a binary search would be better as GAPS is a non decreasing sequence.