kalimm's blog

By kalimm, history, 7 years ago, In English

I'm reaching out to you in the name of Inzva, the sanctuary of the Turkish hacker community.

We are an independent non-profit entity, with the support of Bev.Foundation and we provide a neutral umbrella for all Turkish hackers.

We had organized our first camp on September 16th-23rd 2017. It was an Algorithm Camp for university students with Vasyl Biletskyy who got ICPC gold medal in 2008 (https://icpc.baylor.edu/worldfinals/teams/2008) .

We are planning to organize the second advanced camp between January 26th — February 3rd*, friday to saturday (final contest will be helded at Saturday).

We need a coach for our next camp. We can provide with you flight tickets and hotel stay during camp days in Istanbul. Since we are an education foundation, we would invite professors, guides and coaches by their own will. Yet we have a budget of 300$ for the time being at Inzva.

  • This dates lies between semester break of several universities in İstanbul.

Full text and comments »

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

By kalimm, history, 7 years ago, In English

Hi,

Two days left for ACM-ICPC SEERC 2017. I wanted to know that does reference documents allowed. However when I checked the rules, it directs to "ICPC Regional Rules for 2017 Regionals" page and in "Regional Contest Computing Environment" part it says "Please see the specific regional rules at the ICPC Regional Contest Web Site".

So, anyone knows about it? Can we bring printed documents or flash drive to be printed? I know I shouldn't be writing this two day before the contest but I couldn't find the rules and I don't know why but I didn't send an e-mail to contest director.

Thanks for help.

Full text and comments »

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

By kalimm, history, 7 years ago, In English

First of all, for a long time I wanted to write this blog but I keep delaying it and finally here I am. After seeing matthew99's blog I decided to my time has come. I really wanted to write like him but my English skills aren't enough to use "you would" dozens of times. So I will explain how I didn't perform well in my life, and if you do same things you will end up succeed at failing in your life.

And it's very important to say at this point, I'm very bad at English, so if you're disgusted you can stop right there and I'm truly sorry about it.

TLDR : I am a loser.

I was a regular student before high school. I interested with math olympiads little bit but I didn't get even a national medal just a several contests. By the way I won a The New iPad. So I am passing that times and coming to high school.

In our country national eliminations goes like that, paper based elimination at may, national OI at december, team selection contest at march/april. High school is 4 years so we have a 3 chances to participate(At least we did have).

In first grade I didn't manage to pass first paper based elimination because I'm a dumbass. In second grade a passed first elimination and at national OI I got 18th degree and got last of bronze. Results are here.

On second problem of first day, the setter was more dumbass than me and lot after the contest we learned that checker was wrong. The problem was simply "Print the connected subset of nodes in a tree such that multiplication of values at nodes is maximum as possible. There can be negative ones." Greedy solutions failed, and dp solutions passed if it prints the lexicographically minimum one or something. Mine was greedy and I couldn't come up with an idea and spend all time on that stupid question.

On second problem of second day, even though I love the setter I can't avoid from these words, he was a dumbass too. We never heard checker or input files are wrong but, for to get 30 points you just need to print the maximum of an array but 5 people couldn't get that subtask done.

I wasn't good and lucky so I simply failed. Everyone told me not to prepare for team selection contest because they're 17 people better than me at OI and I have to pass at least 14 of them. enesoncu and EMINAYAR was have a IOI medal and ikbal was a god so I though I have no chance. But muratt intended to study for it and he was at a lower grade than me at my school and I can't except that he will be better than me :P We really supported each other and we had a great motivation(not beaten up by the other) so we really worked hard.

If you really want you can find problems written in English by ikbal here and results here.

Second problem of first day was a really easy sparse table problem. I finished it very fast as solutions is very obvious and simple. But I couldn't manage the get accepted like 3 hours and I did even change my N = (int)1e5 + 5 to N = 100005 because I couldn't find any single bug. I got other points and return this problem and nothing changed till the contest ends. After the contest I heard a really sad story.

Number of nodes is N <  = 105 but number of queries can be M = 2 * N at this problem. The setter was same person who creates "maximum multiplication of tree problem". He wrote N <  = 105 at constraints but I didn't think input size could be 2 times larger so couldn't manage to pass bigger subtask. It's an excuse and it was my fault but WHY WOULD ANYONE SPECIFY THE BOUND OF OUTPUT????? I can't even remember his name but still I can see him in my nightmares(There was a sentence like that on Game of Thrones so it was a sarcasm and I wanted to clarify it)

Anyway I got the 6th degree at first day I was happy because I did pass many people and I still have a chance. Second day I got 100 points from 3rd problem very fast and I was quite sure there won't be many 100 points so I started really believing I can go to IOI. 62 points from second problem was easy so after like 100 minutes I got 162 points.

Here's stupidity comes, after that I didn't go for first problem because it looks easy(or hard I really can't remember) and found a solution that includes mo's algorithm and trie for max xor at second problem and another stupid things(it was real solution anyway) but I didn't manage it to pass so I got like 30 minutes left at the very last of contest.

30 minutes and there was a problem I didn't even think about it. After reading problem a realized it's really easy to got 36 points and started coding for it. My solution was slow but here's the funny part. I didn't get TLE but got WA instead. I couldn't fix it and end up with 23 points.

Two more funny parts, the intended solution uses KD-tree but N <  = 25000 because of high constants and time limit was 5 seconds so O(N2) solutions did pass. Many hours after the contest I heard from a friend of mine, our rabbit can't jump in 4 directions, it can jump to right and up only. BTW the solution is same except two if's.

So even tough I did very well at contest(compared to myself), because of -50 in first day and -77 in second day I got 5th degree having a 2 points difference from 4th guy. Coaches tried to decide which one of us should get in team but after that they decided it was unfair to choose 5th guy even tough there's a really small difference, and they were right.

In our country if anyone gets a medal at internationals he/she will have a right to go any university in our country. If anyone couldn't get to team at 3rd grade they usually stop doing olympiads because they need to study for university. I was loving doing it so I couldn't let it go and I thought I still can get IOI medal next year and don't struggle with university exams shits.

At national OI I got 3rd degree, I couldn't manage to solve matrices and fibonacci problem but I was happy at my results. I didn't stop studying for anytime. Before team selection contest I was wanting get a good score on first day and feel comfortable at second day. At first day I got 300 points and I got really happy at contests.

After first day I learned they were 9 PEOPLE WITH 300 POINTS. Okay, it was easy but, WHAAAT? I got really angry because setters didn't manage any shits. At second day they write 4 hard problems.

As a spoiler I solved 3 of them and got 1st degree and solving 1 was enough to get into team. I solved one of them like 2 hours. After that I got accepted with brute force at one of the problems. Then I solved another one and there was like an 1 our left. After that they changed input data for "brute forced problem" and I got -80 at contest. I was really having a negative points at contest and I went to toilet and start punching walls because my life was depend on it and I have no choice other than IOI medal and I couldn't stand the chance of it.

I realised I need to calm down and managed it don't remember how. Changing inputs at the contest(at even 1 hours left) was really dishonest behavior. Okay my solution is wrong but I waited like 2 hours and they didn't announce anything, I stopped thinking about real solution and start dealing with 4rd problem that I have no clue. Because of that it wasn't fair I got really angry. Anyway somehow I found the real solution in a few minutes and coded it like 40 minute and got accepted.

After I got 100 points, I send a clarification request which contains the following message "You don't need to try to blow up my solutions, it's the intended one now". It was a foolish thing to do but I couldn't stop myself.

I was studying at my top performance till the IOI. Than the real shit has come, which isn't none of my fault this time. Coup d'état attempt happened in our country and they decide not to participate in international olympiads even tough there wasn't any single shit got wrong. It was my whole life and I did have nothing to do. It's just sad and if you don't live in garbage country you should be happy about it sometimes :(

TOBB University gives scholarship to students who haves a national medals. So it was my only chance and I got in there.

We participate at ACM-ICPC SEERC and got 6th degree. My teammates was very bad and I'm not hesitating saying it because they know it too and there isn't a chance that they see here :P Our score was good enough I think when we consider I'm the only one who write codes and deal with solutions. Anyway I got very sad after contest because we finished one problem 1 minute after contest(I submitted that code on Codeforces gym and it got accepted). After some weeks we learned that we are invited to World Finals. It was really shocking because something went good at my life for the first time. Anyway my team was useless and they didn't get visas even though they applied for 2 times.

I went finals with my coach. It was great to participating in it. I was the only Turkish person coming there. I was proud of myself. Anyway I always wanted to have a medal at World Finals even tough I didn't see anyone even participate at it. I wasn't that good for it and I didn't even have a team so there isn't a single chance for me.

They were 3 really easy problems and I finished them in 34 minutes as I remember. I got 12th degree as I remember. It was quite fast for my level and I got very motivated. I looked problem D and in a few minutes I thought it can be solved with divide and conquer optimization. Here's my stupitidy starts again. I didn't prove it but I was quite sure it will pass but instead coded TERNARY SEARCH. I don't have any idea why such thing happened :( Of course id didn't pass but even that time I didn't try D&C optimization. My performance isn't that bad still and I found the solution for problem A and started coding it. It was a geometry problem so I have bugs and got some WAs but it didn't stop. I couldn't manage the get AC. I thought I need a break and try to go for problem C. Solution was obvious but I thought flow was too hard for a problem that most of teams had solve. You idiot, it's WORLD FINALS, YOU ARE NO TOURIST, AND YOU ARE ALONE, AND IT'S JUST A FLOW.

How can anyone think such stupid thing? I really don't know and I hate myself most of times. After that I returned D and completed it in like 2 minutes.(Even that point I didn't code D&C but instead expand the limit of ternary search like while(r-l>1000) and it got accepted) In other minutes I didn't get anything done. After the contest so many people congratulate me even tough I messed up so bad. They don't know who I am, don't have to care about me, don't need to do kindness to me but even that case they treated me like a family. Volunteers, coaches, participants I'm really grateful to know people like you in my life.

At the ceremony Dr. Poucher announced a university and a guy and said that he was alone and we need to applause him. For the ones that was there, that guy was me. Supporting is the best feeling on earth and there're so few times a felt it. I wanted to thanks to anyone who care about me even tough for a second.

So that was my story. Moral of the story is don't be stupid and read problems at contest. BTW, I realized I forgot to mention, I did read geometry problem wrong on finals. I thought it says we connect two vertices but it said we connect any two points. Solution isn't much different just add a small case but I couldn't do it because I realized my wrong a lot after contests.

In a short time period I'm planning to write another long blog but if you hated this so much please let me know so I won't disturb you again in that case :)

Have a wonderful life.

Full text and comments »

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

By kalimm, history, 8 years ago, In English

Hi Codeforces,

Me(kalimm), muratakburak and OnurYildiz have a competitive programming team which name is LogicError in TOBB ETU.

Like a month ago, we participated at SEERC 2016. When there's just a minute before the contest finished, I completed writing problem A and submitted it. It gave a wrong answer because in one line I wrote "a[i]" instead of "b[i]". I changed it immediately but I wasn't be able to submit it because contest had finished. I downloaded code to my flash drive, hoping that somebody add this problem to Gym in Codeforces.

Thanks to Temirulan, he added SEERC 2016 to Gym, I submitted my code on Codeforces, and it passed. I got very sad because we got 6th place and lost 2th place because of one tiny bug, and chance of going ACM-ICPC Finals same time.

Two days ago I got an e-mail from "ICPC Manager", which named "IMPORTANT: Please certify your team." I didn't read it carefully and I thought it was just a "certificate" about 6th place. I was just about to delete it then I thought maybe I can use that certificate some time. I clicked to e-mail but there were no links, pictures, pdfs in there. I read the first sentence and got a little heart attack,

"CONGRATULATIONS! Your team, LogicError, has advanced to the 41st Annual ACM-ICPC World Finals sponsored by IBM and hosted by Excellence in Computer Programming, Inc. from May 20–25, 2017 in Rapid City, South Dakota, USA."

I stared at my phone like WTF IS GOING ON for five minutes. Then I realised we're going to ACM-ICPC Finals.

We will be the first Turkish team which is going to finals, so we're really happy about it. It's a great success for us. However here's the main part I want to learn. Why we are going to finals? As far as I know, top 3 teams are qualified for finals. It made a big surprise for us and made us really happy.

Thanks to whoever thinks "Let's top 6 team go to finals this year"!

Full text and comments »

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

By kalimm, history, 8 years ago, In English

You know there was some shit on Turkey, some times ago. https://en.m.wikipedia.org/wiki/2016_Turkish_coup_d%27%C3%A9tat_attempt

Because of that, we won't participate this year as a team. But some of us think we can participate without coach. Do you know any idea about it? Can we participate without coach? We send e-mail to IOI but we didn't get a reply yet.

Thanks for any idea.

Full text and comments »

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

By kalimm, history, 9 years ago, In English

Hi, I can't solve it for a long time. There are really short codes, but I can't get the main idea :( Thanks for help.

http://mirror.codeforces.com/contest/83/problem/E

Full text and comments »

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

By kalimm, history, 9 years ago, In English
set < int > s;
...
for(set < int > :: iterator it = s.begin(); it != s.end(); it++)
    doSomething();

What is the complexity of this code? Cost of it++ is O(1) or O(log(n)) or another complexity? Do you have any ideas about it?

Thanks for help.

Full text and comments »

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

By kalimm, history, 9 years ago, In English

What is the sum of number of divisors of divisors of number which is smaller than n, such that sum of number of divisors of divisors of this number is maximum?

For example,

g(n) = number of divisors of n

f(12) = g(1) + g(2) + g(3) + g(4) + g(6) + g(12)

f(12) = (1) + (2) + (2) + (3) + (4) + (6) = 18

Can you help about it?

Full text and comments »

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

By kalimm, history, 9 years ago, In English

What is the lenght of largest common subsequence of two round words? In a round word there is no difference from which symbol the word starts and in which direction it is read.

lcs("algorithm", "grammar") = "grma"

1≤N≤2000

http://izho.kz/uploads/izho_2013_en_inform.pdf

Do you have any solutions? Thanks for help.

Full text and comments »

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

By kalimm, 9 years ago, In English

Hi everyone! We just opened new hashtag on Twitter, named #IOIBuddies. Our goal is, sharing photos with another team. You can see our tweets from here.

Turkey — Mexico

Turkey — Colombia

Turkey — Azerbaijan

You can take a photo with another team, and you can post it on Twitter and share it from here if you want.

We really want to see your tweets!

Do you want to join?

Full text and comments »

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

By kalimm, 9 years ago, In English

You are given a sequence A of N positive integers. Let’s define “value of a splitting” the sequence to K blocks as a sum of maximums in each of K blocks. For given K find the minimal possible value of splittings.

1≤N≤100000, 1≤Kmin(N, 100)

http://izho.kz/2014/uploads/izho_day2_en_info.pdf

There are some solutions which is N * K * log(N), like monotonic queue + segment tree. But I'm not sure about this complexity works in 1 second.

Is there any better approach?

EDIT : Thank you ko_osaga for solution, and good explanation!

Here is the code.

Full text and comments »

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

By kalimm, 10 years ago, In English

Hi everyone! I want to share a very cute LIS(Longest Increasing Subsequence) implementation.

I found it on here.

Also thanks to mnbvmar for improve the implementation.

But this assumes no duplicates in array.

set < int > s;
set < int > :: iterator it;

...

FOR(i, 1, n)
{
    s.insert(a[i]);
    
    it = s.upper_bound(a[i]);

    if(it != s.end())
        s.erase(it);
}

cout << s.size() << endl;

So I changed it to multiset, for duplicate.

multiset < int > s;
multiset < int > :: iterator it;

...

FOR(i, 1, n)
{
    s.insert(a[i]);
    
    it = s.upper_bound(a[i]);
    
    if(it != s.end())
        s.erase(it);
}

cout << s.size() << endl;

There are seems work, and it's easy to proof them.

Thanks for your reading :)

UPD : I just found a similar approach for Longest Strictly Increasing Subsequence.

multiset < int > s;
multiset < int > :: iterator it;

...

FOR(i, 1, n)
{
    s.insert(a[i]);

    it = s.lower_bound(a[i]);

    it++;

    if(it != s.end())
        s.erase(it);
}

cout << s.size() << endl;

UPD2 : You can solve LMIS(LIS) and ELIS(LSIS) with this approach.

Full text and comments »

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

By kalimm, 10 years ago, In English

Hi everyone! I have a solution for 440A, and I want to share it.

FOR(i,1,n-1)
    {
        cin >> x;

        t^=x;
        t^=i;
    }

    t^=n;

    cout << t << endl;

The proof is,

x xor x = 0

Make xor to all elements in array, and make xor all number 1 to n. The value is our answer. Because if one number is xor twice, number doesn't change anything.

Sorry for my poor English...

Full text and comments »

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