Eran's blog

By Eran, 20 months ago, In Russian,

Буквально несколько дней назад закончилась сессия. Как и мой первый год в Академическом университете и третий год в жизни бакалавриата...

А потому хочется поделиться некоторыми впечатлениями. И, по возможности, дополнить и без того весьма полный пост от Пети Смирнова, рассказать о каких-то изменениях в жизни бакалавриата.

О том, как всё начиналось

Для начала хочется рассказать о том, как всё начиналось, и кто у нас вообще учится в Академическом университете.

В нашем году был набор 47 человек. Среди поступивших 14 человек — призёры и победители Всероса, причём двое по математике и один по физике. Также четверо — победители олимпиад 1 уровня (призёра для поступления не хватит). Оставшиеся 29 человек поступали по ЕГЭ.

В текущем же году набор составит уже 36 человек.

По уровню подготовки, как видно, люди действительно поступали совсем разные. Однако всё это было учтено при подготовке программы. В частности, в первую неделю обучения нам предложили написать тесты, по результатам которых нас распределили на группы по математике и программированию в зависимости от начальной подготовки. Так что скучать никому не приходилось ;)

Что касается программы нашего курса, то Петя Смирнов подробно написал про неё в своём посте.

Могу лишь написать о некоторых изменениях по сравнению с 2014 годом. А именно, из программы пропала физика (что, наверное, для многих будет плюсом ;)). В остальном же всё осталось по-прежнему.

Обучение

Учиться приходится много. Очень. Очень много. У многих на учёбу может уходить и вовсе всё своё свободное время, так что надо быть готовым к этому. И пусть перед Новым годом мы смогли-таки найти время на то, чтобы поставить в студкомнате ёлку, но с тех пор так и не нашли время, чтобы разобрать её ;)

Особенно сложной для многих выдалась первая четверть учебного года. К примеру, кто-то, поступая в университет, совсем не умел программировать, никогда не слышал об алгоритмах. Другие же, наоборот, имели большие пробелы в математике. А потому работать приходилось очень много.

Наверное, главное здесь — иметь желание, не бояться просить помощи у окружающих. И, как показала практика, все желающие за эти несколько месяцев подтянулись до необходимого уровня. Так что сильно беспокоиться не стоит ни тем, кто недостаточно уверенно себя пока что чувствует в этой сфере, ни тем, кто рассчитывает на сильную программу с первых дней. Всё это будет.

Из особенностей обучения, пожалуй, стоит выделить разделение предметов на лекции/практики. Так, сначала всему потоку читаются лекции, материал которых осознаётся и разбирается подробнее на практиках. В частности, поскольку практические занятия разделяются по довольно небольшим группам, к учащимся вырабатывается персональный подход, что не может не радовать.

Радует ещё и то, что преподавательский состав у нас в большинстве своём довольно молодой и весьма перспективный. Нудных лекций и практик у нас не бывает :)

Да и вообще в АУ царит очень дружелюбная и располагающая атмосфера. Вы в любой момент можете в спокойной обстановке пообщаться со своими преподавателями, куратором или однокурсниками. Вам всегда помогут разобраться, и даже могут приподнять настроение в совсем сложных ситуациях :)

А ещё у нас буквально с первых дней учёбы начали создаваться студенческие конспекты по основным предметам. Также по каким-то предметам конспекты ведут сами лекторы (к примеру, есть конспекты по алгоритмам от Серёжи Копелиовича и по дискретной математике от А.В. Омельченко). Ко второму семестру у нас даже появился сайтик от cdkrot, на котором выкладываются наши конспекты.

Олимпиады

Хочется несколько слов сказать про олимпиады. Хотя, по-видимому, я и повторю уже сказанное Петей...

Во-первых, курс алгоритмов предполагает еженедельное решение контестов.

Разумеется, не всем этого хватает, а потому для любителей олимпиад у нас по субботам проводятся тренировки. Личные и командные. На большее, впрочем, хватает очень немногих... Но спорить не буду, такие находятся.

Если есть желание, то существует возможность поехать на Петрозаводские сборы.

Есть также возможность съездить и на разные студенческие и не только олимпиады. В этом году нашу команду приглашали на командный чемпионат в Самару. Из более значимых — в этом году несколько наших команд успешно съездили на Google HashCode во Францию, а также уже второй год наши команды вполне достойно показывают себя на финале ACM :)

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

Отдых

"Какой же отдых?!", — спросите вы после всех рассказанных страшилок о постоянной учёбе.

Свободного времени и правда, как правило, остаётся не слишком много. Но, как говорится, было бы желание.

Так, мы курсом выбирались в театр, ходили на лазертаг. На каникулах ездили компанией в Великий Новгород на Бегущий Город.

И пусть даже это не слишком часто происходит, но зато отсутствие большого количества свободного времени компенсируется наличием в университете студенческих комнат. Если коротко, то это потрясающая возможность отдохнуть вместе со своими однокурсниками, пообщаться. Частенько в ней можно найти гитару вместе с любителями поиграть на ней. Есть холодильник и микроволновка с чайником. А в шкафу можно обычно найти какие-нибудь вкусняшки.

В студкомнатах вообще всегда царит очень уютная атмосфера. А с некоторых пор даже появилась "стена боли", на которой каждый может поделиться своей болью касательно учёбы и жизни :)

Для живущих в общежитии по выходным ещё бывает опция "загамать в настолки". Просто чтобы отвлечься ненадолго от того потока информации, который приходится воспринимать за время учебной недели.

Общежитие

К слову о. В общежитиях у нас очень круто :)

Комнаты весьма просторные. Есть комнаты на двоих и на троих. Последние, к слову, скорее напоминают полноценную квартиру. Всё, так сказать, включено. На каждом этаже есть своя кухня с холодильниками, микроволновыми печами и чайниками. Есть также постирочная и комната для сушки.

В принципе, при желании всем этим можно оборудовать и свою комнату. И можете не беспокоиться, что в них не хватит места. Но особой необходимости в том точно нет.

Также в общежитии предусмотрена специальная комната, в которой можно оставить ваш велосипед, если таковой имеется.

А ещё совсем скоро у нас откроется второй корпус общежития. И тогда станет совсем просторно жить :)

В завершение...

Год закончился. У всех свои планы на это лето. Двое едут на стажировку в Google, ещё один человек — уже стажируется в JetBrains. К слову, все трое — милые девушки :)

Очень многие едут в ЛКШ в качестве преподавателей. А кто-то решил ботать и отдыхать в своё удовольствие.

Про себя могу сказать, что год прошёл очень продуктивно и интересно. Наверное, более дружного коллектива, чем здесь, мне до сих пор не приходилось встречать. И здесь ты всегда можешь быть уверен в том, что тебя поддержат. Что тебе объяснят непонятный материал и помогут справиться с нагрузкой.

...

Пожалуй, на этом всё :)

Read more »

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

By Eran, 3 years ago, translation, In English,

703A — Mishka and Game

In this problem you had to do use the following algo. If Mishka wins Chris in the current round, then increase variable countM by 1. Otherwise (if Chris wins Mishka) increase variable countC. After that you had to compare this values and print the answer.

703B — Mishka and trip

Let's look at the first capital. Note that the total cost of the outgoing roads is c[id1] · (sum - c[id1]), where sum — summary beauty of all cities. Thus iterating through the capitals we can count the summary cost of roads between capitals and all the other cities. But don't forget that in this case we count the roads between pairs of capitals twice. To avoid this on each step we should update sum = sum - c[idcur] , where idcur is the position of current capital. In the end we should add to the answer the cost of roads between "non-capital" neighbour cities.

Complexity — O(n).

703C — Chris and Road

Imagine that the bus stands still and we move "to the right" with a constant speed v. Then it's not hard to see that movement along the line y = (u / v) · (x  -  v · t0) is optimal, where t0 — time in which we begin our movement. In this way answer is t = t0 + (w / u).

If t0 = 0, then we start our movement immediately. In this case we need to check that our line doesn't intersect polygon (either we can cross the road in front of a bus, or the bus is gone).

Otherwise we need to find such minimal t0 that our line is tangent to the polygon. It can be done with binary search.

Complexity — O(nlogn).

Exercise: Solve this problem in O(n).

703D — Mishka and Interesting sum

Easy to see, that the answer for query is XOR-sum of all elements in the segment xored with XOR-sum of distinct elements in the segment. XOR-sum of all numbers we can find in O(1) using partial sums. As for the XOR-sum of distinct numbers... Let's solve easier problem.

Let the queries be like "find the number of distinct values in a segment". Let's sort all the queries according to their right bounds and iterate through all elements of our array. We also need to make a list last, where last[value] is the last position of value on the processed prefix of array. Assume we are at position r. Then the answer for the query in the segment [l,  r] (l ≤ r) is , where cnt[i] = 1 if last[ai] = i and 0 otherwise. It's easy to store and update such values in cnt. When moving to the next position we have to make the following assignments: cnt[last[ai]] = 0, cnt[i] = 1, last[ai] = i. To get described sum in O(logn) we can use segment tree (or Fenwick tree) instead of standard array.

Now let's turn back to our problem. Everything we have to do is to change assignment cnt[i] = 1 to cnt[i] = ai and count XOR-sum instead of sum. Now we can solve this problem in O(nlogn).

Solution (with Fenwick)

P.S.: Also there is a solution with O(nsqrtn) complexity (using Mo's algo), but we tried to kill it :D

703E — Мишка и делители

Let's use dp to solve this problem.

Suppose dp[i][d] is the minimal number of elements on prefix of size i, that their product is divisible by d. It's easy to see that dp[i][d] = min(dp[i  -  1][d],  dp[i  -  1][d  /  gcd(d,  ai)]  +  1). That is so because it's optimal to take as much divisors of ai as possible. Answer — dp[n][k].

Let's imrove our solution. Notice, that as d we should use only divisors of k (which in the worst case would be 6720). As for gcd, we can easily find it in O(primes(k)), where primes(k) — number of primes in decomposition of k. We also need to renumber our divisors according to their prime decomposition.

To get AC in this problem you had to optimize described dp and add minimization of used elements' sum. Final complexity — O(n · divs(k) · primes(k)).

Solution

Read more »

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

By Eran, 3 years ago, translation, In English,

Hi everyone!

Codeforces Round #365 (Div.2) takes place today on 4th of August at 18:05 MSK. As usual Div.1 participants can join out of competition.

I am the author of all the problems, and this is my first round on Codeforces. I advise you to read all the problems, hope you will enjoy them :)

I'd like to thank GlebsHP and dans for helping me in preparing problems, MikeMirzayanov for the great Codeforces and Polygon platforms and IlyaLos for some useful adviсe.

In this round you will meet Mishka, a little polar bear. She is still young, that's why she may have some problems in finding answers for difficult questions. Will you help her to cope with some of them? :)

UPD. 5 problems, 2 hours to solve them and scoring distribution: 500 — 1000 — 1750 — 2000 — 2250

UPD. We apologize for the inconvenience. All solutions will be judged soon.

UPD. Round is unrated.

UPD. The contest is over. Congratulation to the winners!

Div1: 1. uwi 2. kmjp 3. savinov 4. BigBag 5. KrK

Div2: 1. meteor 2. TmEnd 3. chenjiamin 4. laekov 5. Denisson

Editorial will be published in the nearest time.

UPD. Editorial

Read more »

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