professorbrill's blog

By professorbrill, 11 years ago, In English

The problem is already stated in the topic name. I have KMP values and I need to recover Z function values and vice versa. Thank you!

Full text and comments »

  • Vote: I like it
  • -16
  • Vote: I do not like it

By professorbrill, 11 years ago, In English

Let's assume we have declared integer variables a and b somewhere in the program. The following pieces of code behave identically.

1.

a = 1;
b = 1;

2.

a = b = 1;

However, is there any C++ code convention (Google C++ Style Guide didn't give me an answer) that tells us in which way to write?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By professorbrill, 11 years ago, In English

It is a well-known task to answer whether a node is an ancestor to another one with time complexity O(n) for preprocessing and O(1) for a query.

Each time you enter the node in recursive function DFS, you increase the time counter by one and call it an "entrance" time, and after recursively processing its sons, you increase the time counter by one and call it an "exit" time. Here is the pseudocode.

DFS(u, p): // u is the current node, p is its parent
    increase the timer counter
    in[u] = timer
    for all (u, v) in edges:
        if v != p:
            DFS(v, u)
    increase the timer counter
    out[u] = timer

Now u is an ancestor of v .

Is there someway to implement the same algorithm but with non-recursive DFS?

Full text and comments »

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

By professorbrill, 11 years ago, In English

There is a line l given by the equation ax + by + c = 0 and the point P(x0, y0). Let Q(x1, y1) be projection of P on l. Am I right that ?

Full text and comments »

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

By professorbrill, 11 years ago, In English

I really liked the previous year's post on IOI participants so I decided to do the same for this year.

UPD: Colors updated

Name Country Codeforces Handle IOI 2012 Result
Albert Sahakyan Armenia albert96 No participation
Edgar Minasyan Armenia No participation
Edward Grigoryan Armenia edogrigqv2 No participation
Karen Hambardzumyan Armenia mahnerak No participation
Ishraq Huda Australia JoeyWheeler No participation
James Payor Australia jamespayor No participation
Michael Chen Australia rnsiehemt Bronze
Ray Li Australia AntiForest No participation
Adrian Goldwaser Australia 2 No participation
Austin Tankiang Australia 2 SpiritsUnite No participation
Joshua Lau Australia 2 junkbot Silver
Nicholas Laver Australia 2 No medal
Elmi Ahmadov Azerbaijan No medal
Rashid Gaziyev Azerbaijan No medal
Sanan Pashayev Azerbaijan No medal
Tahir Alizade Azerbaijan No medal
Bristy Sikder Bangladesh bristy1588 Bronze
Dhananjoy Biswas Bangladesh Corei13 Bronze
Hasib Al Muhaimin Bangladesh hasib No participation
Labib Rashid Bangladesh Labib666 No participation
Konstantin Sokol Belarus kostya_by No participation
Konstantin Vilchevski Belarus vilcheuski No participation
Sergey Kulik Belarus CherryTree Bronze
Vladislav Podtelkin Belarus vlad107 Silver
Floris Kint Belgium FKint Silver
Hannes Vandecasteele Belgium No medal
Simon Tihon Belgium No participation
Victor Lecomte Belgium vlecomte Bronze
Amer Zavlan Bosnia and Herzegovina charlieamer No participation
Armin Ašimović Bosnia and Herzegovina sleepmore No participation
Muhamed Parić Bosnia and Herzegovina No participation
Rijad Muminović Bosnia and Herzegovina rmumi No participation
Mateus Dantas Brazil MDantas No participation
Michel Zelazny Brazil michelzel No participation
Ramon Silva Brazil No participation
Renato Ferreira Brazil Renato_Ferreira Silver
Encho Mishinev Bulgaria Enchom No participation
Georgi Georgiev Bulgaria gogokefakefa No medal
Hristo Venev Bulgaria Silver
Momchil Peychev Bulgaria momo_vn No participation
Andy Huang Canada azneyes No participation
Angus Kong Canada No medal
Calvin Deng Canada dnkywin No participation
Yuanhao Wei Canada No participation
Haoran Xu China sillycross No participation
Kangning Wang China a142857a No participation
Lijie Chen China YuukaKazami No participation
Mingda Qiao China ACMonster No participation
Alan Navarro Colombia alan_navarro No medal
Diego Niquefa Colombia Bronze
Jaime Silva Colombia silvavelosa No medal
Sebastian Hoyos Colombia jshoyos No participation
Domagoj Ćevid Croatia Silver
Ivan Lazarić Croatia IvL No participation
Mislav Balunović Croatia mislav No participation
Mislav Bradač Croatia No participation
Aggelos Pelecanos Cyprus No participation
George Gabriel Cyprus No participation
Michalis Psalios Cyprus No medal
Panayiotis Panayiotou Cyprus No medal
Mark Karpilovskij Czech Republic shkarpa No participation
Martin Raszyk Czech Republic m.raszyk No participation
Ondřej Hlavatý Czech Republic No participation
Štěpán Šimsa Czech Republic simsa.st Bronze
Jakob Tejs Knudsen Denmark JakobTejs Bronze
Nikolaj Simling Kristensen Denmark No participation
Simon Hørup Eskildsen Denmark Sirupsen No medal
Svend Christian Svendsen Denmark svendcsvendsen Bronze
Ahmed Sherif Egypt No participation
Mohamed Essam Egypt mohamed.essam No participation
Omar Obeya Egypt aaaaAaaaaAaaaaAaaaaA No Medal
Yousef Salama Egypt Yousef_Salama Bronze
Andres Erbsen Estonia No medal
Jaan Toots Estonia No participation
Janno Veeorg Estonia No medal
Oliver-Matis Lill Estonia No participation
Henrik Lievonen Finland No participation
Kalle Luopajärvi Finland No participation
Sami Kalliomäki Finland No medal
David Saulpic France No participation
Hugo Manet France No participation
Jules Pondard France Bronze
Théophile Bastian France No participation
Giorgi Guliashvili Georgia guliashvili No participation
Jimmy Skhirtladze Georgia jskhirtladze Bronze
Nikoloz Svanidze Georgia svanidz1 Bronze
Tornike Mandzulashvili Georgia TMandzu No medal
Dimitrios Los Greece No medal
George Karagiaouris Greece Karaggeorge No participation
Giorgos Christoglou Greece Giorgos_Christoglou No participation
Panagiotis Kostopanagiotis Greece infinity No participation
Chun Yin Sampson Lee Hong Kong Sampson Bronze
Kam Chuen Tung Hong Kong alex20030190 No participation
Lik Hang Poon Hong Kong hohomu No participation
Pak Nam Hui Hong Kong LittleCow No participation
Akshat Boobna India No participation
Amartya Shankha Biswas India amartyashankha Bronze
Nihal Pednekar India nihalpi1 No participation
Nikhil Tadigoppula India 1nikhil9 No medal
Ammar Fathin Sabili Indonesia athin No participation
Jonathan Irvin Gunawan Indonesia jonathanirvings Bronze
Nathan Azaria Indonesia nathanajah Silver
Stefano Chiesa Indonesia zeulb No participation
Daniyal Mehrjerdi Iran dani1373 No participation
Farzad Abdolhosein Iran fab No participation
Keivan Alizadeh Vahid Iran keivan No participation
Seyed Hamed Valizadeh Iran havaliza Gold
Maciej Goszczycki Ireland No participation
Richard Tynan Ireland rptynan No participation
Daniel Hadas Israel Silver
Ohad Klein Israel No medal
Ron Ryvchin Israel No participation
Tom Kalvari Israel Silver
Davide Pallotti Italy davidepallotti No medal (Team 2)
Federico Glaudo Italy dario2994 Bronze
Gabriele Farina Italy obag No medal (Team 2)
Matteo Almanza Italy matteojug Bronze
Kohji Liu Japan hogloid Silver
Soh Kumabe Japan DEGwer No participation
Tsuyoki Kumazaki Japan wafrelka No participation
Yo Mitani Japan wo_ No participation
Aman Sariyev Kazakhstan Aman Silver
Meirambek Omyrzak Kazakhstan Meirambek No participation
Nurlan Zhussupov Kazakhstan NurlashKO No participation
Zhanadil Nurtoleuov Kazakhstan Zhanadil No participation
Bumsoo Park Korea zlzmsrhak Gold
Geunwoo Bae Korea Cauchy_Function No participation
Jeongwoo Ji Korea tonyjjw Silver
Seokhwan Choi Korea gs12117 No participation
Akylbek Tokon uulu Kyrgyzstan No participation
Alibek Taalaibek uulu Kyrgyzstan alibek_1 No medal
Azamatbek Akhmedov Kyrgyzstan Ahmedov No medal
Aleksejs Popovs Latvia popoffka Bronze
Aleksejs Zajakins Latvia Alex_2oo8 No participation
Mihails Smoļins Latvia No participation
Ojārs Vilmārs Ratnieks Latvia OVR Bronze
Daniel Talamas Mexico allthecode No participation
Diego Roque Mexico Diego9627 No participation
Edgar Santiago Mexico Garo9521 No medal
Saul Gutierrez Mexico sggutier Silver
Andrej Karadzic Montenegro No participation
Ilija Radosavovic Montenegro ilija123 No participation
Luka Bulatovic Montenegro MudoBog No medal
Bouke Van der Bijl Netherlands bvdbijl Bronze
Jorn Hoofwijk Netherlands No participation
Jorrit Dorrestijn Netherlands No participation
Koen Wolters Netherlands koensw No medal
Błażej Magnowski Poland No participation
Krzysztof Pszeniczny Poland No participation
Marek Sommer Poland mareksom No participation
Stanisław Dobrowolski Poland No participation
Afonso Santos Portugal No medal
David Gomes Portugal No participation
Pedro Silva Portugal No participation
Victor Meriqui Portugal No participation
Andrei Heidelbacher Romania andreihh No participation
Mihai Popa Romania mihaipopa12 No participation
Rares Buhai Romania rares.buhai Gold
Vlad Gavrila Romania VladGavrila Gold
Artur Ryazanov Russia tunyash No participation
Dmitry Gorbunov Russia malcolm No participation
Konstantin Semyonov Russia zemen No participation
Nikolay Kalinin Russia KAN No participation
Dimitrije Erdeljan Serbia No participation
Ivan Stošić Serbia ivan100sic Silver
Marko Baković Serbia Delta003 No participation
Marko Stanković Serbia MeinKraft No participation
Eduard Batmendijn Slovakia Baklazan Gold
Jakub Šafin Slovakia Xellos Bronze
Jaroslav Petrucha Slovakia No participation
Jozef Marko Slovakia jodik No participation
Janneman Gericke South Africa No participation
Paul le Roux South Africa No participation
Robert Spencer South Africa rspencer No medal
Shaylan Lalloo South Africa No participation
Anton Grensjö Sweden No medal
Aron Granberg Sweden No participation
Johan Sannemo Sweden jsannemo Bronze
Mårten Wiman Sweden Gullesnuffs Bronze
Aleksandar Abas Syria Alex7 No participation
Gaith Hallak Syria Gaith No participation
Hasan Jaddouh Syria kingofnumbers No participation
Hussain Karra Fallah Syria Pepe.Chess No participation
Han-Chung Wang Taiwan darkhh No participation
Hsin-Yuan Huang Taiwan Robert No participation
Kai-Chi Huang Taiwan step5 No participation
Li Chen Taiwan akaiNeko No participation
Abduqodir Qurbonzoda Tajikistan abdukodir No medal
Haitov Jamshed Tajikistan Jamik No medal
Turaev Mehrubon Tajikistan Ximera No participation
Umarov Doro Tajikistan Alnair No participation
Jirayu Luewetwanit Thailand Feu Bronze
Krittisak Chaiyakul Thailand toppykung No participation
Pichayut Liamthong Thailand pichayut No participation
Tossaporn Saengja Thailand App No participation
Feker Hassine Tunisia No participation
Malek Ben Romdhane Tunisia No participation
Meriem Chaabani Tunisia No participation
Mohamed Amine Hamza Tunisia No participation
Alperen Yakut Turkey ayakut No medal
Burak Bugrul Turkey burakbugrul No participation
Semih Basrik Turkey sbasrik No participation
Yusuf Hakan Kalayci Turkey t0nyukuk No medal
Ahmet Hudayberdiyev Turkmenistan turkmen No participation
Begmuhammet Kakabayev Turkmenistan Bega Bronze
Dovletgeldi Aydogdyyev Turkmenistan 1O1 No medal
Sylap Aliyev Turkmenistan accidentallygivenfuck No participation
Dmitry Fedoryaka Ukraine fedimser No participation
Ilya Shevchenko Ukraine Scorpy No participation
Roman Furko Ukraine Furko Bronze
Roman Rubanenko Ukraine Rubanenko Bronze
Andrew Carlotti United Kingdom Silver
James Clarke United Kingdom No participation
Saravanan Sathyanandha United Kingdom No participation
Toby Cathcart Burn United Kingdom No participation
Johnny Ho United States of America random.johnnyh Gold
Joshua Brakensiek United States of America AstroConjecture No participation
Scott Wu United States of America scott_wu Gold
Steven Hao United States of America stevenkplus No participation
Bui Do Hiep Vietnam hiepsieunhan No participation
Duong Thanh Dat Vietnam infrmtcs No participation
Le Xuan Manh Vietnam No participation
Nguyen Tuan Anh Vietnam con_nha_ngheo Silver

If you know any other countries' delegations, let me know in the comments. Thanks!

Full text and comments »

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

By professorbrill, 11 years ago, In English

Has anyone ever got problems because of forgetting to initialize a global variable?

And should I always initialize a variable when I create it?

P.S. I am talking about C++. Are the global variables initialized with "zero" by default? Or it depends on the compiler?

Full text and comments »

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

By professorbrill, 11 years ago, translation, In English
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#define MX 1000005
using namespace std;

struct BN
{
    int siz, num[MX];
    BN()
    {
        siz = 1;
        memset(num, 0, sizeof(num));
    }
    BN(string &a)
    {
        siz = a.size();
        memset(num, 0, sizeof(num));
        for (int i = 0; i < a.size(); i++)
            num[i] = a[a.size() - i - 1] - '0';
    }
    void len()
    {
        siz = MX - 1;
        while (siz > 0 && num[siz] == 0)
            siz--;
        siz++;
    }
    void inc()
    {
        num[0]++;
        for (int i = 0; i < MX - 1; i++)
        {
            num[i + 1] += num[i] / 10;
            num[i] %= 10;
        }
        len();
    }
    string tostring()
    {
        string a;
        for (int i = siz - 1; i >= 0; i--)
            a += (char)(num[i] + '0');
        return a;
    }
};

BN w;
string s, t, u, v, v1;

string sol()
{
    if (s.size() % 2 == 1)
    {
        u = s.substr(0, s.size() / 2 + 1);
        v = u;
        reverse(v.begin(), v.end());
        v = u + v.substr(1);
        if (v <= s)
        {
            w = BN(u);
            w.inc();
            u = w.tostring();
            v = u;
            reverse(v.begin(), v.end());
            v = u + v.substr(1);
        }
        u = s.substr(0, s.size() / 2);
        v1 = u;
        reverse(v1.begin(), v1.end());
        v1 = u + s[s.size() / 2] + v1;
        if (v1 <= s)
        {
            w = BN(u);
            w.inc();
            u = w.tostring();
            v1 = u;
            reverse(v1.begin(), v1.end());
            v1 = u + s[s.size() / 2] + v1;
        }
        if (v < v1)
            return v;
        return v1;
    }
    u = s.substr(0, s.size() / 2);
    v = u;
    reverse(v.begin(), v.end());
    v = u + v;
    if (v <= s)
    {
        w = BN(u);
        w.inc();
        u = w.tostring();
        v = u;
        reverse(v.begin(), v.end());
        v = u + v;
    }
    return v;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        t = sol();
        cout << t << "\n";
    }
}

Actually I do have a solution for this problem (maybe it is not correct but I didn't create a post for helping with solution). But I wonder why each time I call sol(), the program crashes and gives SIGSEGV.

Can anyone explain?

P.S. BN is a big number structure. Used it to increase a big number by one.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By professorbrill, 11 years ago, In English

Given a weighted digraph with weights either 0 or 1 find the shortest path. I heard that it can be solved using BFS and deque. But I don't really know how to prevent an vertex from appearing in the deque several times. Which condition on adding them to deque should I add? Thanks.

Full text and comments »

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