Spoj Solution Downloader

This script works for today’s SPOJ UI.

https://gist.github.com/a6936dcf504997e49f8b

Advertisements

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:

Screenshot_2015-11-15-09-55-20

Screenshot from 2015-11-15 09:41:22 Screenshot from 2015-11-15 09:54:20

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

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.