StasyaCat's blog

By StasyaCat, history, 11 months ago, In Russian,

Недавно был проведён первый отборочный тур Олимпиады Университета Иннополис.

К сожалению, я не смог решить D и E на полный балл, а разборы авторов меня не удовлетворили из-за отсутствия доказательств корректности. По этому, прошу всех тех, кто сдал эти задачи и при этом понимает, почему то, что он отправил работает, отозваться на мольбы и написать разбор с доказательством.

Условия

Если же вы раньше не видели эти задачи, но интересно попробовать их решить, возможно вам помогут следующие материалы:

Разбор на D, которые оставили автора:

"Выгодно брать только v, 0, s mod v. O(n^2)"

Я понимаю, как это написать, но не понимаю, почему это правильно.

На задачу Е создатели решили разбор не оставлять (то есть я даже не представляю как она делается).

Возможно, помогут авторские исходники:

Код авторского решения на D

Код авторского решения на E

Read more »

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

By StasyaCat, history, 11 months ago, In English,
Tutorial is loading...

C++ code: 46178226

Tutorial is loading...

C++ code: 46178084

Tutorial is loading...

C++ code: 46178118

Tutorial is loading...

C++ code: 46178228

Tutorial is loading...

C++ code: 46178239

Tutorial is loading...

C++ code: 46178244

Read more »

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

By StasyaCat, history, 13 months ago, In English,

I got two solutions for http://codeforces.com/contest/1036/problem/F

First one: 42893786 Second one: 42893945

First solution gets MLE, though it differs from second one only in line 81. On this line in first approach I try to use precalculated values from the array, instead of calculating them anew.

Can someone explain how a person can get MLE because of trying to get a value from an array?

Read more »

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

By StasyaCat, history, 16 months ago, In English,

I tried to test perfomance of different approaches to build and use trie data structure.

I used 706D - Vasiliy's Multiset to test my versions of tries on it.

The question is: Why does approach with pointers takes 2 times more memory than one with static array? As I know, a pointer stores an address of a variable, so it shouldn't take that much memory.

Here are my submissions:

Pointer approach: 40063381

Static array approach: 40063561

Any suggestions are welcomed!

Read more »

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

By StasyaCat, history, 18 months ago, In Russian,

Доброго времени суток!

Недавно я решал задачи с ХХХ Всероссийской олимпиады школьников по информатике. Меня весьма поразило авторское решение задачи 6 (подобный метод я не встречал нигде).

Может ли кто-либо объяснить мне почему авторское решение на 100 баллов корректно? А именно, почему метод построения обратной перестановки и решение задачи "наоборот" работает? Связано ли это с какими-то особыми свойствами обратной перестановки? Могу ли я подобный метод использовать для любых задач на перестановки (строить обратную данной и решать задачу с конца, заменив все действия обратными им)?

Условие задачи: http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf

Разбор: http://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-analysis.pdf

Read more »

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