Rubanenko's blog

By Rubanenko, 4 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.

Read more »

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

By Rubanenko, 4 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 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.

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.

Read more »

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

By Rubanenko, 4 years ago, translation, In English,

There was a discussion, where I promissed to write this blog. My intention was supported by the community by a number of upvotes. I really loved to see that some people want to hear from me, despite of the pretty personal subject and absence of any previous well-written blogs.

Disclaimer
I would like to say that I strongly appreciate what people at Yandex do, their help for CP and I personally know some super smart and nice people that work/worked there.
They are free to hold the interviews as they like it and hire whoever they want. I am ok to think that I am far from perfect candidate. Here I'm just sharing my vision and experience. I am aware that after posting this I will never work at Yandex(YOLO). I also think that it's ok to use a couple of hot words towards impolite and somehow unprofessional people.

If you don't feel like reading a lot, you can go straight to the interview part.

Introduction
The things that made me apply to Yandex probably deserve a separate post and they are even more personal that this one, but I will try to cut long story short. I was 19-years first-year ITMO student. It was April and at that time I was pretty sure that I won't be "second-year ITMO student". The people at ITMO are quite loyal — they give you plenty of opportunities for exam retake, if you have been to WF, PTZ Camp, or playing video games. The point is that I somehow lost the flow of study. I haven't ever really had one, so I used to concentrate only on the things I enjoy, and you know it was a bad place for such an attitude. It was very hard to make myself to write some Physics shity sheets or count 50 integrals to gain 1% of my Calculus year mark. It would be pretty useful even just in terms of self-discipline, but I failed. In spring I couldn't even concentrate on problem solving. If I turn back the time, I would do the things in different way from the very beginning, but...)
I have never told anybody of my family or non-university friends about the troubles I have. So you understand how bad I didn't want to come home and say "Here I am, I've just dropped out!". It was always on my mind and, you know, it feels terrible. However, being on the bottom eventually helped me to catch the flow of doing something again.
As you can see, I didn't want to come home and I liked Saint-Petersburg as well. I thought finding a job there would be cool, because then I could concentrate on something new and challenging. As you might guess — I applied for Yandex internships! Of course I had a very small experience in anything despite of the problem solving, but I thought I can learn fast with everyday practice at the internship, and I can write some code in the end of the day. I wouldn't expect much more than a motivation at first when I offer 300$/month(it turned out that they do). So I thought they will take me as soon as they see I am not a complete dumb and then, after a couple of months, make a decision according to my learning speed and dedication.

Pre-Interview
After I filled in a short form and attached my CV they send me a letter. The a HR had nickname in her mail account. It was something like firstName nickname lastName. You don't expect something like nicknames when you have official mailing with adults. I wouldn't even mention it, but the funny thing is that nickname == "Sosa". For those of you who don't know Russian it sounds like some "Emma "sucky/sucko" Brown" has just mailed you about your internship to Google. It was really weird, man, but at that time I tried to keep myself damn serious. I just want to say that I would not pick such(or any) nickname in case I had to do any business talks from this account
She sent me a link to yandex.contest testing tasks. I was really glad to see this, since it meant a pretty standard way of work for me. I think I won't break the NDA if I say a couple of words in general about the tasks. Oh wait, there was no NDA. One of the tasks is pretty standard CP task, another one was just about big implementation routine with a little space to make a design decision that made the solution about three times shorter. The last task was quite natural in it's statement, so I googled it. I found a tool that can handle it, submitted — WA. Tried another tool — WA again. Ok, let it be. There were about 15 hotshots among of around few hundreds guys, who solved all the three problems, so I was confident that 2/3 is enough to get to the onsite interview. They said I should implement my solutions in C++ or Java. I decided to use Java for the first problem and C++ for another one just to show that I can. I had like two weeks to complete the tasks and the point is that they asked me to use Java for the implementation routine that I have already solved in C++ when it was a day or two to the deadline. Wait, what?! Why the fuck you asked to use C++ or Java, and now ask for Java only?! I had the third task undone, so I invested my time in solving it, rather than rewriting the problem I already have accepted.
Eventually, they invited me to the interview. Yay!

Interview
Before a couple of days before the interview the girl with the funny nickname brought two news for me. The first one said that she is not able to attend the interview and she will be replaced with another girl without any nickname. I didn't really care. However, later I will regret the substitute, because it seems that anybody would be better than the girl without a nickname. The second notification was far worse — it said that they don't have a vacant place for me, so even if I turn out to be Linus fucking Torvalds they won't hire me. Do I have to say how it affected my motivation? Anyway, I accepted the invite to the interview in order to get some experience and all.
One of my good friends vadimmm helped me to get to the office and supported me during the entire period. He spent more than an hour waiting for me, so I had somebody to go to the pub with, right after all the crap I am going to tell you about has happened. The girl was not alone — some guy(I think he was a developer) was with her. We sat down and started a conversation.
I thought that everything will start from walking over my CV and asking about my experience. Then it would be nice to discuss the tasks I was given two weeks before and my solutions. But scenario was quite different:

Guy: what do you do?
Me: I like programming competitions, have spent a while doing it. Now I want to get some production experience and try all this stuff.
Guy: what do you know about CS?
Me: well, all these competitions are a good place for practice a lot of classic algorithms and data structures. Of course, there are always a lot of to learn, but I believe that I am quite skilled in this field comparing to an average developer.
Guy: (he was smiling and wondering like he is about to hack me and put me down to my real place) what books have you read, son?
Me: "Book1", CLRS, "Book2", "Book3", some of Knuth's AoP.
Guy: (the bastard was smiling and about to laugh a bit. he was also looking at the girl and talking to her despite of the fact that I was answering or something) Knuth? Oh, really?!
Me: Yeah, when I was like in 9-10 grade, I wanted to learn DS and took CLRS along with AoP home from my teacher. The data structures turned out to be explained better in CLRS as for kid, but the first part of AoP was pretty useful in number theory, summations and some cool estimations/bounds. Of course I didn't bother to solve a lot of exercises, but anyway.
Guy: ok-ok, got it. (he said it in such a phony way, like my words were a complete it was kind of rocket science — to take the book and work over material that does not require much math)
Me: (man, I was damn angry with this CS-boss. however, I was quite calm, since I was quite confident that I will be able to solve almost every problem I will be given from him. instead of asking questions to verify my words he simply stopped talking and was looking like he doesn't believe me)
Girl: (yeah, the girl remembered that she should be paid for something) Why do you come here being a freshman?
Me: I have already said that I want some new experience. Summer is coming, so it will be like a lot of spare time and all.
Girl: (WA2, she's about to make another attempt) Do you go to the CS-Centre? (it's some lectures Yandex is helping to provide in SPb. dunno about their quality. I guess it's ok.)
Me: No, I don't. Should I?
Girl: Of course!(like it's the only way). There a lot of cool stuff, blah-blah...
Me: Thanks a lot, but in case I have a lot of time and effort I can concentrate on my University program, the teachers are quite nice, so I don't think it's necessary for our students to go to your centre.
Girl: you are wrong, blah-blah.
Me: Ok
// Still no a single word neither about my previous experience according to the CV nor about the tasks I was given before.
//You think it's time for some cool problems, or at least classic questions about data structures to verify my words above? No, it's time for Java and C++ exam!!!
The first part was about some classic OOP questions. Frankly, I wasn't kinda hotshot in it, or something. I failed on one easy question which was like
Guy: should we solve it in a way A, or in a way B?
Me: I don't really like any of these, but let it be B.
Guy: Lol, it should be C, actually.
There also was something like:
Me: (explaining the right solution)
Guy: how is this approach called?
Me: dunno, it's probably called "common sense"
Guy: bad-bad... (like knowing the word is better than coming up with the approach)
Whenever he had to tell me that I am wrong, he turned his head to the girl and was like not saying it to me directly, but discussing the mistake with her. What a man...
After OOP, C++ and Java exam was over, Yandex-King said "ok, let's go to data structures and algos". Man, was I happy.
Guy: what do you know about deque? // not the hottest question, but at least something
Me: Deque is an interface, which provides blah-blah...//ofc, I do know what is deque and the good thing is that we had just finished all this stuff at Discrete Math, so I was quite confident.
Guy: How one can implement it? What will be the complexity?
Me: let's implement it with vector, blah-blah, amortised complexity proof and all the stuff
Guy: amortised constant time is bad for Yandex. Yandex wants the true O(1)
Me: Ok, let's do the stuff with linked list, but in this case we won't have O(1) random access
Guy: Yandex wants the true O(1) with random access.
Me: wuuut
Guy: yeah, have a think
Me: (I could not figure out how to provide O(n) memory usage whenever there are n elements stored, with the true constant access/add/delete.) So I said "I think it's impossible". I was 99% confident it was yet another cunning question from this top interviewer and the answer is "impossible".
Guy: It is
Me: Ok, how?!
Guy: I won't tell you. You may google it as soon as you come home.
//I wasn't angry at this point. I thought that I really don't know something.
Girl: (yeah, she's here!) Ok, it's clear with your level of DS(her face meant that the level is low). Let's talk about algos. //Really?! You did bother me to name every standard class in Java I know(this question is the best to recognize the true talent), but asked only about one bloody DS, which is DEQUE!!
// The girl is still talking. Do you feel it? She's about to ask about algorithms. This one is going to be hot.
Girl: Do you know about F...F...fo...
Girl: For...For...Ford-, Ford-Fu, Fu...
...
Me: Fulkerson?
Girl: Yeah, what do you know about it?
Me: Blah-blah...//I started to say general statements about their theorem and all the stuff
Girl: ok (with like 3/10 excitement rate)
Girl: how can it be used?
Me: for finding the minimal cut, for a number of assignment problems, for dealing with some kind of networks, roads, etc.
Girl: ok
//My questions about the company.
// Finish
Any questions from the phony Yandex man? — No. Any problems considering the algo? — No. Any other problems requiring just a little thinking, but not learning by heart? — No. Checking English somehow? — No, of course.
When they were bringing me to the exit, they both were talking about how cool is CS centre and that I definitely should apply.

Epilogue

Do you remember the problem about deque? After the interview I asked some of VERY cool guys in this area, and they all said that they don't know about such magic deque implementation. I was pretty sad, because even if it does exist, it's quite not reasonable to ask such stuff for a intern position. So I asked Sosa girl via mail to share material with me, because I couldn't find anything. She asked the Wise Man and he gave her a link:
http://en.cppreference.com/w/cpp/container/deque
Tada! Please, don't hold your hand on your face for too long. I didn't really read it's content after seeing the complexity part. I just copied it and posted to the nickname girl. She never replied :)

Anyway, I am pretty thankful to this guys for being assholes. If they hire me, I probably wouldn't end up doing cool stuff at my current workplace :)

Read more »

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

By Rubanenko, 4 years ago, In Russian,

Всем привет!

Этот пост не несет в себе особой смысловой нагрузки. Просто скажите, понимаете ли вы условие этой задачи? Если да, то после какого по счету прочтения оно стало понятным?

UPD

Понял задачу после коммента про вес корзин. Действительно, зачем автору упоминать про вес корзин в условии, ведь это так естественно...приблизительно так же, как и корзина нулевого веса в сэмпле.

Read more »

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

By Rubanenko, 5 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: tuananh93

Russian Translators: vadimmm & Rubanenko

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

Read more »

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

By Rubanenko, 5 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!

Read more »

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

By Rubanenko, 5 years ago, In Russian,

Marathon24 is starting soon. I simply wonder whether there is someone else who have just waken up because of the bug in clist.by schedule. According to it the contest was to start at 3:00 AM. Yeah, it seemed strange, because Poland is almost in the same timezone as me, but I thought that they simply wanted to please Japanese guys which always have to get up at night to compete. The most impressive part was telling one of my teammates that he had to ride back home, and come in the morning instead. I am not sure he will :D

I might be wrong, but it seems I have seen the same starting time somewhere at the Marathon24 website.

Read more »

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

By Rubanenko, 5 years ago, In English,

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!

Read more »

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

By Rubanenko, 5 years ago, translation, In English,

Hey guys,

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

Read more »

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

By Rubanenko, 5 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

Read more »

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

By Rubanenko, 5 years ago, In English,

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

How to solve 1000?

Read more »

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

By Rubanenko, 5 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: 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.

Read more »

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

By Rubanenko, 5 years ago, In Russian,

Сегодня прошел ежегодный открытый чемпионат Харькова. Очень хотелось бы узнать, какое решение проходило в задача G? Мои сокомандники клянутся, что написали божественную декартку, но она не проходила по времени. У кого-то вышло пихнуть ее?

Read more »

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

By Rubanenko, 6 years ago, In Russian,

У меня есть друг, который зафэйлил IOI, и теперь хочет научиться решать задачки на Java. Что для этого нужно? С чего начать? Это вообще сложно?

Read more »

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

By Rubanenko, 6 years ago, In Russian,

Сегодня последняя ночь в роскошном общежитии, где наша команда жила во время подготовительных сборов к международной олимпиаде. Уже завтра днем мы вылетаем, и ровно через сутки прибудем в Австралию. Здесь я буду писать про наше путешествие, олимпиаду и многое другое.

В этот раз двое из участников (Furko & Rubanenko) уже имеют опыт участия в ioi, а двое участников присоединились лишь в этом году. Зато fedimser уже выигрывал золотую и серебряную медали на международной олимпиаде по астрономии, а Scorpy только закончил девятый класс, а значит с большой вероятностью к окончанию школы тоже будет иметь несколько международных наград.

Было бы интересно узнать когда приезжают другие русскоговорящие команды, так что пишите здесь о времени своего приезда.

На сегодня все, to be continued :)

Фото перед вылетом:

Прибыли в аэропорт в Дубае, встретили команду Македонии :) Через 2 часа следующий самолет. Скоро залью фото.

Первую ночь провели в отеле, фото из номера:

Фото со сборной Грузии в терминале в Дубае:

Дозаправились в Сингапуре, летим уже до конечной:)

Первую ночь провели в отеле, фото из номера:

Фото со сборной Мексики:

Бтв, всем реквестирующим обещаю фото со сборной России:)

Веселый получился тур. Уже на первом часу начала образовываться очередь длинной 10-15 минут. После 3 часа уже практически ничего не тестировалось. Задачу про картинки без фидбэка очень неинтересно писать, да и последние субтаски по вомбатам тоже, по-видимому нужно/можно было пропихивать. Лично я коряво написал проверку на одну компоненту в первой задаче, и это заходило на 65. Почти весь контест думал, что неправильная идея, ведь на 65 баллов — это решения для спецэффических графов. То есть в первых 4 группах не было тестов с одной компонентой >.<

На artclass периодически слал решения, за полчаса до конца узнал, что там все нули, так как забыл убрать дэбаг-аутпут в проге. За 5 минут до конца что-то послал, но уверенности у меня в этом решении немного.

Лично у меня нервы на пределе, как и у всех ребят, которые не успели нормально заслать арткласс до начала "веселья".

Кстати, в столовой тоже громадные очереди:)

Пара фоток с закрытия. А вообще, их очень много, так что через день-два отдельным постом все залью)

Read more »

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

By Rubanenko, 6 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.

Read more »

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

By Rubanenko, 6 years ago, In Russian,

Вот такой вот заголовок увидел сегодня. Собственно, хочется узнать...это правда?

Read more »

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

By Rubanenko, 6 years ago, In Russian,

Всем привет!

Меня интересуют два вопроса:

Первый: Как вы генерируете случайную перестановку? Я обычно беру перестановку 1,2,3..N, а потом О(N) раз свопаю рандомную пару. Насколько хорош этот метод и есть ли другие?

Второй вопрос: Как выбрать случайно подмножество размером К из N элементов за О(K)? Если за О(N), то можно ведь ответить на первый вопрос, а потом взять первые К элементов, да?:)

Read more »

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

By Rubanenko, 7 years ago, In Russian,

Сегодня в 16.00 по московскому времени пройдет вторая индивидуальная олимпиада на neerc. Правила, как я понимаю, будут абсолютно такие же как и в прошлый раз.

Всем желаю удачи!

Read more »

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

By Rubanenko, 7 years ago, In Russian,

Завтра, в 12.00 по Москве, начинается сезон мною очень любимых личных олимпиад на neerc.ifmo.ru/school! Не забудьте заново зарегистрироваться. Всем желаю удачи!

Разумеется, предлагаю после контеста здесь же обсудить задачи.

Read more »

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

By Rubanenko, 7 years ago, In Russian,

Как найти последнюю ненулевую цифру N! быстрее чем за О(N)?

Read more »

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

By Rubanenko, 7 years ago, In Russian,

Мне одному кажется, что когда-когда, а в воскресенье можно и пораньше контест провести? Я понимаю, что в некоторых странах будут различные накладки, но раньше эту проблему, пытались решить ротацией времени проведения раундов.Порядка десяти последних контестов, возможно, за исключением 1-2, проводились именно в 19.30 по Москве. Просто иногда совсем не в тему приходится вечер занимать раундом.

Какие мнения на этот счет у остальных?

Read more »

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

By Rubanenko, 7 years ago, In Russian,

Всем привет!

Я захотел поставить себе gedit, чтобы, собственно, на нем писать контесты. Но тут у меня возникла проблема: в скачанном мною с официального сайта gedit'е отсутствует external tool, который нужен для запуска и/или компиляции написанных программ.

Может у кого-то была такая проблема и вы знаете как ее решить? Скорее всего эту штуку надо где-то скачать, но в гугле ничего полезного не нашел.

Заранее спасибо за помощь!

Read more »

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