Spoj ORDERSET – CPP solution

Problem: http://www.spoj.com/problems/ORDERSET/

The problem can be very easily solved using std::set. The problem is that std::set would be slow for this problem.
One can solve it with a custom implementation of a balanced binary search tree. I used Treap.

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <set>
#include <algorithm>
typedef long Key;
typedef long Priority;

struct Treap;
Treap * root;
Treap * nil;

struct Treap {
    Key key;
    Priority priority;
    Treap * left;
    Treap * right;
    int size;
    Treap() : size(0) {};
    Treap(Key _key, Priority _priority) :
        key(_key), priority(_priority), left(nil), right(nil), size(1) {};
    Treap(Key _key, Priority _priority, int _size) :
        key(_key), priority(_priority), left(nil), right(nil), size(_size) {};

void print(Treap * node, int lvl, bool l) {
    if(node == nil) return;
    if (l) printf("Left, Key: %ld, Priority: %ld, Level: %d, Size: %dn", node->key, node->priority, lvl, node->size);
    if (!l) printf("Right, Key: %ld, Priority: %ld, Level: %d, Size: %dn", node->key, node->priority, lvl, node->size);
    print(node->left, lvl+1, 1);
    print(node->right, lvl+1, 0);

void updateSize(Treap * cur) {
    cur->size = cur->right->size + cur->left->size + 1;

void rotateRight(Treap * cur, Treap * leftChild) {
    cur->left = leftChild->right;
    leftChild->right = cur;

void rotateLeft(Treap * cur, Treap * rightChild) {
    cur->right = rightChild->left;
    rightChild->left = cur;

Treap * add(Treap * cur, Treap * node) {
    if (cur->key < node->key) {
        // go right
        Treap * rht = cur->right;
        if (rht == nil) {
            rht = node;
        } else {
            rht = add(rht, node);
            if (rht == nil) return nil;
        cur->right = rht;
        if (rht->priority > cur->priority) {
            // left rotation
            rotateLeft(cur, rht);
            return rht;
        return cur;
    } else if (cur->key > node->key) {
        // go left
        Treap * lft = cur->left;
        if (lft == nil) {
           lft = node;
        } else {
            lft = add(lft, node);
            if (lft == nil) return nil;
        cur->left = lft;
        if (lft->priority > cur->priority) {
            // right rotation
            rotateRight(cur, lft);
            return lft;
        return cur;
    } else {
        return cur;

void add(Key key) {
    Priority priority = rand();
    Treap * node = new Treap(key, priority);
    if (root == nil) {
        root = node;
    } else {
        root = add(root, node);

Treap * rem(Treap * cur, Key key) {
    if (cur == nil) return nil;
    if (cur->key == key) {
        if (cur->left == nil && cur->right == nil) {
            // destroy
            delete cur;
            return nil;
        } else if (cur->left == nil || cur->right->priority > cur->left->priority) {
            // rotate left
            Treap * rht = cur->right;
            rotateLeft(cur, rht);
            rht->left = rem(cur, key);
            cur = rht;
        } else {
            // rotate right
            Treap * lft = cur->left;
            rotateRight(cur, lft);
            lft->right = rem(cur, key);
            cur = lft;
    } else if (cur->key > key) {
        cur->left = rem(cur->left, key);
    } else {
        cur->right = rem(cur->right, key);
    return cur;

void rem(Key key) {
    root = rem(root, key);

Treap * kth(Treap * cur, int k) {
    if (cur == nil) {
        return nil;
    //printf("~%dn", k);
    int tmp = cur->left->size + 1;
    if (tmp == k) {
        return cur;
    } else if ( tmp < k) {
       // printf("right %dn", k-tmp);
        return kth(cur->right, k - tmp);
    } else {
        //printf("left %dn", k);
        return kth(cur->left, k);

int cnt(Treap * cur, Key key) {
    if (cur == nil) return 0;
    if (cur->key == key) {
        return cur->left->size;
    } else if (cur->key < key) {
        return cur->left->size + 1 + cnt(cur->right, key);
    } else {
        return cnt(cur->left, key);

void test(Treap * cur) {
    if (cur == nil) return;
    int sz = 1 + cur->left->size + cur->right->size;
    if (sz != cur->size) {
        printf("SIZE ERRORn");
    if (cur->left->priority > cur->priority) {
        printf("LEFT PRIORITY ERRORn");
    if (cur->right->priority > cur->priority) {
        printf("RIGHT PRIORITY ERRORn");
    if (cur->right != nil && cur->right->key < cur->key) {
        printf("RIGHT KEY ERRORn");
    if (cur->left != nil && cur->left->key > cur->key) {
        printf("LEFT KEY ERRORn");

std::set<int> ss;

void test() {
    if (root->size != ss.size()) {
        printf("SET SIZE ERRORn");

void gen() {
    using namespace std;
    FILE * out = fopen("orderset.test", "w+");
    FILE * ans = fopen("orderset.ans", "w+");
    int n = 50000;
    fprintf(out, "%dn", n);
    set<int> ss;
    set<int>::iterator it;
    for (int i = 0; i < n; ++i) {
        int op = rand()%100;
        if (op >= 0 && op < 15) {
            // delete
            if (ss.size() > 0) {
                it = ss.begin();
                advance(it, rand()%(ss.size()-1));
                int key = *it;
                fprintf(out, "D %dn", key);
            } else {
        } else if (op >= 15 && op < 60) {
            // insert
            int key = rand();
            fprintf(out, "I %dn", key);
        } else if (op >= 60 && op < 85) {
            // count
            int key = rand();
            fprintf(out, "C %dn", key);
            it = ss.lower_bound(key);
            fprintf(ans, "%dn", distance(ss.begin(),it));
        } else {
            // kth
            int num = rand() % (ss.size() + rand()%50) + 1;
            fprintf(out, "K %dn", num);
            if (num > ss.size()) {
                fprintf(ans, "invalidn");
            } else {
                it = ss.begin();
                num -= 1;
                advance(it, num);
                fprintf(ans, "%dn", *it);

//#define DEBUG

int main() {
    #ifdef DEBUG
    return 0;
    nil = new Treap();
    root = nil;
    int q;
    scanf("%d", &q);
    while (q--) {
        char ch[2];
        Key key;
        scanf("%s%ld", ch, &key);
        if (ch[0] == 'I') {
            //print(root, 0, 0);
        } else if (ch[0] == 'D') {
        } else if (ch[0] == 'C') {
            printf("%dn", cnt(root, key));
        } else if (ch[0] == 'K') {
            if (key > root->size) {
            } else {
                printf("%ldn", kth(root, key)->key);
        //print(root, 0, 0);
    return 0;

Spoj DSUBSEQ – CPP solution

Problem: http://www.spoj.com/problems/DSUBSEQ/

Say that so far you have generated so far N strings totally without using the letter A. Then you append the letter A and you generate N+N strings. Later, when you add the letter A again, you would like to know how many strings have been generated using the letter A. Obviously, if you add the letter A to those strings, you won’t get distinct.
Keep the number of totally string generated so far and the number of strings generated by using some letter. Later, when adding some letter (say K), then the strings you would generate is (TOTAL – NUM OF STRINGS GENERATED USING K).
Just update the invariant correctly.

#include <cstdio>

typedef long long ll;
#define MOD 1000000007LL
ll arr[30];
char str[100001];

inline ll mod(ll num) {
    num %= MOD;
    if (num < 0LL) num += MOD;
    return num;

int main() {
    int t;
    while (t--) {
        scanf("%s", str);
        int i = 0;
        ll sum = 1LL;
        while (str[i]) {
            ll tmp = mod(sum-arr[str[i]-'A']);
            arr[str[i]-'A'] = mod(arr[str[i]-'A']+tmp);
            sum = mod(sum+tmp);
        //sum = mod(sum+1LL);
        for (int i = 0; i < 30; i++) arr[i] = 0LL;
        printf("%lldn", sum);
    return 0;

OpenGL Instanced rendering example

You can read about it at many places. Probably the red book and http://ogldev.atspace.co.uk/www/tutorial33/tutorial33.html are one of the best sources. However, there is a lot of information in the red book and the example which is given is not too clear. You just see something rendered and you may have not cover transformations yet or you do not know how to load some model from some file.
In Ogldev you have to read a lot of other tutorials to get aquainted what happens and the tutorial mostly modifies previously written code (the one about loading models with Assimp).
Also, it may be a bit hard to follow since a lot of other stuff is happening as well like texture mapping, etc.

#include <glm/vec3.hpp>
#include <glm/vec4.hpp>
#include <glm/mat4x4.hpp>
#include <glm/gtc/matrix_transform.hpp>
#include <iostream>
#include <GL/glew.h>
#include <GL/freeglut.h>
#include <GL/glut.h>
#include <GL/gl.h>
#include "../common/Shader.hpp"
#include "../common/ShaderProgram.hpp"
using namespace glm;
using namespace std;

    checks whether there are errors and prints them
void checkForOpenglErrors() {
    GLenum glErr;
    while ((glErr = glGetError()) != GL_NO_ERROR) {
        std::cerr << "OpenGL error: " << glErr << std::endl;

    vertices of a pyramid
GLfloat vertices[] = {

    indices to represent all of the faces (triangles) of the pyramid
GLushort indices[] = {

    colors for each pyramid instance rendered
GLfloat colors[] = {

/* Vertex array */
GLuint VAO;

/* Buffers bind to vertex array */
#define NUM_BUFFERS 4
GLuint buffers[NUM_BUFFERS];

/* Locations of buffers in array */
#define INDEX_BUFFER 1
#define COLOR_BUFFER 2
#define TRANS_BUFFER 3

/* Locations of attributes in vertex shader */
#define COLOR_ATTR_LOC 1
#define TRANS_ATTR_LOC 2

void init() {
    /* create aand use shader program */
    ShaderProgram program = ShaderProgram(Shader("shader.vert", GL_VERTEX_SHADER),
     Shader("shader.frag", GL_FRAGMENT_SHADER));

    /* generate the needed vertex array so that we can use later when rendering */
    glGenVertexArrays(1, &VAO);

    /* generate buffers needed for the pyramid */
    glGenBuffers(NUM_BUFFERS, buffers);

    /* buffer to store vertices */
    glBindBuffer(GL_ARRAY_BUFFER, buffers[POSITION_BUFFER]);
    glBufferData(GL_ARRAY_BUFFER, sizeof(vertices), vertices, GL_STATIC_DRAW);
    glVertexAttribPointer(POSITION_ATTR_LOC, 3, GL_FLOAT, GL_FALSE, 0, 0);

    /* index buffer */
    glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(indices), indices, GL_STATIC_DRAW);

    /* buffer for the colors of each pyramid */
    glBindBuffer(GL_ARRAY_BUFFER, buffers[COLOR_BUFFER]);
    glBufferData(GL_ARRAY_BUFFER, sizeof(colors), colors, GL_STATIC_DRAW);
    glVertexAttribPointer(COLOR_ATTR_LOC, 3, GL_FLOAT, GL_FALSE, 0, 0);
    // set change per instance -> every instance will have a new entry from the array buffer
    glVertexAttribDivisor(COLOR_ATTR_LOC, 1);

        create just translate transformations for each pyramid -> 3 pyramids
    mat4 transf[] = {
        translate(mat4(1.0f), vec3(-4.0f, -3.0f, -14.0f)),
        translate(mat4(1.0f), vec3(3.0f, -1.0f, -17.0f)),
        translate(mat4(1.0f), vec3(2.0f, -2.0f, -9.0f))
    glBindBuffer(GL_ARRAY_BUFFER, buffers[TRANS_BUFFER]);
    glBufferData(GL_ARRAY_BUFFER, sizeof(transf), transf, GL_STATIC_DRAW);

        set the attrib location and enable it. since we have a 4x4 matrix we have
        4 columns of vectors of length 4.
    for (int i = 0; i < 4; ++i) {
        glVertexAttribPointer(TRANS_ATTR_LOC+i, 4, GL_FLOAT, GL_FALSE, sizeof(mat4), (GLvoid *)(i*sizeof(vec4)));
        glVertexAttribDivisor(TRANS_ATTR_LOC+i, 1);

    // done with VAO
    // unbind

        create projection transformation and update the uniform
    GLint projectionLoc = glGetUniformLocation(program.getProgram(), "projection");
    mat4 projection = perspective(45.0f, 4.0f / 3.0f, 0.1f, 100.0f);
    glUniformMatrix4fv(projectionLoc, 1, GL_FALSE, &projection[0][0]);

void display() {


    /* bind and draw */

    /* sizeof(indices) / sizeof(GLushort) will return number of elements in the array */
    glDrawElementsInstanced(GL_TRIANGLES, sizeof(indices) / sizeof(GLushort), GL_UNSIGNED_SHORT, NULL, 3);



int main(int argc, char ** argv)

    glutInit(&argc, argv);
    glutInitWindowSize(512, 512);
    glutInitContextVersion(4,3); // freeglut required

    if (glewInit()) {
        cerr << "Problem initializing glew" << endl;




    return 0;

Vertex shader:

#version 430 core

layout (location = 0) in vec3 position;

// per-instance attribute
layout (location = 1) in vec3 color;

// per-instance transformation
layout (location = 2) in mat4 trans;

uniform mat4 projection;

out vec4 col;

void main() {
    gl_Position = projection * trans * vec4(position, 1.0f);
    col = vec4(color, 1.0f);

Fragment shader

#version 430 core

in vec4 col;
out vec4 color;

void main() {
    color = col;

HC-05 Bluetooth Module Windows 7 problems

If you have bought an Arduino bluetooth module (or whatever other device) and it uses the HC-05 chip, then you will probably have a problem establishing a connection with your computer. You will first establish it and shortly the connection will break.
This is because of the Windows 7 bluetooth drivers. I had some serious problems fixing this issue and there were a lot of people having the same issue.
So what is the solution: just install other bluetooth drivers or just install another OS like Ubuntu (it runs flawlessly ).

Хотел Данубе (Силистра) – как да се циганееш

Е, ето ни, отиваме на национална олимпиада по физика в Силистра. Сред множеството оферти за хотел, ръководителите ни избраха Хотел Данубе, тъй като предлага НА ПРЪВ ПОГЛЕД невероятни условия на добри цени (5 звезден хотел все пак – чи как). Тръгнахме всички с добри очаквания за идните дни – една приятна олимпиада, приятно градче и хубав хотел – какво повече му трябва на един състезател. Е, не обаче – трябваше да бъдем съсипани с цигании и опити за минаване тънко от страна на хотела.
1) Първата цигания:
След пристигането ни посрещнаха със следните думи: “Оказва се, че няма места в някои стаи, защото има промени”. Забележете: стаите са запазени от 17 дена и никой не ни е уведомил за такива промени. Какви са причините за нашето неудобство: “В хотела са настанени участници от еди-си-коя партия от Кърджали и щели да имат ВАЖНО СЪБИРАНЕ НА ПАРТИЯТА”. Е, разбрани хора са, смилиха се едва ли не и почнаха да ни търсят удобна, приятна стая, в която ние да се починем от изморителния път за предстоящата олимпиада. Настаниха ни в четворна стая, в която бяха наши познати от Варна (може би предварително трябваше да кажа, че сме 2-ма участници от 1ЕГ). Е, обаче стаята съвсем не беше четворна – по-скоро за семейство с 2 деца, които да се поберат на едно малко общо легло. А ние 18 годишни младежи какво да сторим? Да се тъпчим през нощта? Е, циганията им не се получи и накрая ни настаниха в отделна двойна стая (каквато беше запазена преди 17 дена). Каква милост…
2) “Тъй като ползвате намаление, не можете да ползвате СПА услугите на хотела – басейн, фитнес, сауна, джакузи.”. Забележете, че нормалната цена за 1 човек е 70 лв, а нашето намаление е 60 лв. Същевременно хотелът е пълен само защото над 100 човека от олимпиадата в това число ученици, учители, организатори са гости на хотела. За мен намалението се обосновава на бройката, а не на липсата на услуги. Добре де, все нещо трябва да се измисли. Ще платим като трябва. 10 лв щяло да струва на човек всичко. Очевидно е, че се връщаме на първоначалната (НЕНАМАЛЕНА) цена, но не, не било същото. Така се оказва, че ние можем да ползваме тези услуги само до края на деня, а не докато сме гости на хотела (примерно утре до 12 часа). Служителите се оказаха идиоти – никой не схвана простата идея за дискриминацията, която правят.
3) На самата страница са заявили, че предлагат висококачествен интернет. Вече се бях уверил, че гледат да минат тънко и да измамят клиентите си (очевидно не гледат в дългосрочен план на бизнеса си, а гледат сега да направя яката печалба – 10 лв). Но какво му е високоскоростното на интернета не разбрах. Той поне да не прекъсваше, супер щеше да е. Оказва се, че управителят го е ограничил на 2 мегабита, което е 256 кб/с (мега бавно по каквито и да е стандарти).
4) Не спазваха никакви графици. Казва се, че има засекретяване на работите на участниците в 18:30 и затова трябва да почне вечерята в 17:30, но не: те се забавят с един час и самите организатори (т.е. проверяващите) трябва да забавят засекретяването с още един час, защото ресторантът към хотела се бави. От друга страна сервирането беше уникално бавно и имах чувството, че има едва ли не една сервитьорка.
5) В момента на писането на този блог пост няма топла вода и ще трябва да изчакам сигурно до сутринта.
5 звезди, ама друг път. Според отношение не заслужават повече от 3, а според услугите едва ли повече 4, но и толкова им е много. И не съм единственият недоволен разбира се. Днес бях във фоайето да ползвам по-добра интернет връзка и постоянно идваха учители да се карат с управата на хотела – кой за фактури, кой за някакви други проблеми. Явно откъм много страни хотелът ОЧЕВИДНО НЕ СТРУВА!

Скорошно завръщане

Не съм писал в блога от ужасно много време, но причините са много. Реших да кандидатствам за щатите, реших да участвам в най-различни мероприятия като олимпиади и конференции. Съвсем скоро ми свършват изпитите и смятам да напиша няколко поста за това как са минали и как да се готвим за тях. На практика при писането на следващия ми пост вече ще ми минали изпитите – SAT MATH LEVEL 1 (730 точки), SAT MATH LEVEL 2 (800 точки), SAT 1 (не са излезли), SAT PHYSICS (текущо не е държан), SAT GERMAN (текущо не е държан), SAT KOREAN (текущо не е държан). След тях при добро представяне на SAT 1 ще имам да се готвя само за тойфел, но реших да държа и SAT CHEMISTRY + можеби SAT US HISTORY. Пред последните 5 месеца ми се случиха супер интересните неща и се запознах с още по-интересните хора. Този пост може да остане незабелязан или пък неоценен по повод, че е безсъдържателен, но този пост има и друга цел – да си систематизирам целите и в случай, че срещна трудност или забравя нещо, да си припомня какво гоня. В допълнение това лято реших да се явя на доброволческа работа в Англия. Който проявява интерес, нека послети http://www.rspb.org.uk/volunteering/residential.aspx . Отделно реших да наблегна на физиката и догодина най-вероятно ще се метна на олимпиадите и състезания по физика. Лятото ще работя и по един мой проект за speech recognition, към който известно време проявявам някакъв интерес. Първо щеше да е по-скоро някакъв визуален recognition-ър, но прецених, че този ще е по-удачен. Това е от мен.

За парите

Много хора смятат, че парите не са важни (повечето недорасли), други пък смятат, че всичко е пари.
Истината е, че и двата типа мисления са верни донякъде. Ще започна с твърдението, че “парите не са важни”.
Всъщност без пари животът на един човек би бил ужасен. “Парите не са важни” най-вече произлиза от устата, на хора, които или са бедни и искат да заблудят изстрадалото си съзнание, че причината да са нещастни не се крие в бедността, или деца, които са свикнали да получават прилични сумички от своите родители, деца, които не познават какво е работа, деца, чиято всяка една прищявка е задоволена.

Всъщност се оказва, че парите са изключително важни! Парите са това, което обличате, пиете, спите и ядете. Без пари вие бихте живели в гадно жилище, бихте носили стари дрехи, бихте пили евтини напитки (ако дори можете и напитки да си позволите), бихте се лишавали от основни храни, нужни за вашето тяло.

Сега трябва да се разгледа и твърдението, че “всичко е пари“.

Както по-горе написах много от нещата по света се въртят около парите, но те не са всичко. Парите всъщност не могат да ви направят истински щастливи, но биха могли да ви съпроводят към щастието. Като се замислете с пари можете да обиколите света, можете да карате хубава кола, хубаво жилище, но пак няма да сте щастлив, защото ще е трудно да намерите човек до себе си, който да ви обича, а не използва.

Като заключение смея да кажа, че парите са много, но не всичко. :)

Нищо конкретно 22.04.2011

Поредната публикация от поредицата “Нищо конкретно”.
Преди известно време почнах да се занимавам с Java и по-точно писане на приложения за Android. Засега съм все още начинаещ, но нещата не са много сложни и вече почнах да пиша мои по-простички приложения като можеби ще се позаинтересувам и от правенето на игри за android. Не съм сигурен дали ще почна да разработвам и за iOS. Ще почна и да правя серия уроци за Android (видео можеби), в която ще покажа основни похвати, а нататък ще сте вие :) Наскоро разработих и система за онлайн магазин с базови възможности, която се намира на адрес parfyumi.eu.
Краят на учебната година предстои и се очакват тежки контролни.
Като заключение: Весели празници!

След весело прекарване на празниците отново с много ангажименти

За много години на всички познати!
Весело си прекарах през цялата зимна ваканция! В общи линии си починах добре!
Очакват се доста ангажименти поне до към края Април като работа с клиенти и подготвяне за 3-4 състезания. На ~21 Януари ще има състезания по информатика C/C++. След това почвам да работя по един проект за клиент и след това почвам по проекта за 2те състезания по уеб програмиране – националното по информационни системи в категория Уеб Приложения и Webloz. Дочувам, че имало и някакво състезания в Монтана, по-късно във Варна. Ще се ходи тази година предполагам. По информатика ще съм в B група. Не съм много добре подготвен, но ако отида на областен това ще е успех за мен!

Нищо конкретно 09.12.2010

Нямам нищо конкретно за писане, но все пак реших да постна нещо, тъй като от известно време нищо не бях писал. :)
Засега сайтът 369.bg върви добре, а догодина смятам да участвам с един проект, който разработвам в момента, на състезанията по програмиране пък каквото стане. За 369.bg бях писал мой framework (не специално за сайта, но той е една от причините). Сега направих разни промени, което според мен го прави още по-хубав.
Разни хора почнаха да ми пишат/звънят за изработка на онлайн магазини, сайтове и разни подобни неща и след като ме питат “можеш ли това, можеш ли онова?” и съответно им кажа “да” и съответно след няколко минути ми казват, че ме пишат, ако излезе нещо, ще ми звънат и т.н. Общо взето нищо конкретно :) Скоро идват празници, което означава няколко неща за мен – сняг, коледна ваканция (няма училище), повече свободно време за приятели и писане на код 😀
Поне за момента не се сещам друго какво да споделя. Вероятно ще има и още публикации с име “Нищо конкретно”.