Rubanenko's blog

By Rubanenko, 8 years ago, In English

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.

Full text and comments »

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

By Rubanenko, 8 years ago, In English

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 1k_trash, Maxim 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.

Link to install

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.

Full text and comments »

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

By Rubanenko, 9 years ago, In English

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: ddldyj237

Russian Translators: vadimmm & Rubanenko

Editorialist: fchirica

Mandarin Translator: MinakoKojima

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_love_AA 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 :(

Full text and comments »

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

By Rubanenko, 9 years ago, translation, In English

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!

Full text and comments »

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

By Rubanenko, 10 years ago, translation, In English

Hey guys,

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

Full text and comments »

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

By Rubanenko, 10 years ago, In English

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

Full text and comments »

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

By Rubanenko, 10 years ago, In English

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

How to solve 1000?

Full text and comments »

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

By Rubanenko, 10 years ago, translation, In English

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: PraveenDhinwa

Mandarin Translator: gediiiiiii and MinakoKojima

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 Omelianenko. 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.

Full text and comments »

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

By Rubanenko, 11 years ago, In English

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.

Full text and comments »

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