### Rubanenko's blog

By Rubanenko, 4 years ago, ,

Recently I returned from the Workshop and wanna share my impressions.

The post will be divided into several parts depending on an aspect I am covering in it.

• +282

By Rubanenko, 4 years ago, ,

Few weeks ago there was yet another discussion about "omg why we wait for the rating updates so long!?!?!" in Russian version of CF. MikeMirzayanov said that there are several reasons:

1. cheaters are checked manually;
2. rounds are usually held in the evening and Mike spends some time to get home from the University;
3. sometimes his little daughter asks him to play with her and Mike can't refuse of course

After meh, MaximM and me read the third reason, we started to think what can be done about it. After a little thinking we came up with a solution that seemed to make contestants and Mike's daughter happy. The solution was a creation of browser extension that maintains rating changes of a current scoreboard whenever you refresh the result page. Something like this:

Luckily, CodeForces provided us with all the tools to make it happen: an API and a public implementation of the rating calculation method.

We had very little experience developing stuff like this, but we had strong desire to contribute to CodeForces. Eventually we had much fun and enjoyed the process a lot. At first, we couldn't make the extension work with large scoreboards (div2 or mixed rounds). The API couldn't serve too heavy requests about standings list. So we had to switch this process to the browser's background every time it's launched. So, actually, you have to wait around two minutes after you turned on the browser in order to let the extension download current ratings of all the users. Don't worry, it happens only once the browser has started. In other words, in the very worst situation the extension won't work for the first two minutes of a contest, in case you launched the browser just before the contest start.
When we were done with the routine described above, we noticed two things:

• it takes about 30 seconds to compute the rating change of 5k participants round. It was written in JS :)
• the rating changes it calculated were wrong!

Luckily, we could compare our implementation with the official one literally line-by-line. The issue was in type: official implementation used int, while we used...var. parseInt almost everywhere solved the problem, great :)
At this point we had right rating change calculation method, but it was very slow. Our team was quite upset, because we were sure that CF uses the fastest solution possible and we have no chance to speed it up. However, after a little thinking we noticed, that using int everywhere gives us a possibility to memorize some data. We ended up with O(min(N * K), N2 * log(N)) solution, with N being the number of contestants in a scoreboard, and K being the number of different integer rating values. In current situation K is about 3-4k, so our solution started to work about 20 times faster! Afterwards, we finished some small details and uploaded the extension to the Chrome Store.

Everybody is welcome to contribute to our Github repository.
Hope you love it!

UPD

Thank you all guys for your feedback. After the extensions attracted so much attention we have no choice but to do our best in order to make it better. We will make a lot of changes this week: fix bugs you reported, add requested features, switch to backend in order to decrease pressure on CF servers during the contest.
A special shoutout goes to people, who contributed to our repository. We are very grateful and will look at every pool request these days.
A big thanks to Mike Mirzayanov for being friendly, ready to collaborate and giving few pieces of advice.

• +647

By Rubanenko, 5 years ago, ,

CodeChef invites you to participate in the December Cook-off 2014.
Time: 21st December 2014 (2130 hrs) to 22nd December 2014 (0000 hrs). (IST — +5:30 GMT) — Check your timezone.

Details

Registration: Just need to have a CodeChef user id to participate.

New users can register here.

Problem Setter: Rubanenko

Problem Tester: tuananh93

Editorialist: elfus0

Mandarin Translator: xiaodao

It's my third CodeChef Cook-Off. The contest is quite balanced and I think that this contest will bring you something new and unusual. Don't be afraid of being creative! As always I'd love to hear from you after the competition is over.

Special thanks go vadimmm for discussing the problemset.

Don't forget that top ten contestants will receive CodeChef T-shirts!

UPD

Contest has started with some lagging and delays. I'm sorry for that and, unfortunately I could do nothing with it.

Strongest active ACM ICPC Belarus competitor kostya_by takes the lead! uwi has two penalty submissions in margin.

uwi submits the last problem from the first try and wins the contest!

dreamoon seemed to be trying to do the same as he does on codefoces these days, but the problems were too easy, so he didn't succeed and accidentally solved all of them. Congratulations!

By the way, it seems that I forgot to say that you should be not only creative, but attentive as well..:)

I'm sorry that the problemset was too easy for some contestants. Problem RRPLAYER turned out to be known and easy. As you will see from the editorials, I had more complicated(and I thought cool) solution. I'm really sorry and probably won't set public contests in future :(

• +75

By Rubanenko, 5 years ago, translation, ,

Hey guys! December Clash at HackerEarth is taking place this Saturday. The contest lasts for twelve(!) hours, so almost everyone can find a time slot to participate.

There are five tasks, four of them are standard algorithmic problems with partial solutions allowed, while the last one is an approximation problem which will allow to determine the best participant.

I think that this format of competition is interesting for everybody because newcomers can do better than stronger competitors with a help of "12-hours dedication" strategy, while the strongest guys will enjoy fighting each other on the approximation problem.

The complete problemset is prepared by laoriu. It was very exciting to work over the contest with him. You may know this guy from preparing the Codeforces Round #277 (Div. 2). I did the testing part for this contest and would like to say that I wouldn't be able to solve all the problems without laoriu's help. So I find the problemset pretty challenging and strongly recommend you to participate! I believe that both math_lovers and implementation_lovers will find something interesting for them.

Hope to see you at the scoreboard ;)

Rubanenko

Reminder!!!

UPD

As usually, top three contestants will receive HackerEarth T-shirts!

• +26

By Rubanenko, 5 years ago, ,

If you think you're a looser, you should read this story and calm down :) It probably won't be interesting for all the other people.

You probably remember 472D - Design Tutorial: Inverse the Problem from the 270th round.

It took me about twenty minutes to solve ABC. It wasn't fast, but enough to still have chances to do well. After reading and several minutes drawing I invented MST-based solution(most people seem to have the same) which was pretty easy to prove. I wanted to build MST and check whether I get the same distance matrix as given one. "One more step to beating Petr" I thought, and immediately started coding. I used Kruskal's algorithm to prove my solution, so it was quite natural to implement it. Constructing distance matrix was implemented by calling dfs() N times. Here the shit goes. I don't know why, but I accidentally implemented dfs() for dense graphs, i.e. the one that works O(N2), not O(M). So total complexity was O(N3) which obviously should get TLE.

I submitted my solution and got(surprise!!!) TLE. Do you think, this bug was easy to fix? Yeah, maybe... but not for me on that day!

1. "Hmmm... This Java... I was told not to use it for the contests million times. Hmm.. Creating and sorting 2000000 objects is probably too much. It would pass in c++...damn-damn...I could start thinking on E this moment... Ok, let's do minor optimizations and give it a try. It should be pretty close to get AC"

...doing minor optimizations...

1. "Damn!%^&*^ Ok, calm down... Switching to Java 7 can help(it really helps sometimes! :)"

...submitting & getting "unexpected" TLE...

2. "Ok...-150 points are not a big deal. There is still a lot of time... Probably they don't want O(N2 * log(N)) solution to pass. Ok, it will definitely pass in c++."

...rewriting solution to c++...

3. "ARE YOU KIDDING ME!??! I should have stay at home... Hm..wait, I can prove the same solution with Prim's algo. It will bring me straight to easy O(N2) code, girls, money and fame."

...thinking of implementation details...

4. "I better write it in lovely Intellij Idea + CHelper rather than in CodeBlocks. It shouldn't cause TLE, because they definitely have O(N2) Java solution with at least two times margin."

...coding...

5. "FUUUUCK!!! Is it even possible?!?! Ok, no time, just rewrite it to c++ and forget this task."

...coding...

6. "Pretests Passed(yeah, I managed to make cubicle solution to pass pretests in 1965 ms)."

Well, I wasn't really happy about it. It was 99.9% it will fail during system testing. And here, you know, the moment when something dawns on you and you see THE BUG. I implemented the last and right solution in Java and submitted it. Of course, I couldn't do it without a silly typo in implementing linked list and loosing even more time.

Afterwards I was emotionally exhausted and could do nothing but implement N * M / 64 solution for the last problem. Of course, I wasn't as successful in it as in making cubicle solution to pass pretests for problem D.

Thank you for your attention, be attentive and think about your mistakes first rather than "something wrong with this Java again!!!".

Bye!

• +143

By Rubanenko, 5 years ago, translation, ,

Hey guys,

I can't log in arena for last three days. Does everyone else have the same problem?

• +5

By Rubanenko, 5 years ago, ,

I've implemented a solution for the last contest's problem D which works correct but dramatically slow! It works more than ten minutes on my PC which seems to be quite slower than naive approach. I divide the data into blocks, and store cnt[] array in every block and a deque for maintaining update queries. I cut blocks sometimes, so I rebuild structure when the number of blocks is above 2 * initialNumberOfBlocks. Probably the problem is that I'm a Java noob, who knows :D

If you have a couple of minutes, please have a look at my code. I tried to make it readable... hope it is :)

Thanks!

UPD

After I fixed the but mentalist found, the program got ML. It's also quite strange because I didn't rely on garbage collector and create no more than 400 Blocks. Each Block has int cnt[100000] inside, so total memory usage should not be more than something about 40 mb, but it exceeds 256 mb on practice. Code

• +4

By Rubanenko, 6 years ago, ,

It seems corresponding thread was not created by anybody else...

How to solve 1000?

• +14

By Rubanenko, 6 years ago, translation, ,

CodeChef invites you to participate in the July Cook-off 2014.
Time: 20th July 2014 (2130 hrs) to 21st July 2014 (0000 hrs). (IST — +5:30 GMT) — Check your timezone.

Details

Registration: Just need to have a CodeChef user id to participate.

New users can register here.

Problem Setter: Rubanenko

Problem Tester: msh_shiplu

Russian Translator: Witalia

Editorialist: praveen123

Mandarin Translator: stzgd and xiaodao

It's my second CodeChef Cook-Off. I believe this round is more interesting than my first one and hope you'll enjoy it! I think almost every problem can be solved by almost everyone, so everybody has a chance to place in top ten and win a T-shirt from CodeChef.

Problem statements are dedicated to Ukrainian National Team at IOI — Scorpy, NegaTeef, seland and Omelyanenko. I had a pleasure to help them with preparing for the IOI and they invented a nice solution for one of the problems in this contest! I'd also like to thank vadimmm for discussing and sharing ideas about the problemset.

UPD Contest is starting in 15 minutes!

UPD I'm completely sorry for having this endless testing queue. Hope none of you is disappointed because of it.

As you will see from the editorials, every problem has at most 50-60 lines neat solution. I'd love to hear from you about your impressions, especially your solutions for RRDAG and RRTREE. I also wonder whether there exists O(N2) solution for RRFRNDS. During the setting process I tried to invent such solution, but eventually ended up with O(N3) solution with constant optimization.

• +40

By Rubanenko, 7 years ago, ,

In less than half an hour the third Round 3 will begin. Top 25 participants will go to London to compete in Wordl Final. I wish everybody good luck and interesting problems.