gritukan's blog

By gritukan, history, 6 weeks ago, translation, In English,
Tutorial is loading...

(Idea — Jury of the Olympiad, developing — Andreikkaa)

Tutorial is loading...

(Idea and developing — Kniaz)

Tutorial is loading...

(Idea and developing — Sender)

Tutorial is loading...

(Idea — glebushka98, developing — ch_egor)

Tutorial is loading...

(Idea — GlebsHP, developing — Flyrise)

Tutorial is loading...

(Idea and developing — -__-)

Tutorial is loading...

(Idea — Endagorion, developing — Kraskevich)

Tutorial is loading...

(Idea and developing — wilwell)

Read more »

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

By gritukan, history, 3 months ago, In English,

(Idea — sender , developing — timgaripov)

Tutorial is loading...

(Idea — Chmel_Tolstiy, developing — -__-)

Tutorial is loading...

(Idea — Zlobober, developing — halin.george)

Tutorial is loading...

(Idea — GlebsHP, developing — -__-)

Tutorial is loading...

(Idea — glebushka98, developing — gritukan)

Tutorial is loading...

(Idea — Elena Andreeva, developing — gritukan)

Tutorial is loading...

(Idea — Zlobober, developing — malcolm)

Tutorial is loading...

Read more »

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

By gritukan, history, 2 years ago, In Russian,

Добрый день!

Попытался сегодня написать HLD (а точнее эту задачу). Писал полностью как написано на e-maxx, но при этом стабильно получаю WA. Что я делаю не так? Есть предположение, что я неправильно проверяю "тяжесть" ребра, но с округлениями в разные стороны все-равно WA. мой код

Спасибо большое!

Read more »

 
 
 
 

By gritukan, 3 years ago, In Russian,

Здравствуйте!

Уже в который раз натыкаюсь на странные runtime error, вероятно, связанные с неправильным использованием векторов. Что с этим делать?

Задача

Код

Огромное спасибо!

Read more »

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

By gritukan, 3 years ago, In Russian,

Здравствуйте!

Решал сегодня такую задачу: задача На первый взгляд ничего сложного: сортировка событий + сканирующая прямая.Но я запутался в реализации(случай, если несколько начал/концов отрезков в одной точке). Отсюда возник вопрос: а есть где-нибудь статья о сканирующей прямой, рассказаны все хитрости(в идеале еще и двумерный случай)?

Спасибо большое!

Read more »

 
 
 
 

By gritukan, 3 years ago, In Russian,

Здравствуйте!

При решении задачи наткнулся на следующую подзадачу: у нас есть n элементов и для каждой пары известен штраф за то, что они стоят рядом в перестановке. Необходимо сгенерировать перестановку с минимальным суммарным штрафом. Можно ли это решать быстрее, чем за O(N!) с отсечениями?

Спасибо!

Read more »

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

By gritukan, 3 years ago, In Russian,

Прошу прошения кодеры,как вы думаете на таком планшете возможно установить компилятор MS Visual Studio или GNU Compiler Collection.

Read more »

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

By gritukan, 3 years ago, In Russian,

Читая e-maxx наткнулся на информацию о существовании некого алгоритма Торупа, который ищет расстояния от заданой вершины до других за линию.

Гуглинг на русском языке не дал ничего, на английском выдал эту статью статья Я не очень понял идею, но все-таки возник вопрос: раз он такой крутой, почему его не используют?

Read more »

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

By gritukan, 3 years ago, In Russian,

Здравствуйте!

Возникла вот такая задачка: надо добавлять\удалять элементы из массива и при этом уметь быстро отвечать на вопрос о k порядковой статистике. С одной стороны, тут должен сет пройти, но с другой,насколько я знаю, итераторы в сете реализованы на подобии двусвязного списка, поэтому кроме k инкриметнов итераторов ничего не выйдет.

Что тут можно побыстрее засунуть? Спасибо!

Read more »

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

By gritukan, 3 years ago, In Russian,

Прошу прощения за беспокойство, но я не понимаю поведения gcc.

Вот 2 посылки с одинаковым кодом.

6781271

6781273

Как видите, хотя код и одинаковый вердикты разные...

На компьютере с windows 7/Mingw тоже работает.

Что я делаю не так?

Read more »

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

By gritukan, 4 years ago, In Russian,

Здравствуйте!

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

Спасибо!

Read more »

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

By gritukan, 4 years ago, In Russian,

Здравствуйте!

Попалась мне вот такая вот задачка. Начал её как-то криво решать, потом заглянул в темы и увидел, что задача на графы. После этого совсем перестал понимать в какую сторону идти.

Подскажите пожалуйста!

Read more »

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

By gritukan, 4 years ago, In Russian,

Здравствуйте!

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

В этом году на финал РОИ я не попал(не хватило 23 балла). Теперь я готовлюсь к следующему году, и у меня возникла следующая проблема: даже по первым задачам(финала РОИ) у меня никак не получается писать полные решения. То есть я сходу придумываю тупое решение на 30 или 60, но затем не могу придумать вообще ничего. Когда же я смотрю разбор и понимаю идею, само написание затруднений не вызывает. Поэтому у меня возникла пора вопросов:

1)Какие алгоритмы и приемы нужно знать для успешного выступления на РОИ? (вот тут говорят, что вообще редко бывает что-то сложнее дерева отрезков, но мне кажется,что бывает гораздо хуже)

2)Что стоит порешать, чтобы научиться придумывать решения по А\В на 100?(просто контестов РОИ довольно мало, нужно еще что-то)

3)Ну и вообще,что стоит поделать\поучить для хорошего выступления?

Заранее громадное Спасибо!

Read more »

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

By gritukan, 4 years ago, In Russian,

Здравствуйте! Тут внезапно появилась возможность поучавствовать в командном турнире.Правила как на ACM. Вопрос к опытным acm'щикам? Как Вы организовываете работу в команде, если есть всего один компьютер?Прошу прощение за нубство, так как возможность поучавствовать появилась внезапно...

Заранее спасибо!

Read more »

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

By gritukan, 4 years ago, In Russian,

Здравствуйте!

Возможно тема уже боянная, но все-таки: насколько успехи и познания человека в спортивном программировании помогут программисту в реальной работе? С одной стороны, конечно, понимание асимптотики алгоритма, умение оптимизировать код, да и просто бесценный опыт написания кода и отладки несомненно поможет в работе.Но с другой стороны я с трудом представляю, где в реальном программировании понадобятся различные структуры данных, которые так часто используются в спортивном программировании(стек,куча,красно-черное дерево,дерево отрезков и т.д), алгоритмы на графах тоже нужны не каждый день, да и крохотные доли секунды, от которых зависит вердикт задачи в рельной жизни часто не видны.

Собственно и прошу опытных и знающих участников разъяснить мне этот вопрос.

Read more »

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

By gritukan, 4 years ago, In Russian,

Привет всем!

Я пишу интерактивную задачу в Полигоне.

Программа должна посылать интератору запросы вида "символ число" (через пробел).Для этого я написал следующее в коде интератора

char c= ouf.readChar();

int a = ouf.readInt();

И получаю wrong output format Expected integer, but "=" found

Потом подумал, что пробел тоже символ и написал так

char c= ouf.readChar();

char p=ouf.readChar();

int a = ouf.readInt();

Та же петрушка.В чем дело?

Спасибо!

UPD

Если поменять символ и число местами, то прокатывает

int  a = ouf.readInt();
ouf.nextChar();
char c= ouf.readChar();

А вот наоборот- никак(

Read more »

 
 
 
 

By gritukan, 4 years ago, In Russian,

Только что повесили квоты на число участников заключистельного этапа Всероса по информатике.

Это число составило 260( на 10 больше чем в прошлом году). Соответстенно приблизительное количество участников по классам(исходя из распределения 1:2:3):

9 класс- 44

10 класс- 88

11 класс — 132.

Ну и приблизительные проходные баллы:

9 класс — 478

10 класс- 490

11 класс — 510.

P.S А зачем делают соотношение 1:2:3?

Read more »

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